7
$\begingroup$

Determine (with proof) whether or not there exists a positive integer $N$ such that for every integer $n\ge N$, the number $2^n$ in base ten has two consecutive digits that are equal. (Trailing zeros do not count).

I tested many powers of $2$ for small $n$ and wasn't able to find such an $N$. Can we prove this by contradiction that there does not exist such an $N$? I was thinking that if $N$ does satisfy this, then we can consider certain powers of $2$ that will make a contradiction.

$\endgroup$
  • 3
    $\begingroup$ Where did you find this problem? Its difficulty seems overwhelming to me. $\endgroup$ – ajotatxe Feb 3 '17 at 20:56
  • $\begingroup$ @ajotatxe I found it on AoPS. $\endgroup$ – user19405892 Feb 3 '17 at 20:56
  • $\begingroup$ $N$ won't be small if it exists at all. You'll be potentially talking of something where $2^N$ has thousands of digits. $\endgroup$ – Joffan Feb 3 '17 at 20:57
  • 2
    $\begingroup$ Are you sure that the person who proposed the problem knows the answer? $\endgroup$ – ajotatxe Feb 3 '17 at 21:00
  • 5
    $\begingroup$ I checked up to 10000 and it seems to be $N = 127$ $\endgroup$ – the_architect Feb 3 '17 at 21:10
2
$\begingroup$

I would say it is certain to be true, but will be difficult to prove. Any number with thousands of digits is almost certain to have two consecutive digits equal. We make the gross assumption that the digits are uniformly distributed and independent, which actually should be pretty good away from the ends of the number. With a million digits, the chance that there is not a neighboring pair is $0.9^{1000000}\approx 3.23 \cdot 10^{-45758}$ As every $10$ powers of $2$ give three more factors $0.9$ this is essentially a geometric series with ratio $(0.9^3)^{1/10}=0.9^{0.3}\approx 0.96888$ and summing the series will multiply it by about $30$, leaving a vanishingly small number.

$\endgroup$
  • $\begingroup$ I was working on a similar answer. I would expect $N$ to be in the $120$ to $200$ range, but for proof-of-existence purposes it could obviously be much higher. $\endgroup$ – Joffan Feb 3 '17 at 21:36
  • $\begingroup$ @Joffan: the_architect says your intuition is spot on. $\endgroup$ – Ross Millikan Feb 3 '17 at 22:10
  • $\begingroup$ I'll to take minority view the statement is false and the assumption that the digits are uniformly distributed and independent is very gross. The digits must when converted to binary "cancel out". (in two digits that means if $2^k = ab$ then $2a + b= 8m$. For $2^k = abc = a(64 + 32 +4) + b(8 + 2) + c$ we must have c + 2b + 4a +8b + 32a + 64a = 128m=2^k$, etc. not independent). However I'm not having luck working this out. I figure 10 = 2^3 +2 can come into play but... it's a mess. On the other hand with huge amounts of carrying the and significant number of digit I could be dead wrong. $\endgroup$ – fleablood Feb 4 '17 at 0:11
1
$\begingroup$

I'm not sure whether this will work, but looking to the last $k$ digits of $2^n$ might just work.

When looking to the last two digits, we can see that for every $k \equiv 18 \mod 20$, we have $2^k \equiv 44 \mod 100$. Similiarly, if $k \equiv 19 \mod 20$, we have $2^k \equiv 88 \mod 100$.

Looking to the two digits before that, we need to use that the last three digits of $2^n$ repeat with period $100$. This solves the problem for all $k$ congruent to $3, 40, 41, 46, 53, 89, 90, 91, 96$, in addition to those that were already solved.

There are now 19 congruence classes mod 100 eliminated.

$\endgroup$
  • $\begingroup$ We can show this will not work. As you say the last $k$ digits repeat, but you get all combinations of $k$ digits that are divisible by $2^k$. If you start with the ones digit you have to have $2,4,6,8$. Then in the tens digit you need an odd if the ones is $2,6$ and an even if it is $4,8$. In either case you have at least four choices that do not make a match. $\endgroup$ – Ross Millikan Feb 3 '17 at 22:08
  • $\begingroup$ Then the hundreds needs to be odd or even depending on whether the last two are divisible by $8$, but again you will have choices that do not match. This can show that there is at least one (in fact many) $k$ digit ends that have no matching digits. We had a previous problem asking if there every large enough power of $2$ had at least one zero. I tried the same approach and ran into the same problem. $\endgroup$ – Ross Millikan Feb 3 '17 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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