MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In thinking about a MathOverflow question pertaining to numbers whose decimal and binary digit sums are equal, I found myself asking:

Are there any solutions in non-negative integers $(a,b,c,d)$ to the equation

$$2^a + 2^b = 10^c + 10^d$$

aside from the trivial solution $(0,0,0,0)$ and the nontrivial solutions $(2,4,1,1)$ and $(4,2,1,1)$?

(This is, in effect, the case $s=2$ to the other MO question regarding which numbers $s$ can be a simultaneous binary and decimal digit sum and if so, how often. It seems likely that 20 is the only number whose digit sums are both 2, but that's basically what I'm asking here.)

In searching for other solutions, we may as well assume, for the sake of simplicity, that $a\le b$ and $c\le d$. It's quickly clear that we can restrict to looking for positive solutions, and we can also dismiss the possibility that $a=b$. That is, we can assume $0\lt a\lt b$ and $0\lt c \le d$.

The possibility that $c=d\ne 1$ is ruled out by Mihăilescu's proof of Catalan's conjecture: If $2^a + 2^b = 2\cdot10^c = 2^{c+1}\cdot5^c$ (with $a\lt b$) we necessarily have $a=c+1$, leaving the equation $1 = 5^c - 2^n$, where $n=b-a$, whose only solution is $c=1$, $n=2$. (Aside: We don't actually need to invoke Catalan's conjecture. See below.)

If now we restrict to $c\lt d$, it's immediately clear that we must have $a=c$. After writing $n=b-a$ (as before) and $m=d-c$ and doing a little factoring, the problem reduces to what I take to be the core question:

Does the equation

$$1+2^n = 5^a(1+10^m)$$

have any solutions in positive integers $(a,m,n)$?

This is as far as I've gotten in any meaningful sense. The question is obviously related to the Cunningham project. It's easy to see that $a>0$ implies $n\equiv2\mod4$, so the aurifeuillian factorization

$$2^{4k+2}+1 = (2^{2k+1}-2^{k+1}+1)(2^{2k+1}+2^{k+1}+1)$$

may or may not help. (It does help avoid the use of invocation of Catalan's conjecture above: Only one aurifeuillian factor is divisible by 5.) It's also easy to see that

$$n\log2 + \log(1+1/2^n) = a\log5 + m\log10 + \log(1+1/10^m)$$


$$(a+m)\log5 \approx (n-m)\log2$$

if $m$ and $n$ are large. Finally, writing $5^a = (1+4)^a = 1+4a+16{a\choose2}+\cdots$, it may be possible to say something useful about the relationship of $a$ to $n$, but I don't see what.

share|cite|improve this question
$a$ is determined by $n$ because $a$ is the $5$-adic valuation of $2^n+1$. More precisely, $2$ is a primitive root mod $5^t$ for all $t\geq1$ so $5^t$ divides $2^n+1$ iff $2^n=-1=2^{2.5^{t-1}}$ mod $5^t$ iff $n$ is congruent to $2.5^{t-1}$ mod $4.5^{t-1}$, so $a$ is the largest value of $t$ for which that's true. Basically $n$ has to be 2 mod 4 for $a>0$ and then $a$ is one plus the number of times 5 goes into $n$, if I got it right. – user30035 Apr 2 '13 at 17:46
[I'm not suggesting this helps, I'm just answering the implicit question in your last sentence.] – user30035 Apr 2 '13 at 17:47
up vote 11 down vote accepted

There's an elementary way of solving this (and similar equations). Let's start with $$ 1+2^n=5^a(1+10^m) $$ which you want to solve in positive integers $n$, $a$, $m$. Clearly $m < n$ and $a < n$. As wccanard points out, $2$ is a primitive root modulo $5^a$ and so we obtain that $n$ is divisible by $2 \cdot 5^{a-1}$. In particular, $$ 2 \cdot 5^{a-1} \le n. $$ Now let's use the fact that $m < n$ are reduce the equation modulo $2^m$. We obtain, $$ 5^a \equiv 1 \pmod{2^m}. $$ As in your question you write this as $$ 4a + 16 \binom{a}{2}+\cdots \equiv 0 \pmod{2^m}. $$ This implies that $2^{m-2} \mid a$, and so $$ 2^{m-2} \le a. $$ The inequalities we now have show that the left-hand side of the equation is much bigger than the right-hand side as soon as the $n$ is large!

Appended by the OP: With apologies to Samir if he had something slicker in mind, I thought I'd add my own elaboration on when $(1+2^n)$ becomes bigger than $5^a(1+10^m)$.

The first displayed inequality implies $5^a \le (5/2)n$ and the second, combined with $a \lt n$, gives $2^m \le 4a < 4n.$ Clearly, $1+10^m \lt 16^m = (2^m)^4\lt (4n)^4$. This all gives

$$2^n \lt 1+2^n = 5^a(1+10^m) \lt (5/2)n(4n)^4 = 640n^5,$$

and it's easy to check that this implies $n\lt 35$.

Knowing also that $n$ must be congruent to 2 mod 4 means we can finish the problem off by checking the factorizations of $1+2^n$ for $n=2,6,10,14,18,22,26,30,$ and $34$, which is easy enough to do. A less crude estimate than $1+10^m \lt 16^m$ might shave off a few of the larger values of $n$, but it doesn't seem worth the effort.

share|cite|improve this answer
Blast you and your sensible elementary arguments! Surely it's better to use an unnecessarily big hammer.... – Mike Bennett Apr 3 '13 at 3:07
@Samir, this is great. But can you be a little more specific as to the size of $n$ when the equation can no longer hold? Presumably this would leave a (small?) number of cases to be checked. – Barry Cipra Apr 3 '13 at 4:03

The short answer is "no". One can apply lower bounds for linear forms in $p$-adic ($p=2$ and $5$ here) and complex logarithms, and then argue somewhat carefully. The idea behind solving such $4$-term $S$-unit equations (with the cardinality of $S$ small) effectively goes back to Paul Vojta's thesis and has subsequently appeared in papers of Skinner (written when he was approximately $11$ as I recall) and of Tijdeman with various coauthors.

share|cite|improve this answer

Your Answer


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.