Author |
Topic: 2^n (Read 1872 times) |
|
Christine
Full Member
Posts: 159
|
Does the decimal expansion of 2^n contain all the digits 0 to 9 at least once for large n ?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
Re: 2^n
« Reply #1 on: Dec 12th, 2012, 11:18am » |
 Quote  Modify
|
Do you mean is there an K such that for n>=K 2n 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Christine
Full Member
Posts: 159
|
|
Re: 2^n
« Reply #2 on: Dec 12th, 2012, 1:50pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 2^n
« Reply #3 on: Dec 12th, 2012, 10:42pm » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 2^n
« Reply #4 on: Dec 13th, 2012, 2:10pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 2^n
« Reply #5 on: Dec 13th, 2012, 10:42pm » |
Quote Modify
|
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*5K-1
If the digits are random the chance of using only 9 of the 10 digits is 0.9K
And so the expected number of these in the cycle goes down by almost a factor 2 for each increase of K.
|
| « Last Edit: Dec 15th, 2012, 10:00am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 2^n
« Reply #6 on: Dec 14th, 2012, 6:05am » |
Quote Modify
|
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.
|
| « Last Edit: Dec 14th, 2012, 6:06am by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 2^n
« Reply #7 on: Dec 14th, 2012, 11:48am » |
Quote Modify
|
on Dec 14th, 2012, 6:05am, 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.
|
| « Last Edit: Dec 15th, 2012, 10:01am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 2^n
« Reply #8 on: Dec 15th, 2012, 8:00am » |
Quote Modify
|
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.
|
| « Last Edit: Dec 15th, 2012, 8:05am by Grimbal » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 2^n
« Reply #9 on: Dec 15th, 2012, 8:43am » |
Quote Modify
|
on Dec 13th, 2012, 10:42pm, towr wrote:Cycle lengths are 4*5K-1
If the digits are random the chance of using only 9 of the 10 digits is 0.9K
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 2^n
« Reply #10 on: Dec 15th, 2012, 9:54am » |
Quote Modify
|
on Dec 15th, 2012, 8:43am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print