Hi all,
Thanks once more for your interest and for the excellent inputs and kind comments,
much appreciated. I must say that it's becoming increasingly difficult to come up
with a worthy challenge capable of resisting your combined efforts even for
a few days. I dread the day when my S&SMCs will be completely solved within a few
hours after posting ! This only goes to show the tremendous amount of programming
& math ingenuity displayed by this forum's gentle contributors.
That said, these are my original solutions to all three parts of S&SMC#17, plus
relevant comments:
Appetizer: More power to you
"Write a program to find the first exact power of 2 (up to 22500, say) that begins by a given
sequence of up to four digits"
First of all, it's fairly simple to prove that for any positive integer M there exists
an exact power of 2 that begins with the sequence of digits which represents the number M in the
decimal notation. Which is more, this is also true not only for 2 but for any positive integer A
other than an exact power of 10, so for example, you can find N such that
3141592654N begins with 2718281828, say.
Once we know that the feat is indeed possible for any given M, we can proceed to implement the
search, and this 3-liner (97 bytes) is my original solution for the HP-71B:
1 INPUT M @ X=FP(LGT(M)) @ Y=FP(LGT(M+1)) @ P=LGT(2) @ FOR I=1 TO 2500
2 N=FP(P*I) @ IF N>X AND N<Y THEN DISP I,STR$(10^N);"E";STR$(INT(P*I)) @ END
3 NEXT I
which will accept an integer M, then will find out and print the required exponent and
the corresponding power of 2 (which begins with M) in exponential notation, using decimal logarithms
throughout to keep the numbers within range. Upon running it for the given cases, we construct
the following table:
Beginning N 2^N
-----------------------------------------
1000 2136 1.00016289353E643
1234 1545 1.23407996301E465
1313 1183 1.31366573155E356
2006 682 2.00658260481E205
1776 2087 1.77664619863E628
and we also try out Kiyoshi Akima's suggestion:
1542 1542 1.54259995373E464
which is indeed rather nice, as the required exponent
equals the given beginning sequence,
namely
1542, so that we have:
21542 = 1542.59995373 * 10461
For the longer case, outputting the resulting power of 2 in full, it suffices to append
a routine to compute the exact value of 2
N using some multiprecision algorithm. I'll simply
use the one I already posted as part of my
"Spring Special Challenge" (aka "April's Fool Challenge"), where it was
used to efficiently compute 2
65536-3, and which is readily customizable
for an arbitrary power of 2. The resulting program is thus the following 426-byte quick concoction:
10 DESTROY ALL @ OPTION BASE 0 @ INPUT M
15 X=FP(LGT(M)) @ Y=FP(LGT(M+1)) @ P=LGT(2)
20 FOR I=1 TO 2500 @ N=FP(P*I) @ IF N>X AND N<Y THEN 30
25 NEXT I @ DISP "Not found" @ END
30 N=I @ PRINT N @ M=9 @ DIM A(1) @ K=10^M
35 A(0)=1 @ P=0 @ L=9 @ R=2^L @ FOR J=0 TO N-L STEP L @ MAT A=(R)*A @ GOSUB 65
40 IF NOT MOD(J,27) THEN DIM A(UBND(A,1)+1)
45 NEXT J @ R=MOD(N,L) @ IF R THEN MAT A=(2^R)*A @ GOSUB 65
50 J=0 @ PRINT @ PRINT STR$(A(P));
55 FOR I=P-1 TO 0 STEP -1 @ J=J+1 @ IF J=7 THEN PRINT @ J=0
60 A$=STR$(A(I)) @ PRINT RPT$("0",M-LEN(A$));A$; @ NEXT I @ END
65 FOR I=0 TO P @ A(I+1)=A(I+1)+A(I) DIV K @ A(I)=MOD(A(I),K) @ NEXT I
70 P=P+SGN(A(P+1)) @ RETURN
Let's try a couple of cases:
>RUN
? 2006
682
20065826040452474621738395244141115820123061381619162977212070
095324448220432589806036630768881181530864650607514107580997541
169167266097500334986765487216377087492641938951866881041556870
737904629872328704
which takes just 0.43 seconds in Emu71 (some 2 min. in an actual HP-71B).
Another interesting case is Kiyoshi Akima's 1542:
>RUN
? 1542
1542
154259995322946085669127462785812103226373967868524092887019
202500176473061875404842821441542870147178460721041976832306423
194686642877332798055231225009577693133653720424014385330052986
731615979318114760792820483686230134905894343005528775814368509
759860201045907243368286294738023515418354826493938295703703614
022990181884355470848740016540805157093622457663597753106142505
384395616964083511896011664672399807541625517182144801653972761
678911158848304661716271104
which takes only 1.64 seconds in Emu71 and some 8 min. in a real HP-71B.
Main course: Le petit homage to the 41 !
"Find a 41-digit number consisting solely of the digits 4,1 which can
be halved at least 41 times".
As stated, this is actually quite easy, because you can begin with just one digit (4), which is certainly
divisible by 21 and go on adding digits leftwards one at a time, chosing 1 or 4
so that the resulting number is divisible by 22, 23, etc.
This is almost trivial up to 10-12 digits (depending on your chosen calc model), for instance this
would be one of the simplest HP-71B implementations, valid for up to 12 digits:
1 DESTROY ALL @ U=4 @ V=1 @ N=U @ P=4 @ T=10
2 FOR K=2 TO 12 @ IF MOD(N,P) THEN N=N+T*V ELSE N=N+T*U
3 DISP K;N @ P=P*2 @ T=T*10 @ NEXT K
>RUN
2 44 (divisible by 22, "14" wouldn't be)
3 144 (divisible by 23, "444" wouldn't be)
4 4144
5 14144
6 414144
7 1414144
8 41414144
9 441414144
10 1441414144
11 11441414144
12 411441414144 (divisible by 212)
and afterwards, for more than 12 digits, you only need a multiprecision modulus operator,
which is rather easy to implement as can be seen in my following original 7-line solution for
the HP-71B, which is general because it will work not only for the (4,1) case but for all other
solvable cases as well, namely all pairs of digits which are of different parity (i.e.: one odd, the other even,
zero not included):
1 DESTROY ALL @ INPUT U,V @ D=U+1 @ DIM N(D),B(D) @ N(1)=U @ L=10^11
2 FOR K=2 TO 10*U+V @ W=1 @ MAT B=N @ FOR J=1 TO K @ FOR I=D TO 1 STEP -1
3 IF NOT MOD(B(I),2) THEN 4 ELSE IF I#1 THEN B(I-1)=B(I-1)+L ELSE 5
4 B(I)=B(I) DIV 2 @ NEXT I @ NEXT J @ W=0
5 C=(K-1) DIV 11+1 @ N(C)=N(C)+(V*W+U*NOT W)*10^MOD(K-1,11) @ NEXT K
6 DIM T$[11*D] @ FOR I=1 TO D @ S$=STR$(N(I))
7 T$=RPT$("0",11-LEN(S$))&S$&T$ @ NEXT I @ DISP LTRIM$(T$,"0")
Running it for all 20 possible cases, you'll get the following table:
Digits Number
--------------------------------------------------------------------------------------------------
2,1 112111211111212122112
2,3 23233333323323232223232
2,5 5255552222255222255255552
2,7 727727727272277772727222272
2,9 29229292922999929922222292992
4,1 44111111411444111411141441444411441414144
4,3 4334333333433343344344443443433343333433344
4,5 554445454544445545455455454544555545454444544
4,7 74744444477474477447474474777477444474444447744
4,9 4944949944994494999944449444499949499449494994944
6,1 1116116116116166111166666166166666666111616666661661616111616
6,3 663336366333366636336636363336363363366333336333633333636366336
6,5 66656565566565655566565665666666566656655655556556566656666566656
6,7 6677767667676666776766667777767666677766776777777777777666766667776
6,9 969669666696696696696996666999996996999999996669699999969969696669696
8,1 888811111811181118188118188188811181881818811811881181181818888181888888118181888
8,3 88333833333888383338883833838333388383333888883833338883388388888888888833383333888
8,5 5858588588585858858858558558588888588855588858585588588555858555888855585858558885888
8,7 878788788878877877788787778887877888877787887787878887878878877888887888788888787877888
8,9 99999989998899889889988898999988888898989889899889988989999888898888999898998898989989888
The solution for the (4,1) case is thus this 41-digit number, obtained after 4 min. in a
physical HP-71B (less than 1 second in Emu71):
44111111411444111411141441444411441414144
which indeed is the only 41-digit long number consisting solely of the digits (4,1), and which can be halved
at least 41 consecutive times (actually, 42!). Also, the correct solution for the digits (6,7) is:
6677767667676666776766667777767666677766776777777777777666766667776
which is 67-digits long, consisting of just the digits (6,7), and
can be halved at least 67 consecutive times. Running time is 15 min. in a real HP-71B (less than 4 seconds in Emu71).
By the way, before departing let's have a look at these nice 'cousins' of our number which I've generated for your viewing pleasure, also 41-digit long
and consisting solely of the digits (4,1):
44144444111441144114411411444444411441441 = 12009881291601907477 * 3675676972953081511133 (both prime)
41411111444114444411114141144414144444441 = is a prime
and these are two equally handsome 'cousins' I've generated for the 67-digit (6,7) number:
6777766776766667676667667777777667667776766667766766666767676677677
= 17512766212863416348551 * 387018629403519697077017550365961771489126827 (both prime)
6677776776776667776677667776667677766767676666766666766676767677677 = is a prime
Who knows, they might come handy to test your favorite factoring or primality test algorithms, or even
your multiprecision multiplication routines at the very least. Or, if you're in a little sadistic mood and
you've got some students the right age, have them multiply both factors by hand and keep betting whether
the next digit in the result is going to be a 6 or a 7 ! ... :-)
Le Dessert: Pi & other delights
"Write a program which, given an arbitrary value, will output the exact
order in which the terms of this particular series have to be summed up so that the series sums
to precisely that given value"
This is probably the easiest of the lot, and this 4-liner (147 bytes) is my original solution
for the HP-71B, which is anything but optimized (pessimized more like!) and will output up to
100 terms, then it will display both the given value and the sum after 100 terms:
1 DESTROY ALL @ INPUT E @ K=100 @ P=1 @ N=2 @ S=0 @ FOR I=1 TO K
2 T=2*P-1 @ S=S+1/T @ DISP T; @ P=P+2 @ IF S<E THEN 2
3 T=1-2*N @ S=S+1/T @ DISP T; @ N=N+2 @ IF S>E THEN 3
4 NEXT I @ DISP @ DISP E,S
Let's run it for a few cases:
>RUN
? PI/4
1 -3 5 -7 9 -11 13 -15 17 -19 21 -23 25 -27 29 -31 33 -35 37 -39 41 -43 45 -47 49
-51 53 -55 57 -59 61 -63 65 -67 69 -71 73 -75 77 -79 81 -83 85 -87 89 -91 93 -95 97 ...
.785398163398 .784148171212
>RUN
? PI/5
1 -3 -7 5 -11 -15 9 -19 13 -23 -27 17 -31 -35 21 -39 -43 25 -47 -51 29 -55 -59 33 -63
-67 37 -71 -75 41 -79 45 -83 -87 49 -91 -95 53 -99 -103 57 -107 -111 61 -115 -119 65 ...
.628318530718 .627954521532
>RUN
? EXP(1)/4
1 -3 5 -7 -11 9 -15 13 -19 -23 17 -27 -31 21 -35 25 -39 -43 29 -47 33 -51 -55 37 -59
41 -63 -67 45 -71 49 -75 -79 53 -83 57 -87 -91 61 -95 65 -99 -103 69 -107 73 -111 -115 ...
.679570457115 .678047886984
>RUN
? 1
1 -3 5 9 13 -7 17 21 -11 25 29 -15 33 37 41 -19 45 49 -23 53 57 61 -27 65 69
-31 73 77 -35 81 85 89 -39 93 97 -43 101 105 -47 109 113 117 -51 121 125 -55 129 ...
1 .998110828956
>RUN
? SIN(1)
1 -3 5 -7 9 13 -11 17 -15 21 -19 25 -23 29 33 -27 37 -31 41 -35 45 -39 49 53 -43
57 -47 61 -51 65 -55 69 73 -59 77 -63 81 -67 85 -71 89 93 -75 97 -79 101 -83 105 ...
.841470984808 .840058963385
>RUN
? COS(1)
1 -3 -7 5 -11 -15 -19 9 -23 -27 -31 13 -35 -39 17 -43 -47 -51 21 -55 -59 -63 25 -67 -71
29 -75 -79 -83 33 -87 -91 -95 37 -99 -103 41 -107 -111 -115 45 -119 -123 -127 49 -131 ...
.540302305868 .539956898016
>RUN
? 0
1 -3 -7 -11 -15 -19 -23 -27 -31 -35 -39 -43 -47 -51 -55 -59 -63 -67 -71 -75 5 -79 -83 -87 -91
-95 -99 -103 -107 -111 -115 -119 -123 -127 -131 -135 -139 -143 -147 -151 -155 -159 -163 9 -167 ...
0 -1.03546604552E-4
I think you get the idea: though we're adding up
each and every term of the series
once and only once, we can get
any result we want by simply
chosing their order in
the addition process, which is probably rather unexpected at first sight and nicely shows what
conditional convergence of alternating series actually means.
As for the 30-step HP-15C version, it was a direct translation of the
above 71B program and it doesn't bear being featured here as much better and shorter solutions
have already been provided by you.
That's all. I hope you enjoyed it all and, again, thanks for your interest and stay tuned for
S&SMC#18 coming next month.
Best regards from V.
Edited: 19 Sept 2006, 5:52 a.m.