6
$\begingroup$

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}$.)

$\endgroup$
6
  • $\begingroup$ Consider the equation modulo $2$ and $5$ ... should be easy to prove no such number can exist? $\endgroup$ – Donald Splutterwit Sep 30 '20 at 22:32
  • 1
    $\begingroup$ You can easily conclude that $a=c$. $\endgroup$ – rtybase Sep 30 '20 at 22:35
  • $\begingroup$ @DonaldSplutterwit Sorry, I don't understand how that helps. I know I can use modulo arithmetic to say: “there's no solution mod $n$, so there's no solution at all.” But for example, $2^1+2^3 \equiv 10^1+10^2$, both modulo 2 and 5. $\endgroup$ – Lynn Sep 30 '20 at 22:38
  • 1
    $\begingroup$ @rtybase I reached that conclusion too: rewriting it as $2^a(1+2^x) = 10^c(1+10^y)$ and comparing the prime factorizations. But I don't know where to go from there. $\endgroup$ – Lynn Sep 30 '20 at 22:42
  • $\begingroup$ So you have $2^a + 2^b= 10^a + 10^d \iff 10^a - 2^a = 2^b - 10^d$ and conclude that $a<b\leq d$ is not possible, since that will make $2^b - 10^d <0$. $\endgroup$ – rtybase Sep 30 '20 at 22:53
1
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ The problem is found on page 19 in the internal numbering (page 31 of the PDF). The solution begins on page 103 in the internal numbering (page 115 of the PDF). $\endgroup$ – Misha Lavrov Oct 1 '20 at 1:07
  • $\begingroup$ But I am skeptical that this actually solves the problem. The numbers $\underbrace{33\dots 33}_n$ and $\underbrace{66\dots 67}_n$ have sums of digits that go to infinity with $n$, but that certainly doesn't mean that the same is true of their sum. $\endgroup$ – Misha Lavrov Oct 1 '20 at 1:09
  • $\begingroup$ @MishaLavrov: I was saying "Schintzel's solution", not the problem 209 itself. He proved that if, say, $a>14$, then there are three non-zero digits. But in fact he proves a stronger statement. $\endgroup$ – Mark Sapir Oct 1 '20 at 1:10
  • $\begingroup$ Is there any chance you could spell out the argument to get from there to here? I'm not seeing it, sorry. $\endgroup$ – Misha Lavrov Oct 1 '20 at 2:13
  • $\begingroup$ I will post more details when I have time. $\endgroup$ – Mark Sapir Oct 1 '20 at 2:38
1
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ Your third equation has an error. $1+2^x > 1+10^y$, not the other way around. $\endgroup$ – Yly Oct 1 '20 at 1:03
  • $\begingroup$ @Yly Sorry about that -- should be fixed now. $\endgroup$ – Carl Schildkraut Oct 1 '20 at 1:59
  • $\begingroup$ Thanks for this proof! The only part I don't understand is: How did you get $1\equiv 5^a\bmod 2^y$? $\endgroup$ – Deadcode Apr 4 at 23:50
1
$\begingroup$

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.

$\endgroup$

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.