What is the smallest power that 2 must be raised to so that the resulting string of digits contains all numbers 00 through 99?
I worked on a Mathematica program to figure this out all day today. As some of you know, that is not an easy system to program. But I finally got the answer.
Any takers?
Perl and Math::BigInt to the rescue. The number is the 975th power of two:
31933444952555516986501963408589417057079220166967320664040755878
99539026990342505255932744788217121742947914950707992390355900781
429749857182674877255730272512009076721737082428060354310980779492
24537079127027838932929672819339262222216842951687065201139345100
120966662777359236855041588461568
My progam took 1.117 seconds on my T40 laptop (1.6 GHz Centrino) and that's printing out the exponents as I go. I first searched for the minimal length string that included all one hundred two digit strings from '00' to '99'. I constructed a 110 digit string by contcatenating the symbols to the growing string if and only if they did not already appear in the string. Both ascending and descending ordering yielded a 110 digit string. I assumed that this was the optimal packing of the symbols. To get a minimum valued version, I ordered the digit symbols so that '00' to '09 appeared after '10' to '19' That way I eliminated strings with leading zeros. I then used Math::BigInt to search for the smallest power of two above this value. 2^363 fit this critereon. I then just did a brute force search like so:
my $exponent = Math::BigInt->new("363");
my $gotit=0;
while (!$gotit){
print $exponent->bstr(),"\n";
my $power = $two->copy->bpow($exponent);
my $candidate=$power->bstr();
my $couldbe=1;
while ($couldbe){
foreach (@nums){
if ($candidate !~/$_/){
$couldbe=0;
last;
}
}
if ($couldbe){
print "We have a winner!\n$candidate\n",$exponent->bstr(),"\n";
exit;
}
}
$exponent->binc();
}
"@nums" contains the two character symbols.
Regards,
Howard
Hi Don, maybe you should've tried a calculator first? ;-)
I have it (I think).
Anyway, my program for finding it is "brute force" and not
"optimized". Obviously, it wouldn't be a very small power of 2,
but I figured that they'd fail my program's test pretty quickly
anyway, and I was feeling too lazy to figure out where to start,
so I simply started with 21. My program takes about
235 seconds on a 49g+ with ROM 2.09, and about 509 seconds on a
49G with ROM 2.09.
The PUSH and POP commands are simply for saving the flags before forcing 2 FIX and
restoring them when finished; I'm not sure which ROM revision was the first to
have them. For earlier ROMs, one could use RCLF and STOF instead,
or simply let the program leave the calculator in 2 FIX mode.
Anyway, here's my program, including more comments than anyone
should need.
%%HP: T(3)F(.);Unless I've overlooked something, the power of 2 is 975.
@ For any 49 series with PUSH and POP commands.
@ Download or edit in exact mode.
@ Checksum: FC14h
@ Size: 202.
\<< @ Begin program.
PUSH @ Save flags.
2. FIX @ Force display mode.
0 0. \-> p s @ Bind local variables.
\<< @ Begin defining procedure.
DO @ Start generating powers of 2.
2 'p' INCR ^ @ Power of 2.
\->STR @ Convert to string.
0. .99 @ Generate strings "00" through "99"
FOR n @ Begin loop.
DUP @ Copy of power of 2 string.
n @ 0.00 through 0.99.
\->STR @ Convert to string.
3. 4. SUB @ "00" through "99".
IF @ Begin test.
POS @ Substring?
THEN @ Passes test.
1. 's' STO @ Set success signal.
ELSE @ Fails test.
0. 's' STO @ Clear success signal.
1. 'n' STO @ Exit FOR loop.
END @ End test.
.01 @ Step size.
STEP @ End of FOR loop.
DROP @ Drop the string.
UNTIL @ Next power of 2?
s @ Success signal
END @ Stop generating powers of 2.
p @ Power.
\>> @ Finish defining procedure.
POP @ Restore flags.
\>> @ Finish program.
31933444952555516986501963408589417057079220166967
32066404075587899539026990342505255932744788217121
74294791495070799239035590078142974985718267487725
57302725120090767217370824280603543109807794922453
70791270278389329296728193392622222168429516870652
01139345100120966662777359236855041588461568
Regards,
James
Edited: 8 Oct 2006, 8:07 a.m.
By the way, is there any particular reason for wanting to find this?
Regards,
James
PS:
Okay, a somewhat optimized version. This is almost 30% smaller,
almost 5% faster on my 49g+, and about 8% faster on my 49G. But
it's still brute force and starts checking from 21.
It runs in about 224 seconds on my 49g+, and about 466 seconds on
my 49G.
%%HP: T(3)F(.);
@ For any 49 series with POP and PUSH commands.
@ Download or edit in exact mode.
@ Checksum: 180Ah
@ Size: 143.
\<< @ Begin program.
PUSH @ Save flags.
2. FIX @ Force display mode.
2 0 @ Start with 2 and 0.
DO @ Start generating powers of 2.
1 + @ Increment power.
DUP2 @ Make copies.
^ @ Raise 2 to power.
\->STR @ Convert to string.
1. @ Signal to stop DO loop.
0. .99 @ Generate strings "00" through "99"
FOR n @ Begin loop.
OVER @ Copy of power of 2 string.
n @ 0.00 through 0.99.
\->STR @ Convert to string.
3. 4. SUB @ "00" through "99".
IF @ Prepare for test
POS NOT @ Not substring?
THEN @ Keep looking.
NOT @ Change signal to continue DO loop.
1. 'n' STO @ Exit FOR loop.
END @ Finish test.
.01 @ Step size.
STEP @ End loop.
NIP @ Discard the string.
UNTIL @ Next power of 2?
END @ Success!
NIP @ Discard the 2.
POP @ Restore flags.
\>> @ Finish program.
For a slower and larger version that displays the power that's
being checked and which digit pair is to be searched for, you
could try:
%%HP: T(3)F(.);
@ For any 49 series with POP and PUSH commands.
@ Download or edit in exact mode.
@ Checksum: 2574h
@ Size: 160.5
\<< @ Begin program.
PUSH @ Save flags.
CLLCD @ Clear display.
2. FIX @ Force display mode.
2 0 @ Start with 2 and 0.
DO @ Start generating powers of 2.
1 + @ Increment power.
DUP 1. DISP @ Display power.
DUP2 @ Make copies.
^ @ Raise 2 to power.
\->STR @ Convert to string.
1. @ Signal to stop DO loop.
0. .99 @ Generate strings "00" through "99"
FOR n @ Begin loop.
OVER @ Copy of power of 2 string.
n @ 0.00 through 0.99.
\->STR @ Convert to string.
3. 4. SUB @ "00" through "99".
DUP 2. DISP @ Display substring.
IF @ Prepare for test
POS NOT @ Not substring?
THEN @ Keep looking.
NOT @ Change signal to continue DO loop.
1. 'n' STO @ Exit FOR loop.
END @ Finish test.
.01 @ Step size.
STEP @ End loop.
NIP @ Discard the string.
UNTIL @ Next power of 2?
END @ Success!
NIP @ Discard the 2.
POP @ Restore flags.
\>> @ Finish program.
If you want to slow it down enough to clearly see the digits
change in the above, you could insert something like .2 WAIT
somewhere within the FOR...STEP loop.
Regards,
James
Edited: 8 Oct 2006, 8:10 a.m.
Thanks James and Howard. Boy, you guys are good!
Well, I thought about doing it on my 49g+, but I'm not a big fan of RPL (I'm a minimalist, so I gravitate toward RPN). I also considered my TI89 Titanium, but I knew that Mathematica would be the fastest solution, although it is certainly not programmer-friendly. Here is what I came up with:
found = False;
p = 100;
While [found != True,
x = ToString[2^p];
a = Table[0, {100}];
sl = StringLength[x];
Do[
a[[ToExpression[StringTake[x, {i, i + 1}]] + 1]] = 1;
, {i, 1, sl - 1}];
If[Plus @@ a == 100, Print [p, " ", "gotit"];
found = True];
p = p + 1;
]
Print ["Complete"]
I had no idea of the answer before I ran it, and when I saw that the magic number was 975, I thought wow, that's the sum of the digits of the first odd abundant number (I believe), 945. My (unattainable) goal is to find an odd perfect number, but for now I'll settle for smaller victories.
No real reason for finding this other than "I was just wondering," which is reason enough.
Thanks for your efforts, you guys are great.
I guess a simple way to speed the program up would be to start at a later power of 2. Since it seems like the numbers are 00, 01, 02, ..., 99, the number should have 200 digits, minimum. But if the first number was 00, and the next was 01, it would have only 197 digits.
And 197/0.30103 = 654.4
So, you could start searching at 2^655.
Since the final answer is only 975, starting with 655 should get the answer in only about a third of the time.
Actually, couldn't the number have less than 200 digits, because if it was 12345, that would account for 12, 23, 34, and 45? An interesting question would be how few digits could the number have and still yield 00 to 99.
See my entry above. I estimated a lower bound on the number by composing a 110 digit string that contained all 100 two digit pairs. I couldn't prove this was the optimal packing of the symbols, but I believe that it it was. :
my @nums;
foreach my $i (1,0,2..9){
foreach my $j (0..9){
push @nums,"$i$j";
}
}my $digits = "";
foreach (@nums){
if ($digits !~ /$_/){
$digits .= $_;
}
}print $digits,"\n",length($digits),"\n
I arranged the digits as shown to avoind numbers with leading "0" characters.
The output of the above code is:
1011121314151617181900020304050607080922232425262728293334353637
3839444546474849555657585966676869777879888991
110
I then found the lowest power of two greater than the above number, which was 2363.
my $lowerbound = Math::BigInt->new($digits);my $two = Math::BigInt->new("2");
my $exponent = Math::BigInt->new("1");while (1){
my $power = $two->copy->bpow($exponent);
if ($power->bcmp($lowerbound) > 0){
print $power->bstr(),"\n",$exponent->bstr(),"\n";
exit;
}
$exponent->binc();}
Which produced:
1878834066219066582311584477431469621900546039126655896565832777
2257672200916867547709591987078149624255479808
363
That eliminated about a third of the trials in the brute force approach. As it turns out, it didn't make much difference. Doing all powers of two took about 1.47 seconds, while the shorter list took 1.17.
Regards,
Howard
Edited: 8 Oct 2006, 1:49 p.m.
Quote:Yes. I'm assuming that a digit can be shared by two digit pairs.
Actually, couldn't the number have less than 200 digits, because if it was 12345, that would account for 12, 23, 34, and 45? An interesting question would be how few digits could the number have and still yield 00 to 99.
It seems to me that each digit 1 through 10 would have to occur at
least 10 times, so at the least 100 digits, maybe more.
My initial program to generate a string that contains all substrings "00"
through "99":
%%HP: T(3);That returns this 110-digit string:
@ For any 49 series.
@ Download or edit in exact mode.
@ Checksum: 7266h
@ Size: 112.
\<< "" 0 9
FOR m
"0" m +
DUP2
IF
POS
THEN
DROP
ELSE
+
END
NEXT
10 99
FOR n
n \->STR
DUP2
IF
POS
THEN
DROP
ELSE
+
END
NEXT
\>>
"0001020304050607080911121314151617181922232425262728293
3343536373839444546474849555657585966676869777879888990"
(break added to avoid scrolling)
But it looks like if we want to allow a digit to be shared by two
digit pairs, then any substring of 3 identical digits can be
replaced by a substring of 2 of the same identical digits. So,
with the above string as an argument, run this next program:
%%HP: T(3);That returns this 101-digit string:
@ For any 49 series.
@ Download or edit in exact mode.
@ Checksum: 24F0h
@ Size: 63.5
\<<
0 9
FOR n
"" n + n +
DUP n +
SWAP
SREPL
DROP
NEXT
\>>
"001020304050607080911213141516171819223242526272829
33435363738394454647484955657585966768697787988990"
(break added to avoid scrolling)
But is that the shortest possible? Let's check whether each digit
pair occurs exactly once, using that last string as an argument:
%%HP: T(3)F(.);Well, that runs through without failing, so evidently that
@ For any 49 series.
@ Download or edit in exact mode.
@ Checksum: 8E1Bh
@ Size: 112.
\<<
PUSH
2. FIX
0. .99
FOR n
n \->STR
3. 4. SUB
DUP
SREPL
IF
1. \=/
THEN
"FAIL"
1. 'n' STO
END
NEXT
POP
\>>
But is there some permutation of the 100-digit string
"01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789"
(break added to avoid scrolling)
which contains each of the digit pairs 00 through 99 exactly once?
I don't know.
Regards,
James
Edited: 8 Oct 2006, 3:29 p.m.
Quote:First, your estimate of at least 197 digits to possibly contain
I guess a simple way to speed the program up would be to start at
a later power of 2. Since it seems like the numbers are 00, 01,
02, ..., 99, the number should have 200 digits, minimum. But if
the first number was 00, and the next was 01, it would have only
197 digits.And 197/0.30103 = 654.4
So, you could start searching at 2^655.
Since the final answer is only 975, starting with 655 should get
the answer in only about a third of the time.
Starting out, except that the solution wouldn't be a very low
power of 2, I really didn't have the foggiest notion of what the
solution would be, or even whether the power of 2 would be small
enough for a 49 series to handle, and as for the size of the
string, I surmised at that it must be at least 100 digits, but
didn't take the time to guess a better starting point because I
didn't think that it would save all that much execution time.
In my program, for each power of 2, it stopped testing it after
the first digit pair that wasn't found. So, for examples, in
strings like "2", "4", "8", "16", and "32", testing for "00" as a
substring failed, so substrings "01" through "99" weren't even
tried. If I recall correctly, the substring "00" doesn't even
occur until it gets to 253. Of course, even when
"00" was found, if "01" wasn't found, then "02" through "99"
weren't searched for in that power of 2, and so on. So, typically,
smaller values took less time to check.
But let's try it starting with 2655 as you suggest:
%%HP: T(3)F(.);That took about 136 seconds on my 49g+, compared to about 224
@ For any 49 series with PUSH and POP commands.
@ Download or edit in exact mode.
@ Checksum: 1DB9h
@ Size: 147.5
\<< @ Begin program.
PUSH @ Save flags.
2. FIX @ Force display mode.
2 654 @ Start with 2 and 654.
DO @ Start generating powers of 2.
1 + @ Increment power.
DUP2 @ Make copies.
^ @ Raise 2 to power.
\->STR @ Convert to string.
1. @ Signal to stop DO loop.
0. .99 @ Generate strings "00" through "99"
FOR n @ Begin loop.
OVER @ Copy of power of 2 string.
n @ 0.00 through 0.99.
\->STR @ Convert to string.
3. 4. SUB @ "00" through "99".
IF @ Prepare for test
POS NOT @ Not substring?
THEN @ Keep looking.
NOT @ Change signal to continue DO loop.
1. 'n' STO @ Exit FOR loop.
END @ Finish test.
.01 @ Step size.
STEP @ End loop.
NIP @ Discard the string.
UNTIL @ Next power of 2?
END @ Success!
NIP @ Discard the 2.
POP @ Restore flags.
\>> @ Finish program.
Here's a program that does't start checking for substrings until
the power of 2 is over 99 digits long:
%%HP: T(3)F(.);That runs in about 215 seconds on my 49g+, or about 446 seconds on
@ For any 49 series with PUSH and POP commands.
@ Download or edit in exact mode.
@ Checksum: D42Dh
@ Size: 176.
\<< @ Begin program.
PUSH @ Save flags.
2. FIX @ Force display mode.
2 0 @ Start with 2 and 0.
@ First find power that result in at least 99 digits.
DO @ Start generating powers of 2.
1 + @ Increment power.
DUP2 @ Make copies.
^ @ Raise 2 to power.
SIZE @ Number of digits.
UNTIL
99. > @ At least 100 digits?
END
@ Now check each power of 2 for digit pairs.
DO @ Continue generating powers of 2.
1 + @ Increment power.
DUP2 @ Make copies.
^ @ Raise 2 to power.
\->STR @ Convert power of 2 to string.
1. @ Signal don't repeat DO loop.
0. .99 @ Generate strings "00" through "9
FOR n @ Begin loop.
OVER @ Copy of power of 2 string.
n @ 0.00 through 0.99.
\->STR @ Convert to string.
3. 4. SUB @ "00" through "99".
IF @ Prepare for inner test.
POS NOT @ Not substring?
THEN @ Check next digit pair.
NOT @ Change signal to repeat DO loop.
1. 'n' STO @ Don't repeat FOR loop.
END @ Finish inner test.
.01 @ Step size.
STEP @ End loop.
NIP @ Discard the string.
UNTIL @ Next power of 2?
END @ Success!
NIP @ Discard the 2.
POP @ Restore flags.
\>> @ Finish program.
Actually, 2329 is the smallest power of 2 with at
least 100 digits, so now that I know that, I could start there:
%%HP: T(3)F(.);That runs in about 197 seconds on my 49g+, and about 406 seconds on
@ For any 49 series with PUSH and POP commands.
@ Download or edit in exact mode.
@ Checksum: FD1h
@ Size: 147.5
\<< @ Begin program.
PUSH @ Save flags.
2. FIX @ Force display mode.
2 328 @ Start with 2 and 328.
DO @ Start generating powers of 2.
1 + @ Increment power.
DUP2 @ Make copies.
^ @ Raise 2 to power.
\->STR @ Convert to string.
1. @ Signal to stop DO loop.
0. .99 @ Generate strings "00" through "99"
FOR n @ Begin loop.
OVER @ Copy of power of 2 string.
n @ 0.00 through 0.99.
\->STR @ Convert to string.
3. 4. SUB @ "00" through "99".
IF @ Prepare for test
POS NOT @ Not substring?
THEN @ Keep looking.
NOT @ Change signal to continue DO loop.
1. 'n' STO @ Exit FOR loop.
END @ Finish test.
.01 @ Step size.
STEP @ End loop.
NIP @ Discard the string.
UNTIL @ Next power of 2?
END @ Success!
NIP @ Discard the 2.
POP @ Restore flags.
\>> @ Finish program.
But now that we know the solution, it's hard to beat the program:
\<< 975 \>>for returning the correct value.
Regards,
James
Quote:Well, you're welcome and thanks, Don.
Thanks James and Howard. Boy, you guys are good!
Actually, my first stab at it was just brute force; not much
thought involved in it. It was a fairly simple matter of just
writing the program for what I had in mind. I can see where it
could be easily improved, even using the extra local variables
with a pure brute force approach.
Getting it down to using just the stack except for the FOR index
local variable did take me some thought. As has been noted often
enough, keeping track of the RPL stack (and getting the "stack
flag" in the right place) can be a bit of a challenge. Adding the
check for a length of at least 100 digits did lead me down a
couple of garden paths, but it was surprisingly simple once I saw
an easy way to do it. Of course, it's certainly possible that
someone will come up with a better program.
Quote:I'm lazy and like to keep things as easy as possible, so for all
Well, I thought about doing it on my 49g+, but I'm not a big fan
of RPL (I'm a minimalist, so I gravitate toward RPN).
Of course, for this particular problem, I have my doubts about
whether it's even possible to solve with what's built-in on a
28/48 series or Classic RPN model. Is anyone up to giving it a
try?
Quote:Hmm.... From the very little bit that I've tried TI models, they
I also considered my TI89 Titanium, but I knew that Mathematica
would be the fastest solution, although it is certainly not
programmer-friendly.
Quote:Ah well, I've never had my hands on the programs that you and
Here is what I came up with:
found = False;
p = 100;
While [found != True,
x = ToString[2^p];
a = Table[0, {100}];
sl = StringLength[x];
Do[
a[[ToExpression[StringTake[x, {i, i + 1}]] + 1]] = 1;
, {i, 1, sl - 1}];
If[Plus @@ a == 100, Print [p, " ", "gotit"];
found = True];
p = p + 1;
]
Print ["Complete"]
Quote:Me neither; my mathematical knowledge is limited, but this looked
I had no idea of the answer before I ran it,
Quote:Now that's something that would certainly never occur
and when I saw that the magic number was 975, I thought wow,
that's the sum of the digits of the first odd abundant number (I
believe), 945.
Quote:From what I read at Wikipedia, that just might be
My (unattainable) goal is to find an odd perfect number, but for
now I'll settle for smaller victories.
Quote:Yes, that's reason enough, and besides that, it was a good enough reason
No real reason for finding this other than "I was just wondering,"
which is reason enough.
Quote:You're welcome and thanks again.
Thanks for your efforts, you guys are great.
Regards,
James
Much thanks James.
I have long thought that "brute force" is underrated! Yes, I can appreciate the beauty of a nifty algorithm that is so much faster and shorter than the brute force method, and I'm always happy to see Valentin's (and others) neato solutions to problems that can also be solved by brute force. I do like to see how it can be done in better ways. I am also of the "old school" of programming, having grown up with and made a career of programming in procedural languages like Fortran, Cobol, and even Basic. Object oriented things came along toward the end of my career, and I guess I was just too tired to learn a new way of doing things.
My new career (at age 56 no less) is teaching; specifically, middle school math, and I love it. The kids are so full of energy! I tell them that I will give an A and require no work from anyone who can tell me an odd perfect number. Now THAT motivates them. I need to be wary though, because one of them may do that some day.
Thanks again for your inputs, I really do appreciate it. I modified my Mathematica program to find the power of 2 for all the 3-digit numbers, 000 to 999. It took over an hour to run on my 3 GHZ Pentium, and the result was 2 to a power over 16000. I think that number is too big even for the 49g+ and the TI Titanium, but Mathematica can do it.
16963, to be exact. Running this on my X86_64 system, and redirecting output (so screen writes didn't bias the results), an elaboration on the code I published earlier took 8.702s to exhaustively search for the answer. As before, I estimated a lower bound by packing the digits, perhaps optimally, and finding the lowest power of two that exceeded the result.
To avoid plastering more Perl code onto a site devoted to HP calculators, I have put my code and its output up on the web.
Regards,
Howard
(Edited to change URL of the code. My web host doesn't like files named "*.pl")
Edited: 8 Oct 2006, 10:30 p.m.
Okay, I guess I was shaky on the "rules". I didn't know if "234" would count as both 23, and 34.
I'd guess one reason the speed boost isn't nearly as great as it seems like it should be is that a greater proportion of time is spent calculating, say, 2^835 as compared to 2^8. It looks like your program is actually calculating 2 to each power during each step; maybe another simple speed up could be keeping a copy of the current power of 2 on the stack, and then just multiplying that by 2 on each loop.
Quote:
But is there some permutation of the 100-digit string"01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789"
(break added to avoid scrolling)
which contains each of the digit pairs 00 through 99 exactly once?
No, 101 digits is the shortest it can be.
Consider:
Every pair has a first digit and a last digit.
The sequence as a whole also has a first and a last digit.
All the digits in the sequence can serve as both the first digit of one pair, and the last digit of another pair, except the first and last digits of the sequence as a whole.
Now, if we have 00 to 99, then we have 100 distinct pairs of digits.
In order for there to be a 100-digit sequence, every digit in any given pair must serve as the first digit of one pair, and the second digit of another, different pair.
However, the first digit of the sequence as a whole cannot be the last digit of a two-digit pair, nor can the last digit of the sequence be the first digit of a two-digit pair.
Therefore, any 100-digit sequence contains at most 98 digits that are shared by two different pairs. leaving the first and last
digits to be unshared.
This lets you represent at most 99 distinct pairs of numbers in a 100-digit sequence.
In order to represent 100 distinct two-digit pairs, you must expand the available shared digits by one to 99, making it possible to represent 100 distinct pairs.
This sets a minimum of 101 digits to represent 100 distinct pairs.
Also, since I decided that leading zeroes were disallowed, I came up with this 101-digit sequence instead:
90010203040506070809112131415161718192232425262728293343536373839445464748495565758596676869778798899
The program that found this number is here.
Edited: 9 Oct 2006, 1:50 a.m.
Quote:
As before, I estimated a lower bound by packing the digits, perhaps optimally, and finding the lowest power of two that exceeded the result.
I haven't looked to see if it will change the result, but I have a more optimal packing for you, a 1,002-digit sequence containing 000..999:
99000100200300400500600700800901101201301401501601
70180190210220230240250260270280290310320330340350
36037038039041042043044045046047048049051052053054
05505605705805906106206306406506606706806907107207
30740750760770780790810820830840850860870880890910
92093094095096097098099111211311411511611711811912
21231241251261271281291321331341351361371381391421
43144145146147148149152153154155156157158159162163
16416516616716816917217317417517617717817918218318
41851861871881891921931941951961971981992223224225
22622722822923323423523623723823924324424524624724
82492532542552562572582592632642652662672682692732
74275276277278279283284285286287288289293294295296
29729829933343353363373383393443453463473483493543
55356357358359364365366367368369374375376377378379
38438538638738838939439539639739839944454464474484
49455456457458459465466467468469475476477478479485
48648748848949549649749849955565575585595665675685
69576577578579586587588589596597598599666766866967
7678679687688689697698699777877978878979879988898999
The program that found this number is here.
Edited: 9 Oct 2006, 1:48 a.m.
Since the ultimate answer is many orders of magnitude larger than your minimum guess - or mine - this result doesn't change the final answer. But your program sure is cool! 8) And your packing is 21 digits better than mine.
It was an interesting coincidence that the length of my packing - 1023 digits - was 210-1. But I'll give that up for more efficient packing any day.
Regards,
Howard
Sometimes brute-force problem solving really does seem to be the
"best" way, although various "nifty tricks" are indeed impressive
and are much better if you happen to know of them or figure them
out. Often it seems to be a trade-off between how fast one can
come up with a "good" program and how fast the calculator can
execute the program. Would you rather spend your time writing a
more "optimal" program, or waiting for the calculator to run a
"good enough" program?
Yes, it appears to me that the 49 series errors out immediately
with "^ Error: Integer too large" if I ask it to raise any exact
integer (even 0 or 1) to the power of any exact integer greater
than 9999. So, at first look, it seems that 2 raised to some power
greater than 16000 would be well beyond its capability. But I can
raise 2 to the power of 400, and then raise the result to the
power of 40, which would end up the same value as 2 to the power
of 16000. So in some cases, those in which the exponent can be
factored into integers all less than 10000, integers can be raised
to powers greater than 9999 (always assuming enough available
memory); it's just a round-about way of cajoling the calculator
into working out the result, and waiting for it.
Whether it would eventually return a result for an integer raised
to a large power is another matter. For example, with
\<<or
10000
9999 ^
\>>
\<<it does (eventually) return the correct 39997-digit number (1
10000
101 ^
11 ^
3 ^
3 ^
\>>
An obvious limitation for very large exact integers is the
available memory. Except for the integers "built-in" to ROM, which
each take 2.5 bytes (for the address), as far as I've been able to
surmise, each one takes 5 nibbles for the prologue address, 5
nibbles for the self-inclusive length field, 1 nibble for each
digit, and 1 nibble for the sign field. So the rule for
non-built-in exact integers is 11 nibbles plus 1 nibble per digit,
or 5.5 bytes plus 0.5 byte per digit.
Since the length field is 5 nibbles, it's largest notional value
would be FFFFFh, or 1048575; subtracting 5 nibbles for the length
field itself and 1 nibble for the sign field, that would leave us
1048569 nibbles for the digits, and it would take 1048580 nibbles
(remember that the prologue takes 5 nibbles), or 524290 bytes, to
hold the object.
But since memory is addressed by the nibble with 5-nibble
addresses, the directly addressable memory space is 1048576
nibbles (512KiB). I think that half of that is reserved for ROM,
and some of the RAM is reserved for system use, leaving somewhat
less than 524288 nibbles (256KiB) of "user memory" actually
available for the user.
Anyway, the limitation on the length of exact integers is imposed
by available memory, not the structure of the exact integer object
itself. One could construct a 1048569-digit exact integer object
on a PC and store it on a flash memory card, but the 49 series
would never be able to actually read it.
Experimentally, on my 49g+, after clearing memory, restoring RPN
and "soft menu" modes, disabling last stack, arguments, and
command line saves, purging 'CASDIR' and letting the system
restore part of it, the MEM command returns 246554 (in bytes),
which would be 493108 nibbles, and figuring that the prologue,
length field, and sign field of an integer use up 11 nibbles, that
leaves 493097 nibbles for the digits. To put an object on the
stack takes 5 nibbles for the stack pointer, which cuts it down to
493092 digits. With various other uses of memory probably cutting
it down a bit more, I surmise that the longest exact integer that
one could possiby get onto the stack of a 49 series would be
slightly less than that. Since it's generally desirable to have
the "last" saves enabled, memory is needed for other purposes, and
doing anything with very large integers takes a long time, the
longest integer that it would be comfortable to work with would be
much smaller.
What other limitations the 49 series may have with large exact
integers, I don't know.
Regards,
James
Edited: 9 Oct 2006, 3:28 a.m.
Thank you! That explains perfectly why I didn't see any way to
come up with a sequence that would satisfy the requirement with
less 101 digits.
Since I was testing the sequence as a character string, leading
zeros were of no concern to me, but they certainly would be if the
sequence were treated as a number. It's very easy to modify my
programs to eliminate any leading zero. I suppose that there are
probably several "optimal" sequences. My 101-digit integer result
is:
99897969594939291908878685848382818077675747372717066564636261605545352515044342414033231302212011009
The program which generated this number can be found
here.
Regards,
James
Thanks, Crawl!
Good point. 2 8 ^ takes only about 0.018 second. 2 835 ^ takes
about 0.228 second. 2 834 ^ returns a 252-digit number, and
multiplying that by 2 (the same result as raising 2 to the
power of 835) takes only about 0.022 second, about 0.206 second
faster than raising 2 to the power of 835. So saving the power of
2 and finding the next power of 2 by simply multiplying it by 2
again certainly seems to offer a substantial time savings.
Okay, I've rewritten the program a bit, and it now takes about 105
seconds on my 49g+, and about 224 seconds on my 49G. That's quite
an impressive improvement!
This newest program can be found
here.
Regards,
James
You can save another few seconds by using logarithms to compute the first power of two with enough digits.
Replace this section:
0 1 @ Start with 0 (power) and 1 (power of 2).by this:
@ First find lowest power that results in at least 100 digits. The
@ power of 2 integer must be at least 101 digits long.
DO @ Start generating powers of 2.
SWAP @ Move power down.
1 + @ Increment multiplication count (power).
SWAP @ Move old power of 2 down.
2 * @ Multiply by 2 (raise to next power of two).
DUP @ Copy of new power of 2.
SIZE @ Number of digits.
UNTIL
99. > @ At least 100 digits?
END
1.E99 LNMarcus
2. LN / @ compute log2 of 100 digit number
CEIL R\->I @ round up and make it an exact integer
2 OVER ^ @ put exponent and power of 2 on stack
Quote:
Thank you! That explains perfectly why I didn't see any way to
come up with a sequence that would satisfy the requirement with
less 101 digits.
Similar logic reveals that 1,002 digits is the shortest for the three-digit case that appeared later in the thread.
Quote:
I suppose that there are probably several "optimal" sequences.
Yes, if by 'several' you mean '19.2 gazillion'.
I tweaked my program to do a better job of finding optimal packings, and to attempt to emit them all, rather than just the first one it finds for each leading digit.
Here's the first value it found:
10011202130314041505160617071808190922324252627282933435363738394454647484955657585966768697787988991
Here's the four millionth one:
10011202130314041505160617071808190922324252627282933435363738394454647484955657969987866768597758891
After cleaning the skid marks off my CPUs, I've put the tweaked program here so that someone else with more cache than sense can enumerate the remainder.
Thanks for the tip, Marcus.
Actually, I knew that there was some way or other to do that with logarithms, but about all that I remembered of them is how to find them in the tables and use them for multiplication and division. Your post prompted me to study up on them a bit to remember just why your code works.
Actually, I modified your code a bit for my program. Because the exponent is incremented before the first test, I initially want the largest integer that returns a string less than 101 digits long.
Now the program takes about 99.2 seconds on my 49g+, and about 215 seconds on my 49G, so it was a worthwhile revision.
The revised program can be found here.
Regards,
James
James,
Quote:
Actually, I modified your code a bit for my program. Because the exponent is incremented before the first test, I initially want the largest integer that returns a string less than 101 digits long.
I had checked my code fragment against yours before I posted it and the results were the same.
Quote:
The smallest 101-digit number is 10^100, so I want the largest integer less than n such that 2^n=10^100.
This statement from your program comment is slightly off: You will not find an integer with the property 2n=10100, this should be an inequality. That's the reason why the code uses the FLOOR (or in my version CEIL) function to round the logarithm to the neighboring integer.
There is another issue with your code: As you stated, 10^100 is a number with 101 digits, a one and 100 zeroes. By rounding down its base two logarithm we get an exponent of 332 and a resulting power of two ~= 8.7E99. This is the largest power of two with less then 101 digits and therefore the correct starting point for the search loop. My original code (and yours too, see above) resulted in an exponent of 329 and a power of two ~= 1.09E99. This is the smallest power of two with 100 decimal digits and therefore slightly less then the "best" lower limit for the loop. Not much of an issue, I think.
BTW, LOG(1.E100) is a trivial operation and can be further "optimized", try it on your own calc.
Marcus
Quote:Okay, and I noticed that my previous code could be improved, thus
Quote:I had checked my code fragment against yours
Actually, I modified your code a bit for my program. Because the
exponent is incremented before the first test, I initially want
the largest integer that returns a string less than 101 digits
long.
before I posted it and the results were the same.
Quote:Hmm.... I don't think that my comment implies that n would be an
Quote:This statement from your program comment is slightly off: You will
The smallest 101-digit number is 10^100, so I want the largest
integer less than n such that 2^n=10^100.
not find an integer with the property
2n=10100, this should be an
inequality. That's the reason why the code uses the FLOOR (or in
my version CEIL) function to round the logarithm to the
neighboring integer.
Quote:Quite so. I think that my previous code started checking with the
There is another issue with your code: As you stated, 10^100 is a
number with 101 digits, a one and 100 zeroes. By rounding down its
base two logarithm we get an exponent of 332 and a resulting power
of two ~= 8.7E99. This is the largest power of two with less then
101 digits and therefore the correct starting point for the search
loop. My original code (and yours too, see above) resulted in an
exponent of 329 and a power of two ~= 1.09E99. This is the
smallest power of two with 100 decimal digits and therefore
slightly less then the "best" lower limit for the loop. Not much
of an issue, I think.
Quote:Yes, I was well aware of that, but was thinking that for someone
BTW, LOG(1.E100) is a trivial operation and can be further
"optimized", try it on your own calc.
Another potential optimization that I've thought of was to start
checking for digit pairs at 99 and work my way down to 00. I
didn't have any good reason for expecting that this
would be any faster, but it seemed to me that it
might be. But, experimentally, it turns out that that
seems to be slightly slower instead of faster, so I've stuck with
starting at 00 and working my way up to 99.
I'm surprised that I missed a more important optimization, since
I've often used it to shave a little off of the execution time
with no change in the program size. "DUP +" accomplishes the same
as "2 *", and is faster. Usually not much of an issue, but within
a loop, particularly with large "exact integers", a worthwhile
optimization.
The latest revisions get the execution time down to about 90.2
seconds on my 49g+, and about 201 seconds on my 49G.
The source code for this revision can be found
here.
Regards,
James
Edited: 11 Oct 2006, 6:10 a.m. after one or more responses were posted
James,
for me as a (former) mathematician, "n" denotes an integer. Your recent comments make things clearer.
I'm wondering whether there is a better way to do the search in the inner loop, probably by building a { list } with all digit pairs already present as strings and using GETI in the loop instead of building the strings on the fly. I've no plans to test it, but you might want to try it out.
Another small correction: 2^x-10^100 should read 2^x=10^100.
Marcus
Edited: 11 Oct 2006, 2:34 a.m.
Quote:Yes, I agree that letters such as "n" and "m" normally denote
for me as a (former) mathematician, "n" denotes an integer.
The plain fact is that I was thinking of integers, so "n" came to
my mind, and I used "n" where I should've used "x", and being so
sleepy at the time, I didn't notice that it was misleading, and
even reading it over again, I didn't immediately notice it.
Quote:That strikes me as an excellent suggestion. I'm not certain, but I
I'm wondering whether there is a better way to do the search in
the inner loop, probably by building a { list } with all digit
pairs already present as strings and using GETI in the loop
instead of building the strings on the fly. I've no plans to test
it, but you might want to try it out.
Quote:Thanks; that was a typo. Apparently my finger hit the "-" key when
Another small correction: 2^x-10^100 should read
2^x=10^100.
Regards,
James