PUZZLET 99 - THE SOLUTION
| '
Puzzlet #099 ' Find five consecutive 6-digit integers ' such that each one can be divided by the ' sum of its own digits without remainder. ' Hint: five is the maximum chain with ' this property. ' By Dave Ellis. declare SumDigits(d: int) declare PrintResult() def count, flag, nr, tempNr, sum: int def quotient: float openconsole print "Working ...": print nr = 100000 do count = 0 flag = -1 tempNr = nr do sum = SumDigits(tempNr) quotient = tempNr/sum if quotient = int(quotient) count = count + 1 tempNr = tempNr + 1 else flag = 0 endif until flag = 0 if count = 5 PrintResult() endif nr = tempNr + 1 until nr > 999995 print: print "Done!" print: print "Press any key to exit ..." do: until inkey$ <> "" closeconsole end sub SumDigits(d) ' returns the sum of the ' digits of integer d def tot: int tot = 0 do tot = tot + d%10 d = int(d/10) until d = 0 return tot sub PrintResult ' pretty printer def it: int for it = 5 to 1 #-1 print tempNr - it, next it return |
| PROGRAM NOTES Variable count keeps track of how many consecutive numbers have been found in the current search which can be divided by the sum of its own digits without remainder. Variable flag is used to indicate whether or not the current number meets the specification (that is, it can be exactly divided by the sum of its own digits). Variable nr holds the number being currently investigated. Variable tempNr holds the latest number in the small series which meet the specification. It is initially derived from nr, but increments each time the specification is met. If it ever reaches nr + 4, we have a series of five and thus a solution. Variable sum holds the sum of the digits of the number currently being investigated. |
| The inset flowchart describes what the code
is doing. We begin by initialising variables. nr is set to the minimum possible value for a solution, 100000. The count value must be zero. flag is set to -1 (TRUE), assuming this is going to be a correct answer unless indicated otherwise. Now we set tempNr equal to the current value of nr, so that it can be varied without affecting nr. At this point we enter the main DO loop, which constitutes the program proper. tempNr is passed as parameter to function SumDigits(), whose job is to totalise the individual digits of its argument and return the total. This value is then stored in sum. The original value, tempNr, is divided by the recently-derived sum, and the result stored in quotient. Effectively, we have just divided tempNr by the sum of its own digits. We're looking for numbers which can do this without remainder, and the code now goes on to check it. If quotient is an integer, no remainder exists. If this is the case, flag is left at its preset TRUE value, otherwise its reset to FALSE (0). count and tempNr are now both incremented, ready for the next checks |
 |
| Before continuing, we need to check flag's status. If it's 0, the DO
loop is exited, otherwise it's executed again. In the latter case, the
current value in count is
retained, along with the newly-incremented value in tempNr. So the length of the
chain increases if the successive numbers permit it to. We know from
the specification that count
won't exceed 5, so, even for a maximum chain length, flag will eventually be reset to 0
and the loop exited. After exiting the loop, count may or may not equal 5. If it does, we have a valid solution and it's sent to subroutine PrintResult() for output to the screen. Either way, nr must be set to the beginning of the next possible sequence. That will begin just after the last value in tempNr, so nr is set to that value now. If nr is now greater than 99995, the maximum possible starting value for a correct sequence, there's no point in continuing and the program stops. If not, the whole thing starts again but with the new value in nr. |
| When
you run the program, you'll see the inset printed out to your
computer's screen. These two are the only possible solutions, unless you know something I don't . . . |
|
|
Working
... 131052 131053 131054 131055 131056 491424 491425 491426 491427 491428 Done! Press any key to exit ... |