S&SMC#6: An HP-71B solution
Message #8 Posted by Ex-PPC member on 13 Mar 2003, 6:37 a.m.,
in response to message #7 by Michael F. Coyle
Michael wrote:
I know it's kind of late in the game, but I do have a solution to this problem, written for the 48GX [...]
Hopefully this will still be of interest to someone. For me, the fun was just getting a working program.
Thanks for your interest in my challenge, perhaps it was
a little more difficult than the usual "do this simple thing in the least possible number of programming steps", but it certainly offered an opportunity to show off one's favorite HP calc and some advanced programming techniques, right ?
As promised, here's a solution to both the original and the extended challenge, for the HP-71B. As usual, it's far from optimal, but it can be written very easily and gets the job done quickly:
This short (164 bytes) program recursively finds all
numbers that have the property
that the number consisting in the first N leftmost digits is divisible by N, for N ranging from 2 to 9 digits. Repeated digits are allowed for this version.
10 DESTROY ALL @ OPTION BASE 0 @ DELAY 0,0 @ STD
20 FOR I=1 TO 9 @ CALL TST((I),2,9) @ NEXT I @ DISP "DONE!" @ END
30 SUB TST(N,D,M) @ N=10*N @ FOR I=0 TO 9 @ X=N+I @ IF MOD(X,D) THEN 50
40 DISP D;X @ IF D#M THEN CALL TST(X,D+1,M)
50 NEXT I @ END SUB
It simply starts from 1-digit numbers and calls a subprogram that adds a new digit, testing all 10 possibilities for divisibility. When a suitable candidate appears, the subprogram calls itself, to add yet another digit, and so on till the number is 9 digits long and all possibilities have been tested. Brief comments:
- Line 10 simply sets up some initial conditions; you may want to change the DELAY to slow down the display, but the STD is important to keep the presentation tidy.
- Line 20 is the "main program": it just stablishes a loop to find solutions from 2 to 9 digits long, and calls the
subprogram to do the actual work. That's it. You could
search for numbers up to 12 digits long just by changing the 9 to 12 !
- Line 30 is the subprogram: it tests all 10 possibilities by adding a new digit to the already existing ones, and if the divisibility condition is met, it simply calls itself to add yet another digit
- Notice how the recursive call CALL TST(X,D+1,M) at line 40 depends on a condition, else the recursion would go ever deeper.
If you RUN this program, you'll get an output like this:
2 10 -> 3 102 -> 4 -> 1020 -> 5 -> 10200 -> 6 102000
-> 7 1020005 -> 8 10200056 -> 9 -> 102000564
-> 6 102006, etc
To find a 10-digit solution with no repeated digits, as the original challenged asked for, first we notice that for a 10-digit number to be divisible by 10, it must end in 0.
So we just need to find 9-digits solutions, 0 excluded, then add a final 0 to all of them.
We just need a very few changes to the program above, like this 200+ byte version:
10 DESTROY ALL @ OPTION BASE 0 @ DELAY 0,0 @ STD
20 FOR I=1 TO 9 @ CALL TST((I),2,9) @ NEXT I @ DISP "DONE!" @ END
30 SUB TST(N,D,M) @ N=10*N @ FOR I=1 TO 9 @ X=N+I @ IF MOD(X,D) THEN 50
32 A$=STR$(X) @ FOR J=1 TO LEN(A$) @ IF POS(A$[J+1],A$[J,J]) THEN 50
34 NEXT J
40 DISP D;X @ IF D#M THEN CALL TST(X,D+1,M)
50 NEXT I @ END SUB
- As before, line 10 sets things up, but STD is even
more mandatory, for the STR$ conversion below.
- The loop at line 30 in the subprogram begins at 1 instead of 0, as 0 must be the final, 10th digit.
- Lines 32 and 34 simply check for repeated digits,
by converting the candidate number (which already meets
the divisibility requirement) to a string, then using the
POS function to find if any character occurs more than
once. It's a simple, non-optimal idea that works.
The rest of the program is just the same. When RUN, it
outputs:
2 12 -> 3 123 -> ... -> 9 381654729
and so, the one and only 10-digit solution is 3816547290.
That's all, hope you enjoyed it, and see how recursion
makes an easy job of apparently complex tasks.
|
Go back to the main exhibit hall