S&SMC#16: My Original Solutions & Comments
Message #24 Posted by Valentin Albillo on 19 May 2006, 6:43 a.m.,
in response to message #1 by Valentin Albillo
Hi all,
As always, thanks to all of you who were interested in my S&SMC#16, most
specially to the ones who took their time to analyze and eventually solve it.
As promised, I'm posting now my original solutions plus relevant comments:
Scroll 1: Being yourself ...
"Write a program that finds out all 10-digit integers (base 10, of course) that upon being
squared, the result's rightmost digits exactly reproduce the original number"
These are well-known numbers, usually called automorphs. In a sense, they can
be considered additional roots to the equation:
x2 = x
if we're willing to accept 'infinite' numbers as solutions. For all numeric bases,
there are always two solutions, namely 0 and 1. For N-base
numbers where N is either prime or the power of a prime, these are the
only solutions. On the other hand, when N=10, we also have
two other solutions, namely:
... 8212890625 and ... 1787109376
which can be extended infinitely. In all numeric bases, their sum is always of
the form 11, 101, 1001, 10001, 1000000000...0000000001, etc, so it suffices
to compute just one of them and the other can be immediately written down with
a trivial computation. As Thomas Okken and Bram demonstrated, a little
theoretical work can do wonders to help implement a simple, concise algorithm,
and in particular, to stablish that 5 and 6 are the only possible 1-digit solutions in base 10
(disregarding the trivial solutions 0 and 1, which can't be extended with non-zero
digits), and they can be extended indefinitely a digit at a time. Which is more, only the
"5" solution needs to be extended, the "6" solution is computed immediately from it.
This is my original 4-line (101-byte) version for the HP-71B:
1 N=5 @ FOR K=2 TO 10 @ P=10^K @ R=P/10 @ FOR D=0 TO 9
2 M=R*D+N @ IF NOT MOD(M*M-M,P) THEN 4
3 NEXT D
4 N=M @ NEXT K @ DISP M;10000000001-M
Running it produces:
>RUN
8212890625 1787109376
in negligible time. This works Ok thanks to the extreme high-quality nature of HP's
arithmetic routines, as implemented in the HP-71B and most other HP calc models, which allows for proper
computation of MOD even
when you would fear that lost digits beyond 12-digit precision in the
computation of M2 would lead to inaccurate results. That's
not so and the above program works fine in the HP-71B.
It might *not*
if converted to other less accurate, non-HP models.
The solutions are indeed correct, as we have:
82128906252 = 67451572418212890625
17871093762 = 3193759921787109376
We also have the following interesting results:
8212890625 + 1787109376 = 10000000001
8212890625 * 1787109376 = 14677333840000000000
8212890625 * (8212890625-1) = 67451572410000000000
1787109376 * (1787109376-1) = 3193759920000000000
(1787109376-1)2 = 3193759918212890625
(8212890625-1)2 = 67451572401787109376
The equivalent RPN version for the HP-15C is this short, fast 44-step routine:
01 *LBL A 14 10 27 ENTER 37 PSE
02 6 16 / 28 X^2 38 STO 0
03 STO 0 17 STO 3 29 LASTX 39 ISG 1
04 2.01 18 .09 30 - 40 GTO 1
08 STO 1 21 STO I 31 RCL/ 2 41 1
09*LBL 1 22*LBL 0 32 FRAC 42 RCL 0
10 RCL 1 23 RCL I 33 ISG I 43 RCL- 2
11 INT 24 INT 34 TEST 0 44 -
12 10^X 25 RCL* 3 35 GTO 0
13 STO 2 26 RCL+ 0 36 X<>Y
which is essentially a direct translation of the above, which the
added nice touch that it will pause to let you see each correct digit as it's being added. Let's run it:
GSB A -> (76) -> (376) -> ...
-> 8212890625
X<>Y -> 1787109376
which only takes 85 seconds to run, including 9 one-second pauses.
Amazingly this program also works, despite the fact the HP-15C is
limited to 10-digit results, not 12-digit as in the HP-71B !.
This
would seem to be a fatal pitfall when having to deal with the square
of 10-digit integers, which comes out to 19/20-digit results,
but thanks again to the utterly incredible quality of
HP's arithmetic routines as implemented in the HP-15C, the above
program does run fine, against all odds, and directly computes the
correct "6" solution, which is immediately used to get the "5" solution
without further computation.
Again, it would very likely fail if converted to non-HP 10-digit models.
Scroll 2: ... Big Time !
"Write a program to find and orderly output all solutions with the same requirements
as above, but this time for 100-digit integers"
My original solution is this short, 635-byte program for the HP-71B:
100 DESTROY ALL @ DIM M$[128],N$[128],P$[256] @ M$="5"
110 FOR I=2 TO 100 @ CALL MS(M$,P$) @ M$=REV$(P$)[I,I]&M$ @ NEXT I
120 GOSUB 140 @ DISP @ M$[100]="6"
130 FOR I=1 TO 99 @ M$[I,I]=STR$(9-VAL(M$[I,I])) @ NEXT I @ GOSUB 140 @ END
140 FOR I=1 TO 5 @ DISP M$[20*I-19,20*I] @ NEXT I @ RETURN
150 !
160 SUB MS(P$,R$) @ OPTION BASE 1 @ DIM A$[512],E$[512] @ A$=FNL$(P$)
170 X=LEN(A$) DIV 6 @ Z=2*X @ U=10^6 @ V=U-1 @ DIM A(X),C(Z),C$[Z*6]
180 FOR I=1 TO X @ A(X+1-I)=VAL(A$[I*6-5,I*6]) @ NEXT I
190 FOR I=1 TO X @ M=A(I) @ IF RES THEN L=I ELSE 230
200 FOR J=1 TO X @ N=A(J) @ IF RES THEN P=M*N @ C(L)=C(L)+RES ELSE 220
210 P=RES @ IF RES>V THEN C(L)=RMD(P,U) @ C(L+1)=C(L+1)+P DIV U
220 L=L+1 @ NEXT J
230 NEXT I @ FOR I=Z TO 1 STEP -1 @ IF C(I) THEN 250
240 NEXT I
250 C$=STR$(C(I))
260 FOR I=I-1 TO 1 STEP -1 @ C$=C$&FNL$(STR$(C(I))) @ NEXT I @ R$=C$
270 DEF FNL$[512](A$) @ E$=A$
280 IF RMD(LEN(E$),6) THEN E$="0"&E$ @ GOTO 280 ELSE FNL$=E$
where the main program is a mere 5 lines long, and simply calls subprogram MS
to compute the multiprecision square of a multiprecision integer. MS is
a very simple subprogram which takes two string arguments, namely:
P$ contains the multiprecision number to square, as a string
R$ contains the multiprecision result
Having the number and result be strings is much less efficient and
more memory-wasting than using arrays, but it makes for easy use right from
the keyboard and I happened to have at hand this little subprogram I wrote
long ago. Tha main program simply uses it to compute the "6" solution, and
then outputs both the 100-digit "6" solution and "5" solution in 20-digit groups:
>RUN
39530073191081698029
38509890062166509580
86381100055742342323
08961090041066199773
92256259918212890625
60469926808918301970
61490109937833490419
13618899944257657676
91038909958933800226
07743740081787109376
These results are indeed correct, as we do have:
39530073191081698029385098900621665095808638110005574234232308961090041066199773922562599182128906252
=
1562626686492275980643313531100701521758660998626415856673412452830198131380176443023792967609238890
3953007319108169802938509890062166509580863811000557423423230896109004106619977392256259918212890625
and
60469926808918301970614901099378334904191361889994425765767691038909958933800226077437400817871093762
=
3656612048275936374766293750976368502596933376625301009826950660612189918140221658511273131183457641
6046992680891830197061490109937833490419136188999442576576769103890995893380022607743740081787109376
By the way, this program is general in nature so you can use it to compute more or less than 100 digits by simply changing some constants here and there. Also, as stated, you can use subprogram MS from the keyboard to square large integer numbers, like this:
>M$="3147926784726726563780030042374237187751" @ CALL MS(M$,P$) @ P$
9909443041999946686063013207932562462851613614976494122324802303779777224438001
Scroll 3: All included
"Write a program to find and output all pairs of 5-digit integers such that together
they do include all digits from 0 to 9 and each of their respective 10-digit squares also
include all digits from 0 to 9 as well"
This is my original 13-line, 393-byte program for the HP-71B:
10 DESTROY ALL @ DIM S(50) @ A$="1234567890" @ L=0 @ FOR A=3 TO 9
20 T=10000*A @ FOR B=0 TO 9 @ IF B=A THEN 100
30 U=T+1000*B @ FOR C=0 TO 9 @ IF C=A OR C=B THEN 90
40 V=U+100*C @ FOR D=0 TO 9 @ IF D=A OR D=B OR D=C THEN 80
50 W=V+10*D @ FOR E=0 TO 9 @ IF E=A OR E=B OR E=C OR E=D THEN 70
60 N=W+E @ IF NOT SPAN(A$,STR$(N*N)) THEN L=L+1 @ S(L)=N @ DISP N;N*N
70 NEXT E
80 NEXT D
90 NEXT C
100 NEXT B @ NEXT A @ DISP "Checking matching pairs ..."
110 FOR I=1 TO L @ A=S(I) @ FOR J=I+1 TO L @ B=S(J)
120 IF NOT SPAN(A$,STR$(A)&STR$(B)) THEN DISP A;B,A*A;B*B
130 NEXT J @ NEXT I @ DISP "OK"
Upon running, it first does find out all 5-digit (nonrepeated) numbers
whose 10-digit squares feature all digits from 0 to 9, then automatically
matches them in pairs to quickly produce all four solutions, namely:
>RUN
35172 1237069584
37905 1436789025
39147 1532487609
43902 1927385604
46587 2170348569
53976 2913408576
54918 3015986724
57321 3285697041
58413 3412078569
59403 3528716409
60984 3719048256
63051 3975428601
63129 3985270641
69513 4832057169
76182 5803697124
78453 6154873209
80361 6457890321
81945 6714983025
85743 7351862049
86073 7408561329
87639 7680594321
89145 7946831025
89523 8014367529
90153 8127563409
91248 8326197504
91605 8391476025
96702 9351276804
Checking matching pairs ...
35172 60984 1237069584 3719048256
57321 60984 3285697041 3719048256
58413 96702 3412078569 9351276804
59403 76182 3528716409 5803697124
OK
This runs in less than 9 seconds in Emu71 @ 2.4 Ghz, and less
than 25 minutes in a real HP-71B.
The algorithm used is pretty straightforward: 5 nested loops
generate all 5-digit numbers from 30000 to 99999, in an optimized
way to minimize computation, and sieving out those having repeated
digits. The ones which remain after the sieving process are then
squared and their squares are checked to see if they feature all
digits from 0 to 9. The ones which pass muster are then collected
in an array, later to be matched to select compatible pairs that
together include all digits as well, which are suitably output
with their respective squares for added visual confirmation.
Note:
You might be interested to see how a 10-digit number is checked to
see if it includes all digits from 0 to 9. This is done in two
separate occasions at lines 60 and 120. Instinctively, one would
resort to using a loop to do the check, but it's far better to use
the SPAN function as shown, thus completely avoiding both loops
within the maximum nesting level, and so speeding up the program
a real lot.
The SPAN function is a little-known, little-used string function which
can be found in a number of different LEX files for the HP-71B,
though it was originally featured in STRNGLEX, which is a very common LEX,
included in a number of ROMs and thus easily available. In particular. it
comes already installed and ready to use in Emu71.
If you don't have Emu71 or STRNGLEX, you can substitute it for a simple
loop, using POS instead, but it's good to know about non-obvious, time-saving
uses for such functions as SPAN. By the way, the program can still be
optimized even further by noticing that once you have generated a
5-digit number N which doesn't have repeated digits (say 34567), then
another suitable candidate is 99999-N (99999-34567 = 65432) which is
automatically guaranteed to also have no repeated digits as well. This
can reduce the outer loop (and running time) by almost 50%. I'll leave that as an "exercise for the reader" :-)
Well, that's all for now. Hope you enjoyed it and thanks again to the
kind contributors, your postings were as keen as usual and certainly
enlightening to all interested readers. See you in S&SSMC#17, coming next month.
Best regards from V.
Edited: 19 May 2006, 7:11 a.m.
|
Go back to the main exhibit hall