S&SMC #9, Act II - Solution and RPL Programming Challenge Message #6 Posted by J-F Garnier on 29 May 2005, 3:03 p.m., in response to message #1 by J-F Garnier
Below is my solution. First, I noticed that to be divisible by 25, a number should end with 00,25,50 or 75 so it is enough to find all the 24-digit solutions. This means that double length arithmeric can be used on Saturn (and Capricorn...) machines (2*12 digits), with only the implementation of MOD, *10 and div10 operations, which is quite easy to do.
10 ! S&SMC #9, Act II
20 ! JFG, May 2005
30 H=24 ! # of digits (24 max)
40 C=0 ! solution counter
50 FOR I=10 TO 98 STEP 2 ! loop for 1st and 2nd digit positions
60 L=3 ! start tests from 3rd position
70 M=I*10 ! lower part of candidate number
80 N=0 ! higher part
90 'A': X=MOD(N*1.E+12,L)+MOD(M,L) @ IF X>=L THEN X=X-L ! x= [n,m] mod L
100 IF X<>0 THEN X=L-X ! find Lth digit
110 IF X>9 THEN 'D' ! is it a possible candidate?
120 M=M+X ! yes, built it.
130 IF L=H THEN C=C+1 @ DISP N;M @ GOTO 'C' ! found one!
140 'B': N=N*10+M DIV 100000000000 @ M=MOD(M,100000000000)*10 ! go on [n,m]*=10
150 L=L+1 @ GOTO 'A'
160 'C': X=X+L @ IF X<=9 THEN M=M+L @ GOTO 'B' ! next try, if possible
170 'D': M=MOD(N,10)*100000000000+M DIV 10 @ N=N DIV 10 ! else [n,m]/=10
180 X=MOD(M,10)
190 L=L-1 @ IF L>2 THEN 'C'
200 NEXT I
The only three 24-digit solutions are:
144408645048 225636603816
360852885036 840078603672
402852168072 900828009216
So the unique 25-digit solution is: 3608528850368400786036725.
You can notice that I used a few GOTOs and 4 labels. Actually, I'm a supporter of structured programming style with WHILE/LOOP/REPEAT/etc structures (such as in the HP71 JPCROM), so it can be a challenge to rewrite the program with no explicit GOTO.
Will someone implement this simple but non-trivial algorithm on HP48's RPL for instance?
J-F
|