[LONG] S&SMC #8: My original solutions, comments and curiosities !
Message #32 Posted by Valentin Albillo on 25 Apr 2005, 5:13 a.m.,
in response to message #1 by Valentin Albillo
Hi all,
Thanks to all of you interested in my S&SMC #8 and most specially to those who provided such ingenuous and elegant solutions for such a variety of HP calcs and computers, we really saw a lot of interesting techniques being used here for the one and only purpose: find the solutions and find them fast. Congratulations to all of you, I *really* feel most satisfied with your contributions !
As promised, this is my original, 4-line solution for the HP-71B:
10 C=0 @ FOR N=33334 TO 99999 @ M$=STR$(N*N) @ IF POS(M$,"0") THEN 40 ELSE T$=M$[1,1]
20 FOR I=2 TO 10 @ IF POS(T$,M$[I,I]) THEN 30 ELSE IF LEN(T$)=3 THEN 40 ELSE T$=T$&M$[I,I]
30 NEXT I @ C=C+1 @ DISP N;M$,T$
40 NEXT N @ DISP "OK:";C;"found"
Calling it produces the 48 solutions, displaying the number, its square, and the
distinct digits it consists of:
>CALL
33334 1111155556 156
33335 1111222225 125
33338 1111422244 142
33359 1112822881 128
33989 1155252121 152
34641 1199998881 198
...
81404 6626611216 621
81619 6661661161 61 <- only *two* different digits, the solution to the first part
81813 6693366969 693
83666 6999999556 695
86478 7478444484 748
97773 9559559529 952
98336 9669968896 968
OK: 48 found
It takes 3 min 28 sec when run under Emu71 in a 1.4 Ghz PC. The program searches all numbers which generate 10-digit squares fulfilling the conditions. As no 0's are allowed, the smaller possible square would be 1111111111, so we begin the search at SQR(1111111111) rounded to the nearest integer, which is 33334, and go on searching till SQR(9999999999), which comes out to 99999. We square each number in turn and convert the result to a string. The first POS then immediately discards numbers having a "0" anywhere. Then we keep on extracting individual digits which are added to an auxiliary string, using POS to detect repetitions (in which case we don't add the digit again) and LEN to see if there are more then 3 distinct digits already collected, in which case we forfeit further processing of this number and go instead to check the next candidate.
However, this is not the fastest way to proceed because the HP-71B is optimized for numerical computations and string processing is relatively slow. So I originally came out instead with this other version, which uses flags to register which digits have been used:
10 C=0 @ FOR N=33334 TO 99999 @ M=N*N @ CFLAG ALL @ P=0
20 FOR I=1 TO 10 @ D=MOD(M,10) @ IF NOT D THEN 50 ELSE M=M DIV 10
30 IF FLAG(D) THEN 40 ELSE IF P=3 THEN 50 ELSE SFLAG D @ P=P+1
40 NEXT I @ C=C+1 @ DISP N;N*N
50 NEXT N @ DISP "OK:";C;"found"
It works the same, only using flags instead of strings. Each candidate number is decomposed
into its constituent digits. If the digit is a 0, we skip to the next candidate, else a flag is set corresponding to the digit. If more than 3 flags have alrady been set, no further digits are isolated but we go instead to test the next candidate. This version finds the exact same solutions but it takes just 72 seconds (under Emu71), i.e., it's 3 times faster than the string version. A real HP-71B takes much longer of course, but it's a real beauty to see the display's flag indicators making a frantic dance while the program runs !
In both versions, changing the "3" to any other single digit N (1-9) would find squares made up of N distinct digits. For instance, with N=2, it produces 6661661161, the only 10-digit square consisting of just two different digits, 1 and 6 in this case. Also, you can search for 12-digit squares instead, say, by simply changing the search limits to 333334 and 999999 respectively, and by changing the limit of the I loop to 12. This can be automated by simply creating a new, generalized version that asks the user for the number of digits and maximum different values, like this:
1 INPUT "# Digits (1-12) = ";U @ INPUT "# Diff. val. (1-9) = ";V
10 C=0 @ FOR N=INT(SQR((10^U-1)/9)) TO INT(SQR(10^U-1)) @ M=N*N @ CFLAG ALL
20 P=0 @ FOR I=1 TO U @ D=MOD(M,10) @ IF NOT D THEN 50 ELSE M=M DIV 10
30 IF FLAG(D) THEN 40 ELSE IF P=V THEN 50 ELSE SFLAG D @ P=P+1
40 NEXT I @ C=C+1 @ DISP N;N*N
50 NEXT N @ DISP "OK:";C;"found"
Let's try it ! To find the five 5-digit squares consisting of at most 2 different values:
>RUN
# Digits (1-12) = 5 [ENTER]
# Diff. val. (1-9) = 2 [ENTER]
109 11881
173 29929
212 44944
235 55225
264 69696
OK: 5 found
While to find the thirty 12-digit squares consisting of at most 3 different values:
>RUN
# Digits (1-12) = 12 [ENTER]
# Diff. val. (1-9) = 3 [ENTER]
333334 111111555556
333335 111112222225
333338 111114222244
333359 111128222881
333858 111461164164
363639 132233322321
387288 149991994944
461761 213223221121
492162 242223434244
505525 255555525625
515415 265652622225
586893 344443393449
649788 422224444944
658357 433433939449
664388 441411414544
665908 443433464464
666515 444242245225
666665 444442222225
666667 444444888889
666668 444446222224
682908 466363336464
782104 611686666816
805262 648446888644
818333 669668898889
828667 686688996889
834386 696199996996
869924 756767765776
939938 883483443844
974417 949488489889
994836 989698666896
OK: 30 found
The 'flags' version also has the added advantage that it translates very easily to RPN machines with little or no alpha capabilities, such as the HP-41C or HP-15C. For instance, here's the translated version for an HP-41CX, a meager 46 steps:
01 *LBL "SQ3" 16 STO 04 31 GTO 04
02 CLX 17 10 32 *LBL 05
03 X<>F 18 STO 05 33 1
04 CF 08 19 *LBL 01 34 ST+ 02
05 CF 09 20 RCL 03 35 1E5
06 RCLFLAG 21 INT 36 RCL 02
07 STO 01 22 10 37 X#Y?
08 33334 23 ST/ 03 38 GTO 00
09 STO 02 24 MOD 39 STOP
10 *LBL 00 25 X=0? 40 *LBL 04
11 X^2 26 GTO 05 41 DSE 05
12 STO 03 27 FS? IND X 42 GTO 01
13 RCL 01 28 GTO 04 43 RCL 02
14 STOFLAG 29 SF IND X 44 X^2
15 .003 30 ISG 04 45 VIEW X
46 GTO 05
It runs under the V41 emulator in 72 min (a real HP-41CX would take a lot longer) to produce all 48 solutions, and again, it's a joy to see all those flag indicators frantically turning on and off:
[R/S]
1111155556
1111222225
...
9559559529
9669968896
For practical reasons and in order to to make it accessible to most HP calculators, this challenge specifically addressed 10-digit squares, but if you feel like it there are marvels out there waiting to be discovered, here are some examples:
10099510939154979751^2 = 102000121210111101102120011101220022001 (39 digits, all 0,1,2)
557963558954625926861^2 = 311323333121312322332133323111223321313321 (42 digits, all 1,2,3)
675754811056988742949784^2 = 456644564666666555445565455644644555565545646656 (48 digits, all 4,5,6)
Actually, even the 48-item list of solutions for the original challenge holds a number of very interesting results upon close inspection, such as these beautifully-patterned squares:
1111155556 ( 11111-5555-6 )
1111222225 ( 1111-22222-5 )
1616361616 ( 16-16-36-16-16 )
2929299129 ( 29-29-29-91-29 )
4444222225 ( 4444-22222-5 )
4444488889 ( 44444-8888-9 )
5252625625 ( 52-52-625-625 )
6617171716 ( 66-17-17-17-16 )
Thanks for your interest in this humble S&SMC #8, hope you enjoyed it, and
Best regards from V.
|
Go back to the main exhibit hall