The Museum of HP CalculatorsHP Articles Forum
[Return to the Index ]
[ Previous | Next ]
Sum of Digits Divisibility Challenge - an unusual solution
Posted by David Hayden on 16 Jan 2011, 9:39 p.m.
On January 5, 2011, Don Shepherd posed the following challenge in the forum. You should be able to find the thread in the archives.
Quote:
A new year deserves a new challenge!Write a program on whatever calculator you like to answer the following question: Are there 4 consecutive 4-digit integers that are each evenly divisible by the sum of their digits? If so, list them (there MAY be more than one set, and I probably wouldn't pose this challenge if there were no sets).
For example, if 1001 is evenly divisible by 2 and 1002 is evenly divisible by 3 and 1003 is evenly divisible by 4 and 1004 is evenly divisible by 5, you've got a set. Of course, only one of those 4 conditions is true in this example, so 1001-1004 don't work.
So post your program and tell how long it took. This challenge has no practical value that I can think of other than it's just fun to develop the algorithm and get it to work, and that's reason enough for me.
Many clever solutions were posted, but they mostly used and optimized the same basic algorithm:
for each number between 1000 and 9999
if it's divisible by the number of digits then
if the next 3 are also divisible by the number of digits then
you have found a solution
For fun, I decided to try a completely different approach. I posted my solution on January 16, 2011. Don asked me to post it as an article, so here it is. I want to thank Don for providing this challenge.
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 as 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.
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 be 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 35The 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.
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.
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(I'm using "==" to mean "congruent to," which is usually indicated by a symbol with three horizontal lines).or equivalently: N == 0 mod s0 N == -1 mod s1 N == -2 mod s2 N == -3 mod s3
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.
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:
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
\>>
\>>
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 s3More generally, suppose we want to solve two simultaneous equations:
X == b mod a, and X == r mod swe 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 k1and 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
\>>
\>>
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 s3Remember, this means that if {s0 s1 s2 s3) are a possible sum-of-digits, then the values 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.
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:
The program also demonstrates that it's worth stepping back from a problem and asking "is there a different approach that might work."
%%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
Edited: 15 Mar 2012, 4:20 p.m.
Go back to the main exhibit hall