Is there a solution to $2^a+2^b = 10^c+10^d$, with $0 \leq a < b$ and $0 \leq c < d$?

231 Views Asked by At

This question arose on the code golf StackExchange:

Is there a solution to $2^a+2^b = 10^c+10^d$, with $0 \leq a < b$ and $0 \leq c < d$?

In other terms: is there an integer that looks like $\color{blue}{1000...001000...}$ in both binary and decimal?

I feel like there probably isn't, but I can't think of a simple counterargument.

(A computer search by one of the commenters suggests there is no such integer up to $10^{100000}$.)

3

There are 3 best solutions below

5
On

The question asks if the sum of decimal digits of $2^a+2^b$ ($a<b$) can be equal to $2$. The Schinzel solution of problem 209 here shows that $a,b$ should be relatively small, certainly $<100$.

4
On

For a prime $p$, let $\nu_p(n)$ denote the exponent of $p$ in the prime factorization of $n$. We will use the Lifting the Exponent lemma.

Firstly, note that $$a=\nu_2(2^a+2^b)=\nu_2(10^c+10^d)=c,$$ so we have $2^a+2^b=10^a+10^d$. Let $b=a+x$ and $d=a+y$, and write $$1+2^x=5^a(1+10^y).\tag{1}\label{eq1}$$ We observe that $$2^b<2^a+2^b<2\cdot 10^d\implies a+x< 1+(a+y)\log_2(10)<1+\frac 72a+\frac 72y,$$ so $x<1+\frac 52a+\frac 72y$, and $$2^a+2^{a+x}=10^a+10^{a+y}\implies 2^{a+x}>10^{a+y}\implies a+x>a+y\implies x>y.$$ We see that, from (*), $$5^a|1+2^x|2^{4x}-1\implies a\leq \nu_5(2^{4x}-1)=1+\nu_5(x).$$ On the other hand, looking at powers of $2$, we see that, modding out by $2^y$, $$1\equiv 5^a\bmod 2^y,$$ which implies that $$y\leq \nu_2(5^a-1)=1+\nu_2(a).$$ We now have the inequalities $$y\leq 1+\nu_2(a),\ \ a\leq 1+\nu_5(x),\ \ x<1+\frac 52a+\frac 72y.$$ Since the functions on the right sides of the first two inequalities are very small, this is basically enough to finish -- we just need to actually carry out the bounding. We note that $$\nu_p(x)\leq \log_p(x)=1+\log_p\left(\frac xp\right)<1+\frac{x}{p}.$$ As a result, $$y<2+\frac{a}{2},\ a<2+\frac{x}{5},\ x<1+\frac 52a+\frac 72y.$$ This gives $$a<2+\frac{2+5a+7y}{10}<2+\frac{2+5a}{10}+\frac{7}{10}\left(2+\frac a2\right)=\frac{18}5+\frac{17a}{20},$$ which gives that $a<24$. In addition, we have $y<2+a/2=14$ and $x<110$, so this is just a finite case check (which it seems like one of the commenters has performed to a satisfactory bound).

0
On

NOT AN ANSWER. Commentary too long to fit in a Comment

  1. The equation: $2^a+2^b=10^c+10^d;\ 0\le a<b,\ 0\le c<d$. If $b>a,\ d>c$ were not already stated, it is provable that $a\ne b,\ c\ne d$ from which we could validly assume WLOG $b>a,\ d>c$.

  2. Although $a=0$ and $c=0$ are contemplated by the question as stated, neither $a$ nor $c$ can actually be $0$. If only one of them is, then we have an odd sum equal to an even sum. If both of them are, then by subtracting $1$ from each side we obtain $2^b=10^d$ which is impossible.

  3. $b-a=4k-2$. This follows from $2^a+2^b\equiv 0 \bmod 5$. Positive integer powers of $2$ modulo $5$ cycle in order through $2,4,3,1$. Sums of powers of $2$ that are $\equiv 0 \bmod 5$ arise from $2^{4m+1}+2^{4n+3}\text{ or }2^{4m}+2^{4n+2}$, and the differences of the exponents have the stated form.

  4. $a=c$. The original equation can be rearranged to $2^a(2^{b-a}+1)=2^c5^c(10^{d-c}+1)$. Plainly, there are $a$ factors of $2$ on the LHS and $c$ factors of $2$ on the RHS, so $a=c$.

  5. $a$ is even. From point 4 we obtain $2^a+2^b=10^a+10^d \Rightarrow 1+2^{b-a}=5^a(1+10^{d-a})$. We look at this equation $\bmod 3$. $1+2^{b-a}\not \equiv 1 \bmod 3$, and $(1+10^{d-a})\equiv 2 \bmod 3$. This requires $5^a \not \equiv 2 \bmod 3$ which in turn requires $a$ is even. This impacts point 3 by restricting the exponents to $(a,b)=(4m,4n+2)$ up to order. So $b$ is also even.

  6. $d$ is even. From points 4 and 5, $c$ is even. $10\equiv -1 \bmod 11$ so $10^c+10^d \equiv 1+(-1)^d \equiv 0,2 \bmod 11$; $0$ if $d$ is odd and $2$ if $d$ is even. $2^{4m}+2^{4n+2}\not \equiv 0 \bmod 11$. There are instances where $2^{4m}+2^{4n+2} \equiv 2 \bmod 11$. So if there are solutions to the equation, $d$ is even.

This is as far as I have gotten; I will update if I get further.