wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> 2^n
        
(Message started by: Christine on Dec 12^th, 2012, 10:41am)

Title: 2^n
Post by Christine on Dec 12^th, 2012, 10:41am

Does the decimal expansion of 2^n contain all the digits 0 to 9 at least once for large n ?

Title: Re: 2^n
Post by towr on Dec 12^th, 2012, 11:18am

Do you mean is there an K such that for n>=K 2ⁿ always contains every digit in the decimal expansion?
Be cause I'm sure it's true for at least few n's, but I don't know if at some points it's always true.

Title: Re: 2^n
Post by Christine on Dec 12^th, 2012, 1:50pm

I have 2 questions:

It appears that for n = 168 all the digits 0-9 are represented in the decimal expansion.

for n < 168 some digits are missed in 2^n

Digit 7: is it true that for n => 72 the digit 7 will always be represented in the decimal expansion of 2^n?

That is, n < 72, the digit 7 will be missed sometimes.

Title: Re: 2^n
Post by towr on Dec 12^th, 2012, 10:42pm

It's true up to n=100000, but that's no proof, of course.
The easiest way is probably to show that for some K the last K digits cycle through a set where each of these parts contains all digits.

Title: Re: 2^n
Post by Grimbal on Dec 13^th, 2012, 2:10pm

I would say there is no such cycle.

Take for example digit 7.

If for some K, m values in the cycle have no digit 7, then for K+1, the cycle length gets multiplied by an integer between 1 and 10. The number of values that have no 7 in the last K digits is a multiple of m in the longer cycle with K+1 digits. On average 5.5 times more. On the other side, on average, only 10% of them have a digit 7 as first digit.

So the number of 7-less values mod K tends to increase with K. The larger K becomes, the more hopeless it is to have 7's in all values.

But that doesn't mean there are 7-less values in 2^n. In fact, by considering only K digits, we are ignoring a very large proportion of the digits of 2^n.

Title: Re: 2^n
Post by towr on Dec 13^th, 2012, 10:42pm

I disagree. Every increase of the cycle length gives you an extra digit that may be your missing digit, say, a 7. So the proportion always goes down.

Cycle lengths are 4*5^K-1
If the digits are random the chance of using only 9 of the 10 digits is 0.9^K
~~And so the expected number of these in the cycle goes down by almost a factor 2 for each increase of K.~~

Title: Re: 2^n
Post by Grimbal on Dec 14^th, 2012, 6:05am

But it is not enough that the proportion of numbers missing some digit in the last K digits drops down to 0.

It is like the question what proportion of integers does not include digit 3. The proportion of numbers <N that don't include the digit 3 drops to 0 as N goes to infinity, but that doesn't mean that past some point all numbers include that digit.

Title: Re: 2^n
Post by towr on Dec 14^th, 2012, 11:48am

on 12/14/12 at 06:05:57, Grimbal wrote:
But it is not enough that the proportion of numbers missing some digit in the last K digits drops down to 0.
But isn't it enough (for a probabilistic argument, not as proof) that the expected number of numbers missing some digit drops to 0? The proportion drops much faster than the number of numbers grows.
It isn't comparable to your example.

Title: Re: 2^n
Post by Grimbal on Dec 15^th, 2012, 8:00am

I start to wonder whether we are speaking about the same thing.

My claim is that in the repeating cycle of the sequence
2^n mod 10^K
the number of numbers that are written without the digit 7 is growing with K. As a result, there is no K such that each and every number in the cycle is written with a 7.

If I do the calculations for each K of the cycle length and the number of 7-less numbers, I get the following figures:
1: 4 4
2: 20 18
3: 100 81
4: 500 364
5: 2500 1639
6: 12500 7375
7: 62500 33188
8: 312500 149336
9: 1562500 672027
10: 7812500 3024119
11: 39062500 13608569
12: 195312500 61238500

Obviously, there are more and more numbers that don' t include the digit 7, even though the proportion of such numbers drops to 0.

You can even show that there are at least 4^K 7-less numbers in the cycle:
For K=1, all 4 elements are 7-less.
When you go from K to K+1, each element of the cycle unfolds into 5 elements in the longer cycle. These are all different, so at most 1 of them starts with digit 7. That means that for each 7-less element in the cycle for K, there are at least 4 7-less element in the cycle for K+1.

The figures above confirm that lower bound.

Title: Re: 2^n
Post by Grimbal on Dec 15^th, 2012, 8:43am

on 12/13/12 at 22:42:50, towr wrote:

Cycle lengths are 4*5^K-1
If the digits are random the chance of using only 9 of the 10 digits is 0.9^K
And so the expected number of these in the cycle goes down by almost a factor 2 for each increase of K.

I don't see how the expected number goes down by a factor 2. I would say it increases by a factor 5*0.9.

Title: Re: 2^n
Post by towr on Dec 15^th, 2012, 9:54am

on 12/15/12 at 08:43:29, Grimbal wrote:

I don't see how the expected number goes down by a factor 2. I would say it increases by a factor 5*0.9.

Yeah, apparently I lost the ability to perform basic arithmetic... I hope it doesn't last.