The Museum of HP Calculators

HP Forum Archive 16

[ Return to Index | Top of Index ]

Mathematica challenge
Message #1 Posted by Don Shepherd on 7 Oct 2006, 10:32 p.m.

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?

      
Re: Mathematica challenge
Message #2 Posted by Howard Owen on 8 Oct 2006, 2:06 a.m.,
in response to message #1 by Don Shepherd

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

      
Re: Mathematica challenge
Message #3 Posted by James M. Prange (Michigan) on 8 Oct 2006, 2:10 a.m.,
in response to message #1 by Don Shepherd

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(.);
@ 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.
Unless I've overlooked something, the power of 2 is 975. 2975 equals the following 294 digit value, that I've put a break into after every fifty digits. Join all of the digits into one long number.

31933444952555516986501963408589417057079220166967 32066404075587899539026990342505255932744788217121 74294791495070799239035590078142974985718267487725 57302725120090767217370824280603543109807794922453 70791270278389329296728193392622222168429516870652 01139345100120966662777359236855041588461568

Regards,
James

Edited: 8 Oct 2006, 8:07 a.m.

            
Re: Mathematica challenge
Message #4 Posted by James M. Prange (Michigan) on 8 Oct 2006, 8:08 a.m.,
in response to message #3 by James M. Prange (Michigan)

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.

                  
Re: Mathematica challenge
Message #5 Posted by Crawl on 8 Oct 2006, 12:25 p.m.,
in response to message #4 by James M. Prange (Michigan)

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.

                        
Re: Mathematica challenge
Message #6 Posted by Don Shepherd on 8 Oct 2006, 12:34 p.m.,
in response to message #5 by Crawl

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.

                              
Re: Mathematica challenge
Message #7 Posted by James M. Prange (Michigan) on 8 Oct 2006, 2:36 p.m.,
in response to message #6 by Don Shepherd

Quote:
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.
Yes. I'm assuming that a digit can be shared by two digit pairs.

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);
@ 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
\>>
That returns this 110-digit string:

"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);
@ 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
\>>
That returns this 101-digit string:

"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(.);
@ 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
\>>
Well, that runs through without failing, so evidently that 101-digit string contains each digit pair 00 through 99 once and only once.

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.

                                    
Re: Mathematica challenge
Message #8 Posted by Frank Wales on 9 Oct 2006, 12:59 a.m.,
in response to message #7 by James M. Prange (Michigan)

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.

                                          
Re: Mathematica challenge
Message #9 Posted by James M. Prange (Michigan) on 9 Oct 2006, 5:23 a.m.,
in response to message #8 by Frank Wales

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

                                                
Re: Mathematica challenge
Message #10 Posted by Frank Wales on 9 Oct 2006, 10:17 a.m.,
in response to message #9 by James M. Prange (Michigan)

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.

                        
Re: Mathematica challenge
Message #11 Posted by Howard Owen on 8 Oct 2006, 1:30 p.m.,
in response to message #5 by Crawl

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.

                        
Re: Mathematica challenge
Message #12 Posted by James M. Prange (Michigan) on 8 Oct 2006, 4:41 p.m.,
in response to message #5 by Crawl

Quote:
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.

First, your estimate of at least 197 digits to possibly contain all digit pairs 00 to 99 is too high; see my reply to Don.

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(.);
@ 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.
That took about 136 seconds on my 49g+, compared to about 224 seconds when I started at 21. So it does save about 39%, but not the 67% that you expected.

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(.);
@ 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.
That runs in about 215 seconds on my 49g+, or about 446 seconds on my 49G, but note that the program size is larger. Is it a worthwhile trade-off?

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(.);
@ 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.
That runs in about 197 seconds on my 49g+, and about 406 seconds on my 49G. So, by figuring out which power to start checking at ahead of time instead of letting the program figure that out, I save about 8-9% in execution time.

But now that we know the solution, it's hard to beat the program: 

\<< 975 \>>
for returning the correct value.

Regards,
James

                              
Re: Mathematica challenge
Message #13 Posted by Crawl on 8 Oct 2006, 10:09 p.m.,
in response to message #12 by James M. Prange (Michigan)

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.

                                    
Re: Mathematica challenge
Message #14 Posted by James M. Prange (Michigan) on 9 Oct 2006, 9:04 a.m.,
in response to message #13 by Crawl

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

                                          
Re: Mathematica challenge
Message #15 Posted by Marcus von Cube, Germany on 9 Oct 2006, 9:50 a.m.,
in response to message #14 by James M. Prange (Michigan)

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).
@ 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
by this: 
  1.E99 LN
  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
Marcus
                                                
Re: Mathematica challenge
Message #16 Posted by James M. Prange (Michigan) on 9 Oct 2006, 6:56 p.m.,
in response to message #15 by Marcus von Cube, Germany

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

                                                      
Re: Mathematica challenge
Message #17 Posted by Marcus von Cube, Germany on 10 Oct 2006, 3:06 a.m.,
in response to message #16 by James M. Prange (Michigan)

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

                                                            
Re: Mathematica challenge
Message #18 Posted by James M. Prange (Michigan) on 10 Oct 2006, 10:54 p.m.,
in response to message #17 by Marcus von Cube, Germany

Quote:
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.
Okay, and I noticed that my previous code could be improved, thus the slight modifications.
Quote:
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.
Hmm.... I don't think that my comment implies that n would be an integer, unless you take it that using "n" instead of, for example, "x" implies an integer. I was very sleepy when I wrote the comments, and overlooked that. In fact, I very carefully wrote it that way to slightly emphasize the fact that 2^n=10^100 is not an integer. If n is taken to be integer, then clearly 2^n=10^100 doesn't have any solution, but if we allow n to be a "value" (in this case an irrational number), then it does have a solution, which can be approximated as a "real number" (actually, rational number in decimal notation) on the calculator, which can be rounded to an integer. For the next revision, I've revised the comment to "The smallest 101-digit number is 10^100, so I want the largest integer less than the (non-integer) value of x such that 2^x=10^100." Does that completely clarify what I meant to say?
Quote:
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.
Quite so. I think that my previous code started checking with the next integer higher than the integer exponent which resulted in a lowest power of 2 with less than 101 digits (in case the doubling resulted in an integer with more than 101 digits). I realized that it would be better to start checking with the exponent that would result in the lowest power of 2 with at least 101 digits, thus the change. As you write, not much of an issue, but it does save three iterations of a loop.
Quote:
BTW, LOG(1.E100) is a trivial operation and can be further "optimized", try it on your own calc.
Yes, I was well aware of that, but was thinking that for someone trying to follow the program code, "1.E100 LOG" might be a little easier than simply "100.", and since it's outside of any loop, it makes a relatively tiny difference in the execution time. But for the next revision, I've changed the code (and comments) to simply use "100.".

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

                                                                  
Re: Mathematica challenge
Message #19 Posted by Marcus von Cube, Germany on 11 Oct 2006, 2:30 a.m.,
in response to message #18 by James M. Prange (Michigan)

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.

                                                                        
Re: Mathematica challenge
Message #20 Posted by James M. Prange (Michigan) on 11 Oct 2006, 6:05 a.m.,
in response to message #19 by Marcus von Cube, Germany

Quote:
for me as a (former) mathematician, "n" denotes an integer.
Yes, I agree that letters such as "n" and "m" normally denote integers, and for that matter, "i" and "j" normally mean "instance" or perhaps "iteration" (although "i" can also mean the "imaginary number", and "i", "j", and "k" are often used for a unit vector), letters from the beginning of the alphabet normally denote constants, "x", "y", and "z" denote "unknown values" (but sometimes magnitudes in a rectangular coordinate system), with "u" and "v" denoting substitutions, and various other conventions are often used. As a non-mathematician, I sometimes overlook such conventions (after all, a program wouldn't care, as long as I used a valid name).

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:
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.
That strikes me as an excellent suggestion. I'm not certain, but I expect that it would be faster, although it would probably result in a larger program object. I might give it a try.
Quote:
Another small correction: 2^x-10^100 should read 2^x=10^100.
Thanks; that was a typo. Apparently my finger hit the "-" key when I meant to press the "=" key next to it, and I didn't notice. I've made that correction.

Regards,
James

      
Re: Mathematica challenge
Message #21 Posted by James M. Prange (Michigan) on 8 Oct 2006, 3:24 a.m.,
in response to message #1 by Don Shepherd

By the way, is there any particular reason for wanting to find this?

Regards,
James

            
Re: Mathematica challenge
Message #22 Posted by Don Shepherd on 8 Oct 2006, 9:24 a.m.,
in response to message #21 by James M. Prange (Michigan)

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.

                  
Re: Mathematica challenge
Message #23 Posted by James M. Prange (Michigan) on 8 Oct 2006, 6:36 p.m.,
in response to message #22 by Don Shepherd

Quote:
Thanks James and Howard. Boy, you guys are good!
Well, you're welcome and thanks, Don.

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:
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'm lazy and like to keep things as easy as possible, so for all but the simplest problems, I much prefer RPL as compared to Classic 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:
I also considered my TI89 Titanium, but I knew that Mathematica would be the fastest solution, although it is certainly not programmer-friendly.
Hmm.... From the very little bit that I've tried TI models, they didn't exactly strike me as "programmer-friendly" either. Oh well, perhaps for someone experienced with them....
Quote:
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"]
Ah well, I've never had my hands on the programs that you and Howard used, but with some effort, I think that I get the general ideas. It's no surprise that the 49 series is slower.
Quote:
I had no idea of the answer before I ran it,
Me neither; my mathematical knowledge is limited, but this looked like something that would yield easily enough to a brute force approach, as long as the power of 2 didn't turn out to be too terribly long.
Quote:
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.
Now that's something that would certainly never occur to me!
Quote:
My (unattainable) goal is to find an odd perfect number, but for now I'll settle for smaller victories.
From what I read at Wikipedia, that just might be attainable, but maybe not. Enjoy the search!
Quote:
No real reason for finding this other than "I was just wondering," which is reason enough.
Yes, that's reason enough, and besides that, it was a good enough reason for me to play with the 49 series.
Quote:
Thanks for your efforts, you guys are great.
You're welcome and thanks again.

Regards,
James

                        
Re: Mathematica challenge
Message #24 Posted by Don Shepherd on 8 Oct 2006, 7:29 p.m.,
in response to message #23 by James M. Prange (Michigan)

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.

                              
Re: Mathematica challenge
Message #25 Posted by Howard Owen on 8 Oct 2006, 9:56 p.m.,
in response to message #24 by Don Shepherd

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.

                                    
Re: Mathematica challenge
Message #26 Posted by Frank Wales on 9 Oct 2006, 1:35 a.m.,
in response to message #25 by Howard Owen

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.

                                          
Re: Mathematica challenge
Message #27 Posted by Howard Owen on 9 Oct 2006, 2:32 a.m.,
in response to message #26 by Frank Wales

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

                              
Re: Mathematica challenge
Message #28 Posted by James M. Prange (Michigan) on 9 Oct 2006, 3:20 a.m.,
in response to message #24 by Don Shepherd

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 

\<<
  10000
  9999 ^
\>>
or 
\<<
  10000
  101 ^
  11 ^
  3 ^
  3 ^
\>>
it does (eventually) return the correct 39997-digit number (1 followed by 39996 0s), which takes up 20004 bytes. But I don't care to experiment with finding the largest values that it can handle.

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.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall