Number Theory - How to solve equations like this?

Question

$$\mathbf {n = 2^i + 5^j \quad\forall\;i,j\in \{0\}\cup Z^+}$$

I want to find all the n that satisfies this constraint within some interval say $\mathbf{[\alpha,\;\beta]}$ where $\alpha\;and\;\beta$ are some integers.

Answer 1

You can just search. The greatest $j$ can be is $\lfloor \log_5 \beta \rfloor$. For that $j$ the largest $i$ can be is $\lfloor \log_2(\beta -5^j)\rfloor$ and the smallest is $\max (0,\lceil \log_2(\alpha-5^j)\rceil)$ Now just count downward from the highest $j$, finding the range of $i$ for each. Keep a list of the $n$s you find. Sort it at the end, if you want.

Answer 2

You can only do it by trial and error.

Bear with me.

First of $2|n$ or $5|n$ then $i$ or $j$ (respectively) must be $0$. And that will only have solutions if $n-1$ equals $5^j$ or $2^i$ (respectively).

Otherwise

Let $n \equiv k \mod 5$.

Then we need $2^i \equiv k \mod 5$. Precisely one value of $m = 0, 1,2,3,$ or $4$ will be such that $2^m \equiv k \mod 5$ and $2^4 \equiv 1 \mod 5$.

So we will just check all the values $i = 4v + m$ where $m \le 4v + m \le \log_2 n$.

Then we check whether $n- 2^i$ is a power of $5$.

So for example if $n = 11317$

$11317 \equiv 2 \mod 5$ and $2^1 \equiv 2 \mod 5$ so we only need to check $2,2^5, 2^9, etc.$

$11317- 2 = 11315$ and $11315$ and .....

Okay you know what. I can "eyeball" multiples of $25=5^2$ and that will have a lot fewer things to check.

$11317 - 5 = 11312$ which is not a power of $2$ so if there is any solution $j \ge 2$.

$11317\equiv 17 \mod 25$ and $2^{20}\equiv 1 \mod 25$ and one of $2^{1 + 4m} \equiv 17 \mod 25$

$2^5 =16*2\equiv 32\equiv 7; 2^9\equiv 16*7 \equiv 112 \equiv 12;2^{13} \equiv 16*12 \equiv 32*6\equiv 7*6\equiv 42\equiv 17$. So $i \equiv 13 \mod 20$.

$11317 - 2^{13} = 11317 - 8192 =3125$ which may be a power of $5$. $3125 = 25*125 = 5^5$ so $11317 = 2^{13} + 5^5$.

And $\log_2 11317 =\frac {\ln 11317}{\ln 2} = 13.46... $ so we don't need to check any further.