Re: a new challenge
Message #83 Posted by David Hayden on 16 Jan 2011, 10:52 a.m.,
in response to message #1 by Don Shepherd
Here is a solution to the challenge in User RPL that takes a completely different approach. On a 50g, it runs in 123 seconds. I
haven't attempted any coding optimization - the time is due entirely
to the algorithm - so I'm sure it can be improved.
Instead of checking each possible 4-digit number to see whether it's
divisible by the sum of its digits, this program starts with a
possible sum of digits for four consecutive numbers. It then checks
the much smaller set of numbers that can be divided by this set.
For example, the sum of the digits in the first solution (beginning at 1014) are 6,7,8, and 9. It turns out that any set of numbers N, N+1, N+2, N+3 that are divisible by 6,7,8 and 9, must be of the form N = 6 + 504k where k is an integer. So for the sums {6 7 8 9} we only have to check every 504'th number.
The program is quite long and this will be a long explanation. I hope you'll find it interesting. I implemented the program is a directory for simplicity (and debugging!) and I'll refer to the various programs in the directory.
Throughout this explanation, I'll use N, N+1, N+2 and N+3 (or N0, N1, N2 and N3) to refer to the sequential 4-digit numbers, and I'll use s0, s1, s2 and s3 to refer to the sum of the digits in each of these numbers.
Enumerating the sums of digits
To begin, lets figure the possible values for the sum of the digits of four sequential numbers between 1000 and 9999. Clearly the smallest sum is 1 (for 1,000) and the largest sum is 36 (for 9999). So any sum must between 1 and 36.
For most sequences of N, the sum of their digits is also a
sequence. E.G, for N = {1001, 1002, 1003, 1004 }, s = {2 3 4 5}.
So one possible set of sums is:
{s s+1 s+2 s+3} for s= 1 through 33
Now consider N = {1207 1208 1209 1210}. The digit sums are s = {10 11 12 4}. In general, when the one's digit rolls over from 9 to 0, you lose 9 in the digit sum, but you gain 1 because the 10's digit increments. So another possible set of sums is:
{s s+1 s+2 s-6} for s=8 to 33
The roll-over from 9 to 0 could occur anywhere in the sequence, so
other possibilities are:
(s s+1 s-7 s-6) for s=9 to 34
(s s-8 s-7 s-6) for s=10 to 35
The numbers in N can also roll over from 99 to 00 or 999 to 000, these give the possible sums:
{s s-17 s-16 s-15} for s=19 to 35
{s s+1 s-16 s-15} for s= 18 to 34
{s s+1 s+2 s-15 } for s= 17 to 33
{s s-26 s-25 s-24} for s=27 to 36
{s s+1 s-25 s-24} for s=26 to 35
{s s+1 s+2 s-24} for s=25 to 34
In my solution, all of these lists are calculated by the SUMS program. The result of SUMS is a list of lists where each sublist is 4 numbers that represent the sums of the digits of 4 consecutive numbers.
Restricting the start and end values
The challenge asks us to find a 4-digit number - one that's between
1000 and 9999, but if we start with a possible sum of the digits in N, we can use that information to restrict the upper and lower bounds of the search. For example, suppose we're considering the sums 10, 11, 12, and 13. The smallest 4-digit number whose digits add up to 10 is 1009 and the largest is 9001, so there's no point in checking numbers less than 1009 or larger than 9001.
The subprogram BIGandSMALL calculates the largest and smallest 4-digit numbers whose digits sum to each of the values between 1 and 36. It leaves the results on the stack in two arrays. The main program calls BIGandSMALL once and stores the results in global variables BIGGEST and SMALLEST. For example, BIGGEST[12] is the biggest 4 digit number whose digits sum to 12. Later when we check a particular set of sums, we use BIGGEST and SMALLEST to get the upper and lower bounds of the loop.
Mathematics
Suppose we're given a list {s0 s1 s2 s3} that is a solution for the
sequence of numbers {N N+1 N+2 N+3}. That means that N is evenly
divisible by s0, N+1 is evenly divisible by s1 etc. Mathmatically:
N == 0 mod s0
N+1 == 0 mod s1
N+2 == 0 mod s2
N+3 == 0 mod s3
or equivalently:
N == 0 mod s0
N == -1 mod s1
N == -2 mod s2
N == -3 mod s3
(I'm using "==" to mean "congruent to," which is usually indicated by a symbol with three horizontal lines).
What are the values of N that satisfy these equations? The first
equation means that N = k0*s0 for any integer k0. Plugging that into the second equation gives k0*s0 = -1 mod s1. Can we simplify this into the form k0 = r mod s? The answer is yes.
Solving modulo equations - there's an app for that!
In a more general sense, how do you solve Ax == B mod C? This is done with the Linear Congruence Theorem. The procedure goes like this:
- If (B / GCD(A,C)) not an integer,then there is no solution
- Let D = GCD(A,C).
- Find r and s such that rA + sC = D
- The solution is x == (rB/D) mod (C/D)
How do you find r and s? It's built-in to the 50G! The IEGCD command does it for you.
Here is the function that solves a single modulo equation:
@ This solves an equation of the form ax = b mod n
@ Where "=" really means "is congruent to".
@ It returns r s such that x = r mod s, or
@ equivalently x = s*k + r
@ arguments are a b n (must be integers)
@ Results are r s 1. if there's a solution, or
@ 0. if no solution exists.
@ See http://en.wikipedia.org/wiki/Linear_congruence_theorem
@ and the IEGCD command for details.
SLVMOD
\<< \-> a b n \<<
@ If GCD(a,n) doesn't divide b evenly then no solution
IF b a n GCD / DUP IP \=/ THEN
0.
ELSE
@ It's good!
a n IEGCD DROP
b * OVER /
n ROT /
1. @ Indicates success
END
\>>
\>>
Solving simultaneous modulo equations
Let's return to the original problem. We want to find N such that it
simultaneously solves:
N == 0 mod s0
N == -1 mod s1
N == -2 mod s2
N == -3 mod s3
More generally, suppose we want to solve two simultaneous equations:
X == b mod a, and
X == r mod s
we do it as follows:
X = a*k0 + b (for any integer k0)
a*k0 + b == r mod s (substituting for X into the second equation
k0*a == (r-b) mod s (subtract b)
We can use SLVMOD on this equation to find:
k0 == u mod v, or equivalently
k0 = k1*v + u for any integer k1
and substituting for k0 into the equation above:
X = a*(k1*v+u) + b
= (a*v)k1 + (a*u + b)
X == (a*u+b) mod (a*v)
The program SSLVMOD solves these simultaneous modulo equations:
@ Given two equations:
@ x = r mod s, and
@ x = b0 mod a0
@ This program returns b1 and a1 such that
@ x = b1 mod a1
@ Arguments: b0 a0 r s
@ results: b1 a1 1. (if there is a solution), or
@ 0. if not
SSLVMOD
\<< \-> b a r s
\<< a r b - s
IF SLVMOD
THEN a * SWAP a * b + SWAP 1.
ELSE 0.
END
\>>
\>>
Putting it all together
The somewhat poorly named FACTS program takes a list of possible sums of digits {s0 s1 s2 s3} and computes a and b such that N == a mod b and
N == 0 mod s0
N == -1 mod s1
N == -2 mod s2
N == -3 mod s3
Remember, this means that if {s0 s1 s2 s3) are a possible sum-of-digits, then the vales N == a mod b are the only possible numbers where N, N+1, N+2 and N+3 are evenly divisible by s0, s1, s2, and s3 respectively.
For example, given the list of possible sums-of-digits {4 5 6 7}, FACTS determines that N == 4 mod 420 are the only values that will work.
The CHKSUM prorgam takes a list of possible digit sums and checks for a solution to the challenge that matches that list. In other words, it checks to see if there is a sequence of four 4-digit numbers that are (1) evenly divisible by the numbers in the list, AND (2) whose sum of digits equals the values in the list.
CHKSUM uses FACTS to determine the possible values that satisfy the
first criteria. Then it uses the BIGGEST and SMALLEST arrays arrays
to look up the largest and smallest numbers that satisfy the
sum-of-digits criteria. Finally, it uses a FOR loop to check each of the possible values to see if it matches the sum-of-digits criteria.
The DIGITS program takes an integer and computes the sum of its digits.
The MAINP program is the main entry point to the algorithm. It
computes and stores the biggest and smallest 4-digit numbers for each possible sum. Then it calls SUMS to create the list of all possible sums of digits of sequences of 4-digit numbers. Finally, it uses DOLIST to call CHKSUM on each of these possible sums.
Conclusions
I think this is a good example of how you can squeeze performance out of a program by exploiting the properties of the problem that you're trying to solve. By starting with the potential sum of digits and then working forward to the possible 4-digit number (rather than the other way around), this program cuts down on the work needed:
- Computing the biggest and smallest numbers with the given sum cuts the range of numbers that you need to check.
- Computing the possible numbers that satisfy the divisibility test cuts the numbers down even more.
The program also demonstrates that it's worth stepping back from a
problem and asking "is there a different approach that might work."
Program Listing
%%HP: T(3)A(R)F(.);
DIR
MAINP
\<< BIGandSMALL 'SMALLEST' STO 'BIGGEST' STO SUMS 1.
\<< CHKSUM
\>> DOLIST
\>>
DIGITS
\<< 0. SWAP
WHILE DUP
REPEAT DUP 10. MOD ROT + SWAP 10. / IP
END DROP
\>>
FACTS
\<< 0. \-> L n
\<< 0. 1. 1. L 1.
\<<
IF SWAP
THEN n 'n' 1. STO- SWAP SSLVMOD
ELSE DROP 0.
END
\>> DOLIST
\>>
\>>
CHKSUM
\<< \-> L
\<< L
IF FACTS
THEN L HEAD { } \-> a b N RES
\<< SMALLEST N GET a - b / CEIL b * a + BIGGEST N GET
IF DUP2 \<=
THEN
FOR I
IF I DIGITS N ==
THEN 1. 1. 3.
FOR K I K + DIGITS L K 1. + GET == AND
NEXT
IF
THEN I 'RES' STO+
END
END b
STEP
IF RES SIZE
THEN RES
END
ELSE DROP DROP
END
\>>
END
\>>
\>>
SUMS
\<< 1. 33.
FOR i i DUP 1. + DUP 1. + DUP 1. + 4 \->LIST
NEXT 8. 33.
FOR i i DUP 1. + DUP 1. + i 6. - 4 \->LIST
NEXT 9. 34.
FOR i i DUP 1. + i 7. - i 6. - 4 \->LIST
NEXT 10. 35.
FOR i i DUP 8. - DUP 1. + DUP 1. + 4 \->LIST
NEXT 19. 35.
FOR i i DUP 17. - DUP 1. + DUP 1. + 4 \->LIST
NEXT 18. 34.
FOR i i DUP 1. + DUP 17. - DUP 1. + 4 \->LIST
NEXT 17. 33.
FOR i i DUP 1. + DUP 1. + DUP 17. - 4 \->LIST
NEXT 28. 35.
FOR i i DUP 26. - DUP 1. + DUP 1. + 4 \->LIST
NEXT 27. 34.
FOR i i DUP 1. + DUP 26. - DUP 1. + 4 \->LIST
NEXT 26. 33.
FOR i i DUP 1. + DUP 1. + DUP 26. - 4 \->LIST
NEXT 186. \->LIST
\>>
BIGandSMALL
\<< 0. 36. NDUPN \->ARRY DUP \-> bigres smallres
\<< 1. 36.
FOR i 0. 1000. i \-> val mult cur
\<<
WHILE cur
REPEAT cur 9. MIN 'cur' OVER STO- mult * 'val' STO+ 'mult' 10. STO/
END 'bigres' i val PUT 1. 'mult' STO i 1. - 'cur' STO 1000. 'val' STO
WHILE cur
REPEAT cur 9. MIN 'cur' OVER STO- mult * 'val' STO+ 10. 'mult' STO*
END 'smallres' i val PUT
\>>
NEXT bigres smallres
\>>
\>>
SLVMOD
\<< \-> a b n
\<<
IF b a n GCD / DUP IP \=/
THEN 0.
ELSE a n IEGCD DROP b * OVER / n ROT / 1.
END
\>>
\>>
SSLVMOD
\<< \-> b a r s
\<< a r b - s
IF SLVMOD
THEN a * SWAP a * b + SWAP 1.
ELSE 0.
END
\>>
\>>
END
| 
Go back to the main exhibit hall