' Puzzlet #083 ' Take the sums of the cubes of the in- ' dividual digits of a 5-digit integer ' to form a new integer. Repeat this ' process until the integer equals 153. ' Which integer, less than 15300, and ' divisible by 3, takes the maximum ' number of iterations to reach 153? ' By Dave Ellis. declare SumCubes(s: int) declare PrintIt(p: int, n: int) def current, itCount, i, maxIts: int openconsole print "Searching ...": print maxIts = 0 for i = 10002 to 15299 #3 current = i itCount = 0 do current = SumCubes(current) itCount = itCount + 1 until current = 153 if itCount > maxIts maxIts = itCount PrintIt(i, itCount) endif next i print: print "Done!" print: print "Press any key to exit ..." do: until inkey$ <> "" closeconsole end sub SumCubes(s) ' Accepts integer s, returns sum ' of cubes of digits of s. def s$: string def i, L, tot: int s$ = ltrim$(str$(s)) L = len(s$) tot = 0 for i = 1 to L tot = tot + (val(mid$(s$,i,1)))^3 next i return tot sub PrintIt(p, n) ' pretty printer def m$, p$: string def it, L, m: int p$ = ltrim$(str$(p)) L = len(p$) for it = 1 to L - 1 m$ = mid$(p$, it ,1) print m$,"^3 + ", next it m$ = mid$(p$, L ,1) print m$,"^3 using ", print using ("##", n), print " iterations." return |
| PROGRAM NOTES Iterator i in the main routine is used to examine all legal values in the stipulated range, Solutions have to be 5-digit integers, less than 15,000, and divisible by 3, so the code line for i = 10002 to 15299 #3 captures these requirements. The process will always alter i into a smaller number as it adds the cubes of its digits and starts over, continuing until i has reduced to 153. Obviously, we would lose track of what numbers had been checked this way by mutating i, To prevent this, i 's value is copied into variable current (that is, "the current number being investigated"), and all the processing carried out on current, leaving i unchanged. We need to keep track of how many iterations it takes for current to be transformed into value 153. Variable itCount is created for this purpose, and is set initially to zero every time a new number is loaded into current for processing. Once this has all been set up, the whole program is effectively contained in the lines:
do
current = SumCubes(current) itCount = itCount + 1 until current = 153 current's value is passed as the parameter to function SumCubes. The latter simply adds together the cubes of each digit in current and then places the sum back into current, overwriting its original value. Each time this happens, itCount is incremented, since another iteration of the process has taken place. Eventually, current will contain value 153. When this happens, the DO-LOOP can be exited. Remember, this loop is executed for each value of i. At the beginning of the program, variable maxIts (for "maximum number of iterations so far") was initialised to zero. Every time the DO-LOOP yields a value in itCount which is greater than maxIts, we have found a new maximum number of iterations required to reach 153, and this is printed out neatly by the subroutine PrintResult(). That's all there is to it. The function and subroutine used by the program are self-exlanatory. If you would like further information on how they work, or anything else about the program, please contact me. |
| As
you can see from the inset sketch, the code finds five successively
greater iteration values. The solution is the last (and largest) one found: a total of 14 iterations. |
|
Searching
... 1^3 + 0^3 + 0^3 + 0^3 + 2^3 using 5 iterations. 1^3 + 0^3 + 0^3 + 0^3 + 5^3 using 10 iterations. 1^3 + 0^3 + 0^3 + 1^3 + 7^3 using 11 iterations. 1^3 + 0^3 + 0^3 + 7^3 + 7^3 using 13 iterations. 1^3 + 2^3 + 5^3 + 5^3 + 8^3 using 14 iterations. Done! Press any key to exit ... |
| Site design/maintenance: Dave Ellis | E-mail
me! |
Last Updated: April 4th, 2004. |