88,889 cards are consecutively numbered from 11,111 to 99,999.

These cards are now arranged in a line in any arbitrary order.

Can the 444,445 digit number formed in this manner be a power of 2?

Even at first glance it doesn't seem likely that powers of 2 could be formed:

There could only be 3 or 4 powers of two that have the requisite numbers of digits: call the first one k; the next ones are k*2, k*4, k*8 and k*16. The last one definitely has more digits than the first, and the next to last could have more digits than the first.

As a result, two factors weigh against the probability that one of them can be formed:

• The birthday problem: that among the 444,445 groups of 5 digits needed, there are no duplicates. Duplicates would require there be duplicates in the cards, and duplicates do not occur.
• Leading zeros: None of the cards contain leading zeros. It's not likely that of the 3 or 4 very long numbers there is one that has not even one zero in any of the 444,445 multiple-of-5-plus-1 positions.

Testing it:

The earliest 444,445-digit number is 10^444,444, with common logarithm 444,444. Divide by the common log of 2, to get the mixed-fractional power of 2 to get it:

?444444/(log(2)/log(10))
 1476411.010204118871336876248519982527322069123641416705543103303
 
So the valid powers of 2 start at 1,476,412.

list
   10   for I=1476412 to 1476415
   20    L=(log(2)/log(10))*I-444444
   30    print 10^L;"* 10^444444"
   40   next
OK
run
 1.98590399652092541238131509567199660313414381712026142157545981 * 10^444444
 3.97180799304185082476263019134399320626828763424052284315091961 * 10^444444
 7.94361598608370164952526038268798641253657526848104568630183919 * 10^444444
 15.88723197216740329905052076537597282507315053696209137260367936 * 10^444444
OK

Indeed only 3 of these numbers have the required number of digits--the last one goes into one more digit.  (Note above, that the last 6 digits of each mantissa are probably not reliable, as we subtracted a 6-digit number from the common logarithm, but we won't be using those last few digits.)

Now divide the first few digits into groups of 5:

  19859 03996 52092 54123 81315 09567 19966 03134 14381 71202
  39718 07993 04185 08247 62630 19134 39932 06268 28763 42405
  79436 15986 08370 16495 25260 38268 79864 12536 57526 84810
  

Already, within the first three cards of each, a leading zero is needed, in  03996, 07993 or 08370, and again, no actual card has a leading zero.

So it is indeed impossible that a power of 2 can be formed in this way.

Posted by Charlie on 2007-09-16 16:55:08