Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a friend who turned 32 recently. She has an obsessive compulsive disdain for odd numbers, so I pointed out that being 32 was pretty good since not only is it even, it also has no odd factors. That made me realize that 64 would be an even better age for her, because it's even, has no odd factors, and has no odd digits. I then wondered how many other powers of 2 have this property. The only higher power of 2 with all even digits that I could find was 2048.

So is there a larger power of 2 with all even digits? If not, how would you go about proving it?

I tried examining the last N digits of powers of 2 to look for a cycle in which there was always at least one odd digit in the last N digits of the consecutive powers. Unfortunately, there were always a very small percentage of powers of 2 whose last N digits were even.

Edit: Here's a little more info on some things I found while investigating the N digit cycles.

$N$: $2,3,4,5,6,7,8,9$

Cycle length: $20,100,500,2500,12500,62520,312500,1562500,\dotsc, 4*5^{N-1}$

Number of suffixes with all even digits in cycle: $10, 25, 60, 150, 370, 925, 2310,5780,\sim4*2.5^{N-1}$

It seems there are some interesting regularities there. Unfortunately, one of the regularities is those occurrences of all even numbers! In fact, I was able to find a power of 2 in which the last 33 digits were even $(2^{3789535319} = \dots 468088628828226888000862880268288)$.

Yes it's true that it took a power of 2 with over a billion digits to even get the last 33 to be even, so it would seem any further powers of 2 with all even digits are extremely unlikely. But I'm still curious as to how you might prove it.

Edit 2: Here's another interesting property I noticed. The next digit to the left of the last N digits will take on every value of its parity as the N digits cycle each time. Let me illustrate.

The last 2 digits cycle every 20 powers. Now examine the following:

$2^7 = 128$
$2^{27} = \dots 728$
$2^{47} = \dots 328$
$2^{67} = \dots 928$
$2^{87} = \dots 528$
$2^{107} = \dots 128$

Notice that the hundreds place starts out odd and then proceeds to take on every odd digit as the final 2 digits cycle.

As another example, let's look at the fourth digit (knowing that the last 3 digits cycle every 100 powers.)

$2^{18} = 262144$, $2^{118} = \dots 6144$, $2^{218} = \dots 0144$, $2^{318} = \dots 4144$, $2^{418} = \dots 8144$, $2^{518} = \dots 2144$

This explains the power of 5 in the cycle length as each digit must take on all five digits of its parity.

EDIT 3: It looks like the (N+1)th digit takes on all the values 0-9 as the last N digits complete half a cycle. For instance, the last 2 digits cycle every 20 powers, so look at the third digit every 10 powers:

$2^{8} = 256$, $2^{18} = \dots 144$, $2^{28} = \dots 456$, $2^{38} = \dots 944$, $2^{48} = \dots 656$, $2^{58} = \dots 744$, $2^{68} = \dots 856$, $2^{78} = \dots 544$, $2^{88} = \dots 056$, $2^{98} = \dots 344$

Not only does the third digit take on every value 0-9, but it also alternates between odd and even every time (as the Edit 2 note would require.) Also, the N digits cycle between two values, and each of the N digits besides the last one alternates between odd and even. I'll make this more clear with one more example which looks at the fifth digit:

$2^{20} = \dots 48576$, $2^{270} = \dots 11424$, $2^{520} = \dots 28576$, $2^{770} = \dots 31424$, $2^{1020} = \dots 08576$, $2^{1270} = \dots 51424$, $2^{1520} = \dots 88576$, $2^{1770} = \dots 71424$, $2^{2020} = \dots 68576$, $2^{2270} = \dots 91424$

EDIT 4: Here's my next non-rigorous observation. It appears that as the final N digits cycle 5 times, the (N+2)th digit is either odd twice and even three times, or it's odd three times and even twice. This gives a method for extending an all even suffix.

If you have an all even N digit suffix of $2^a$, and the (N+1)th digit is odd, then one of the following will have the (N+1)th digit even:

$2^{(a+1*4*5^{N-2})}$, $2^{(a+2*4*5^{N-2})}$, $2^{(a+3*4*5^{N-2})}$

Edit 5: It's looking like there's no way to prove this conjecture solely by examining the last N digits since we can always find an arbitrarily long, all even, N digit sequence. However, all of the digits are distributed so uniformly through each power of 2 that I would wager that not only does every power of 2 over 2048 have an odd digit, but also, every power of 2 larger than $2^{168}$ has every digit represented in it somewhere.

But for now, let's just focus on the parity of each digit. Consider the value of the $k^{th}$ digit of $2^n$ (with $a_0$ representing the 1's place.)

$$ a_k = \left\lfloor\frac{2^n}{10^k}\right\rfloor \text{ mod 10}\Rightarrow a_k = \left\lfloor\frac{2^{n-k}}{5^k}\right\rfloor \text{ mod 10} $$

We can write $$2^{n-k} = d\cdot5^k + r$$ where $d$ is the divisor and $r$ is the remainder of $2^{n-k}/5^k$. So $$ a_k \equiv \frac{2^{n-k}-r}{5^k} \equiv d \pmod{10} $$ $$\Rightarrow a_k \equiv d \pmod{2}$$ And $$d\cdot5^k = 2^{n-k} - r \Rightarrow d \equiv r \pmod{2}$$ Remember that $r$ is the remainder of $2^{n-k} \text{ div } {5^k}$ so

$$\text{The parity of $a_k$ is the same as the parity of $2^{n-k}$ mod $5^k$.}$$

Now we just want to show that for any $2^n > 2048$ we can always find a $k$ such that $2^{n-k} \text{ mod }5^k$ is odd.

I'm not sure if this actually helps or if I've just sort of paraphrased the problem.

EDIT 6: Thinking about $2^{n-k}$ mod $5^k$, I realized there's a way to predict some odd digits.

$$2^a \pmod{5^k} \text{ is even for } 1\le a< log_2 5^k$$

The period of $2^a \pmod{5^k}$ is $4\cdot5^{k-1}$ since 2 is a primitive root mod $5^k$. Also

$$2^{2\cdot5^{k-1}} \equiv -1 \pmod{5^k}$$

So multiplying any $2^a$ by $2^{2\cdot5^{k-1}}$ flips its parity mod $5^k$. Therefore $2^a \pmod{5^k}\text{ }$ is odd for

$$1 + 2\cdot5^{k-1} \le a< 2\cdot5^{k-1} + log_2 5^k$$

Or taking the period into account, $2^a \pmod{5^k} \text{ }$ is odd for any integer $b\ge0$ such that

$$1 + 2\cdot5^{k-1} (1 + 2b) \le a< 2\cdot5^{k-1} (1 + 2b) + log_2 5^k$$

Now for the $k^{th}$ digit of $2^n$ ($ k=0 \text{ } $ being the 1's digit), we're interested in the parity of $2^{n-k}$ mod $5^k$. Setting $ a =n-k \text{ } $ we see that the $k^{th}$ digit of $2^n$ is odd for integer $b\ge0$ such that

$$1 + 2\cdot5^{k-1} (1 + 2b) \le n - k < 2\cdot5^{k-1} (1 + 2b) + log_2 5^k$$

To illustrate, here are some guaranteed odd digits for different $2^n$:

(k=1 digit): $ 2\cdot5^0 + 2 = 4 \le n \le 5 $
(k=2 digit): $ 2\cdot5^1 + 3 = 13 \le n \le 16 $
(k=3 digit): $ 2\cdot5^2 + 4 = 54 \le n \le 59 $
(k=4 digit): $ 2\cdot5^3 + 5 = 255 \le n \le 263 $

Also note that these would repeat every $4\cdot5^{k-1}$ powers.

These guaranteed odd digits are not dense enough to cover all of the powers, but might this approach be extended somehow to find more odd digits?

Edit 7: The two papers that Zander mentions below make me think that this is probably a pretty hard problem.

share|improve this question
7  
I just wrote a program that tested all of the powers of 2 up to 2^1,000,000 and 2^11 (2048) was the highest one it could find. –  PhiNotPi Mar 3 '12 at 17:49
50  
Do not mention 64. Try flowers. –  Will Jagy Mar 3 '12 at 19:28
2  
Flowers would probably be easier at this point. I have been pointedly silent on the matter since I offhandedly mentioned that "I might see if I can prove this conjecture" a while ago. –  Brian Rothstein Mar 4 '12 at 8:50
3  
I find it interesting that only 5 of these numbers have been found (with a conjecture that the list is complete). This strikes me as oddly similar to Fermat primes. There are only 5 known Fermat primes (primes of the form $2^{2^n}+1$) and conjecturally that list is complete. Maybe these conjectures are equivalent. +1 Nice question. –  Bill Cook Mar 9 '12 at 21:59
    
Have you tried posting this at MO? –  Fernando Martin Mar 31 '12 at 18:12
show 2 more comments

3 Answers

up vote 28 down vote accepted
+150

This seems to be similar to (I'd venture to say as hard as) a problem of Erdős open since 1979, that the base-3 representation of $2^n$ contains a 2 for all $n>8$.

Here is a paper by Lagarias that addresses the ternary problem, and for the most part I think would generalize to the question at hand (we're also looking for the intersection of iterates of $x\rightarrow 2x$ with a Cantor set). Unfortunately it does not resolve the problem.

But Conjecture 2' (from Furstenberg 1970) in the linked paper suggests a stronger result, that every $2^n$ for $n$ large enough will have a 1 in the decimal representation. Though it doesn't quantify "large enough" (so even if proved wouldn't promise that 2048 is the largest all-even decimal), it looks like it might be true for all $n>91$ (I checked up to $n=10^6$).

share|improve this answer
    
Nice find on that paper. There was actually a similar question here: Status of a conjecture about powers of 2.. Though it was not treated as rigorously. –  Brian Rothstein Mar 10 '12 at 19:05
    
Wow, if I'm reading it correctly, Conjecture 2' proposes that not only does every digit occur in all sufficiently large powers of 2, but any particular finite sequence of digits will occur in all powers of 2 which are large enough. –  Brian Rothstein Mar 10 '12 at 19:27
    
I'm accepting this answer because it seems like it provides good evidence that this problem is very difficult. –  Brian Rothstein Mar 11 '12 at 18:09
add comment

This sequence is known to the OEIS.

Here are the notes, which give no explicit answer but suppose that your conjecture is correct:

Are there any more terms in this sequence?

Evidence that the sequence may be finite, from Rick L. Shepherd (rshepherd2(AT)hotmail.com), Jun 23 2002:

1) The sequence of last two digits of $2^n$, A000855 of period $20$, makes clear that $2^n > 4$ must have $n = 3, 6, 10, 11,$ or $19 (\text{mod }20)$ for $2^n$ to be a member of this sequence. Otherwise, either the tens digit (in $10$ cases), as seen directly, or the hundreds digit, in the $5$ cases receiving a carry from the previous power's tens digit $\geq 5$, must be odd.

2) No additional term has been found for n up to $50000$.

3) Furthermore, again for each n up to $50000$, examining $2^n$'s digits leftward from the rightmost but only until an odd digit was found, it was only once necessary to search even to the 18th digit. This occurred for $2^{12106}$ whose last digits are $\ldots 3833483966860466862424064$. Note that $2^{12106}$ has $3645$ digits. (The clear runner-up, $2^{34966}$, a $10526$-digit number, required searching only to the $15$th digit. Exponents for which only the $14$th digit was reached were only $590, 3490, 8426, 16223, 27771, 48966$ and $49519$ - representing each congruence above.)

share|improve this answer
    
2) and 3) clearly don't prove anything, and 1) sounds rather vague to me, too – but my number theory knowledge is $<\varepsilon$, so... Perhaps someone comment on how much this actually means? –  leftaroundabout Mar 3 '12 at 22:37
5  
@leftaroundabout, indeed this is not a proof but what this suggests is that the theorem is likely to be true due to probabilistic reasons even though it can be very hard to find a proof for this. –  Listing Mar 3 '12 at 22:43
    
@Listing: Thanks for putting the bounty on this question! I don't want my OCD friend worrying that there might be a small chance that she'll need to live past age 2048 to reach another nice age. –  Brian Rothstein Mar 9 '12 at 11:49
add comment

Here's a heuristic justification that none exist.

The odds of a uniformly-randomly chosen $n$-digit number has all of its digits even is $$ p(n) = \frac{5}{9} \frac{1}{2}^{n-1} $$

(note that your last digit data supports this method of analysis: roughly $1/2^n$ of the last $n$-digits are all-even)

On average, there are $\log_2(10)$ $n$-digit numbers in the sequence of powers of 2.

So, at random, the odds that there does not exist a power of 2 of $k$ or more digits that are all even is $$ \prod_{n=k}^{\infty} \left(1 - \frac{5}{9} \frac{1}{2^{n-1}}\right)^{\log_2 10}$$ For $k=10$, wolfram alpha computes this to be $0.992814$. So there's a less than 1% chance of there being another power of 2 whose digits are all even.

Of course, after you exhaust the small ones to see one doesn't exist, you can plug in much larger values into $k$....

share|improve this answer
3  
Neat fact, however in my honest opinion a 1% chance is still quite high to conclude that such a number could not exist :) –  Listing Mar 9 '12 at 9:25
1  
I've actually verified the conjecture for over a billion digits in the course of finding the 33 all even N digit suffix. Your formula is another good piece of evidence indicating that there are not going to be any more powers of 2 with all even digits. I still would like to find a proof, though. –  Brian Rothstein Mar 9 '12 at 10:06
1  
@Listing: For $k=100$, the odds are worse than one in $10^{-15}$. (of course, you have to check all 1-99 digit numbers manually) Wolframalpha won't even try to compute it for $k=10^9$. :) –  Hurkyl Mar 9 '12 at 10:34
    
@Brian: I agree a proof would be nice. Still, it is at least something to estimate just how surprising it would be for your conjecture to be false. –  Hurkyl Mar 9 '12 at 10:35
1  
@Patrick: The probability would be 1. The odds that any particular number passes the condition is 1 in $10^{4 \cdot 10^{9}}$ no matter how large, so the odds that every number fails the condition is $\prod_{n=k}^{\infty} (1 - 10^{-4 \cdot 10^{9}}) = 0$. –  Hurkyl Mar 9 '12 at 22:20
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.