53
$\begingroup$

The number $128$ can be written as $2^n$ with integer $n$, and so can its every individual digit. Is this the only number with this property, apart from the one-digit numbers $1$, $2$, $4$ and $8$?

I have checked a lot, but I don't know how to prove or disprove it.

$\endgroup$
14
  • 1
    $\begingroup$ So you're asking if the equation $2^{x_0} \cdot 10^0 + 2^{x_1} \cdot 10^1 + \cdots + 2^{x_n} \cdot 10^n = 2^m$, for some $n,m,x_1,x_2, \cdots, x_n \in \mathbb{N}$ has unique solution? $\endgroup$
    – jh4
    Dec 8, 2014 at 18:23
  • 1
    $\begingroup$ Well, yes! Seems harder than I thought. $\endgroup$
    – bifurcat
    Dec 8, 2014 at 18:24
  • 4
    $\begingroup$ What is true is that a power of $2$ can't end in $00000128$ unless it is $128$. This is because $2^n == 2^7 \mod 10^8$ implies $2^n == 2^7 \mod 2^8$. $\endgroup$ Dec 8, 2014 at 18:49
  • 6
    $\begingroup$ But there are powers of $2$ that end in, for example, $841112244224$, e.g. $2^{6578090}$. $\endgroup$ Dec 8, 2014 at 19:49
  • 2
    $\begingroup$ @Samuel $0 \neq 2^n$ for any $n \in \Bbb N$. $\endgroup$
    – Daniel R
    Dec 9, 2014 at 12:10

4 Answers 4

51
$\begingroup$

This seems to be an open question. See OEIS sequence A130693 and references there.

$\endgroup$
6
  • 5
    $\begingroup$ OMG, thanks! I think I should stop wasting time. $\endgroup$
    – bifurcat
    Dec 8, 2014 at 18:27
  • 60
    $\begingroup$ @bifurcat Yes. If there's one thing Mathematicians shouldn't be doing, it's trying to find solutions to unanswered questions! $\endgroup$
    – KSmarts
    Dec 8, 2014 at 19:27
  • 3
    $\begingroup$ I suspect the question is not tractable in the current state of the art. We have good methods to deal with questions such as "what are the possibilities for the lowest $k$ digits of $2^n$ when $n$ is large", but it appears that this won't solve our problem: there will always be some possibilities whose digits are all in $\{1,2,4,8\}$. We can also look at the highest $k$ digits; that won't help either. We don't have ways to say much about all the digits. $\endgroup$ Dec 8, 2014 at 19:45
  • 3
    $\begingroup$ I feel dumb posting this but... Whilst this may theoretically answer the question, it would be preferable to include the essential parts of the answer here, and provide the link for reference. $\endgroup$
    – J. Musser
    Dec 9, 2014 at 2:50
  • 12
    $\begingroup$ The essential part of the answer is "This seems to be an open question". $\endgroup$ Dec 9, 2014 at 3:41
6
$\begingroup$

Here's some empirical evidence (not a proof!).

Here are the first powers which increase the length of 1-2-4-8 runs in the least significant digits (last digits):

Power 0: 1 digits. ...0:1
Power 7: 3 digits. ...0:128
Power 18: 4 digits. ...6:2144
Power 19: 5 digits. ...5:24288
Power 90: 6 digits. ...9:124224
Power 91: 7 digits. ...9:8248448
Power 271: 8 digits. ...0:41422848
Power 1751: 9 digits. ...3:242421248
Power 18807: 10 digits. ...9:8228144128
Power 56589: 14 digits. ...3:21142244442112
Power 899791: 16 digits. ...9:8112118821224448
Power 2814790: 17 digits. ...6:42441488812212224
Power 7635171: 19 digits. ...5:2288212218148814848
Power 39727671: 20 digits. ...6:48844421142411214848
Power 99530619: 21 digits. ...6:142118882828812812288
Power 233093807: 25 digits:  ...0:2821144412811214484144128
Power 22587288091 : 26 digits: ...9:81282288882824141181288448

Easy to see, this run length grows veeeery slow: $25$ digits of $233093807*log_{10}2 \approx 70168227$ decimal digits are powers of 2. Hardly 25 can reach 70168227.

Let's look at it deeper. Consider $2^k$ having $n$ decimal digits (obviously $n \le k$). Let's say $2^k \mod 5^n = a$. Then by CRT we can recover $2^k \mod 10^n$ (note that $2^k \equiv 0 \pmod {2^n}$):

$$f(a) \equiv 2^k \equiv a \cdot 2^n \cdot (2^{-n})_{\mod 5^n} \pmod{10^n}$$

Now let's assume that $2^k$ randomly goes over $\mod 5^n$. How many there are elements $x \in (0,\dots,5^n-1)$ such that $f(x) \mod 10^n$ consists from digits 1-2-4-8? There are at most $4^n$ such values (all possible combinations of 1-2-4-8 $n$ times), from $5^n$ (remark - we should consider only coprime with 5 numbers, there are $5^{n-1}*4$ such). So if $2^k$ acts randomly, then the probability of getting 1-2-4-8 value is limited by $(4/5)^{n-1}$, which decreases exponentially with $n$ (and $k$).

Now how much powers of 2 do we have for each $n$? Constant amount, 3 or 4! So, if for some small $n$ there are no such values, then very probably for all numbers it's also true.

Remark: this may look mouthful, nearly same explanation could be given modulo $10^n$. But in my opinion it's easier to believe that $2^k$ randomly goes over $\mod 5^n$ than $\mod 10^n$. EDIT: Also, $2$ is a primitive root modulo $5^n$ for any $n$, so it indeed goes over all $5^{n-1}*4$ accounted values.

Remark 2: the exact amount of $x$, such that $f(x) \mod 10^n$ consist from digits 1-2-4-8, from experiments:

...
n=15: 54411 / 30517578125 ~= 2^-19.0973107004
n=16: 108655 / 152587890625 ~= 2^-20.4214544789
n=17: 216803 / 762939453125 ~= 2^-21.7467524186
n=18: 433285 / 3814697265625 ~= 2^-23.0697489411
n=19: 866677 / 19073486328125 ~= 2^-24.3914989097
n=20: 1731421 / 95367431640625 ~= 2^-25.7150367656
...

UPD:

The fact that $2$ is a primitive root modulo $5^n$ is quite important.

  1. We can use it to optimize search for first powers of 2 which increase the 1-2-4-8 run length (first data in this post). For example, for $n=3$ only $13$ of $5^2*4=100$ values correspond to 1-2-4-8 3-digit endings. For $\mod 1000$, period for powers of 2 is equal to order of the group, namely $100$. It means we need to check only 13 of each 100 values. I managed to build the table for $n=20$ which speeds up the computation roughly by $2^{25}$. Sadly each next $n$ for the table is much harder to compute, so this approach does not scale efficiently.

  2. For arbitrary $n$ we can quite efficiently find some $k$ such that $2^k$ has last $n$ digits-powers-of-two.
    Let's assume that for some $n$ we know such $k_0$. Consider $a = 2^{k_0} \mod 10^n$. We want to construct $k'$ for $n+1$. Let's look at $a \mod 2^{n+1}$. It's either $0$ or $2^{n}$. If it's $0$, we can set $(n+1)$'s digit to any from $0,2,4,6,8$, in particular $2,4,8$ will fit our goal. If it's $2^{n}$ then we need to set $(n+1)$'s digit to any from $1,3,5,7,9$, in particular $1$ will be fine for us.
    After setting the new digit we have some value $a' < 10^{n+1}$. We now find $k'$ by calculating discrete logarithm of $a'$ base $2$ in the group $(\mathbb{Z}/5^{n+1}\mathbb{Z})^*$. It must exist, because $2$ is primitive root modulo $5^{n+1}$ and $a'$ is not divisible by five (meaning that it falls into the multiplicative group).

Summing up, it's possible to extend any existing 1-2-4-8 tail either with $1$, or with any of $2,4,8$. For example, tail of length 1000, consisting only of 1 and 2:

sage: k
615518781133550927510466866560333743905276469414384071264775976996005261582333424319169262744569107203933909361398767112744041716987032548389396865721149211989700277761744700088281526981978660685104481509534097152083798849174934153949598921020219299137483196605381824600377210207048355959118105502326334547495384673753323864726827644650703466356156319492521379682428275201262134907960967634887658195264018797348236155773958687977059474419550906257366056229915615067527218040720408353328787880060032847746927391316869927283585312014157952623949696812057481086276896651244409107902992111507870787820359137244857060839675634572294938878098506151681269336043213294287160464665102314138635395739226878089
sage: print pow(2, k, 10**1000)
1112221212111222212111211212211112121221111221112211221212222212222111211212111122221111222222211112222211112122111222122222212222111221111112211122121122221212111122212112211122121121212211211221122111111111111121211111211212222212112121222221221122111222221222222122212221212111121111112111211222111111211222222222112222212112211212121122212122222211111121112122122112112122222212121121222221112121221222221121122221121222121112111121221221212211121221122121122122122112112112111222212111111221121211211122222122211122211211222122122211112121121111211222211211212211112111212121212111222221212221211212222121122221211112222211221121221211211221222211112121221222122112122221221221221221222211122222222222222222222111121122221121121212111222211112122112112222112221212111112121221221121211221111121212111111121212222212211222122122212112211221221112222121221212121121112111222221122221221121111212121211211211221121211211121122122211212221112122111122212112212121112121121122111112111211111212122112
$\endgroup$
1
$\begingroup$

No value less than 2^30,000 bigger than 128 follows this pattern, as I have found through this tool:

http://www.michalpaszkiewicz.co.uk/maths/series/powers-of-two.html

You can use this tool to try and find such a value, but it would probably be easier to prove no such number exists using number theory.

$\endgroup$
2
  • 4
    $\begingroup$ The already-linked page at OEIS has your result put somewhat in the shade: "By looking at just the lowest 20 digits of the powers of 2, the Mathematica program shows that there are no other terms less than 2^10000000." $\endgroup$
    – AakashM
    Dec 9, 2014 at 10:56
  • $\begingroup$ You are right, should have read it properly! $\endgroup$ Dec 9, 2014 at 11:02
1
$\begingroup$

Every such number is of the form of a sum of f(n,m) = 2^n*10^m where m is an integer and n is 0,1,2,3. You can gain insight into this problem by writing this problem out in binary. Every power of two is a 1 followed by zeros, so 1, 10, 100, 1000 is 1,2,4,8 etc. So multiplying a binary by 2 adds a zero to the right. So lets look at powers of ten:

1 1010 1100100 1111101000 10011100010000

The key point to note is that they are followed by more and more trailing zeros. Lets assume this is true. I knows its true up to 10^22 or so, since its used in algorithms to do fast floating point arithmetic, see e.g. here: http://www.exploringbinary.com/why-powers-of-ten-up-to-10-to-the-22-are-exact-as-doubles/ .

EDIT - This is obviously true, since every power of ten is a power of two since 10 = 2*5. Thus ever power of 10^n must have exactly n trailing zeros. (Since powers of 5 are odd they must end in one.)

I can add up to three zeros (multiply by 8), but i cannot exclude any power of ten. So I have to sum these. Clearly I have to eliminate all the 1's. So to convert 100 to the next power of two I take 1100100 and clearly need to add 0011100 i.e. fill in all the zeros with 1's and put a final one in to make them carry like dominoes. This is similar to making a power of ten, work out what you add to make the number nines followed by zeros then add one to which ever column has the last non zero digit.

so can I make 11100 out of ten and one? yes, 10*2 = 10100 and 1*8 = 1000. So 128 is a perfect power.

Lets look at eliminating the 1s in the last two columns. Clearly all numbers of 100 or greater have no ones so don't matter, so I can have 12. I can also have 48. So any such number must end in 12, 28 or 48. Next try eliminating all the 1's in the last three columns. 128 = 10000 will do the job. So will 112 and 248, but thats it*. Lets follow the 112 chain. That will give us 2112 4112 8112 with 5 trailing zeros.

If we move to six trailing zeros we get 22112 42114 82112 14112 and 18112*. There are, around 1000 numbers with six trailing zeros under 10000. So if there is no deep structure, so we see that this form is extremely restrictive in terms of the sets that you can build.

Its even conceivable that an exhaustive search along these lines would lead to all the branches terminating - i.e. that you couldn't eliminate the last one's any further. In that case you would have proved the statement.

*I offer no guarantees that my inspection was exhaustive!

$\endgroup$
2
  • 1
    $\begingroup$ I don't see how binary is relevant to the question, nor the expression $2^n*10*m$, which is never a power of $2$, and can't seem to follow the logic here. Could you try to write it out as a proof or something really crisp like that - i.e. define terms and try to only do manipulations directly necessary to the point. $\endgroup$ Dec 13, 2014 at 0:18
  • 1
    $\begingroup$ It should be 2^n*10^m, sorry, typo. Clearly if a number in base ten has a power of 2 as every digit, its of that form, since e.g. 128 = 100 + 20 + 8 which is the sum of f(0,2)+f(1,1)+f(3,0) Binary is useful because every power of two, represented in binary, is a 1 followed by zeros. So adding binary numbers to reach a power of two is equivalent to eliminating all trailing ones from a number so to make 1100 into a power of two, you add 100, yielding 10000. So if there is ever a trailing one you cannot eliminate, then you cannot form a power of two. $\endgroup$
    – phil_20686
    Feb 4, 2015 at 12:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .