Tjyylli

I have reason(empirical calculations) to think the following statement is true:

For any $k in mathbb{N}$, there exist $s in mathbb{N}$ such that the expression

$$9*s+3+2^{k}$$

is a power of $2$.

To me it seems like a silly statement, but I don't know how I would go about proving it. Any ideas, or references?

THank you.

The statement that $9s + 3 + 2^k$ is a power of $2$ for some $sinBbb{N}$ is equivalent to saying $2^k + 3 equiv 2^n pmod 9$ for some $ngt k$. Since the values of $2^kbmod 9$ are the periodic sequence $1,2,4,8,7,5,1,2,4,8,7,5,ldots$ consisting of all values which are not multiples of $3$, this is true.

For example, take $k = 5$. Then $2^k + 3 = 35 equiv 8 pmod 9$ and the next power of $2$ which is congruent to $8$ is $2^9 = 512$. So in this case $s = (512 - 35)/9 = 53$.

$9cdot s+3+2^k=2^{j+k} Rightarrow 2^k(2^j-1)-3 equiv 0 mod 9 Rightarrow 2^k(2^j-1) equiv 3 mod 9$

$2^k mod 9$ cycles through $2,4,8,7,5,1,$ etc. so $2^j-1 mod 9$ cycles through $1,3,7,6,4,0$ etc.

For any residue of $2^k$ it is possible to find a residue of $2^j-1$ such that their product equals $3 mod 9$, viz: $2cdot 6; 4cdot 3; 8cdot 6; 7cdot 3; 5cdot 6; 1cdot 3$

So your observation is true.

NB As I typed this, I see that Fred H has given a similar answer.

Euler's Theorem tells us $2^6 equiv 1 pmod 9$ and direct calculation shows so

$2^{6k + i; i=0...5}equiv 1,2,4,8,7,5 pmod 9$.

So $2^m - 2^k equiv 3 pmod 9$ if

$kequiv 0 pmod 6;2^kequiv 1pmod 9$ and $mequiv 2pmod 6; 2^mequiv 4pmod 9$.

$kequiv 1 pmod 6;2^kequiv 2pmod 9$ and $mequiv 5pmod 6; 2^mequiv 5pmod 9$.

$kequiv 2 pmod 6;2^kequiv 4pmod 9$ and $mequiv 4pmod 6; 2^mequiv 7pmod 9$.

$kequiv 3 pmod 6;2^kequiv 8pmod 9$ and $mequiv 1pmod 6; 2^mequiv 2pmod 9$ (So $2^m - 2^k equiv 2-8equiv -6equiv 3 pmod 9$).

$kequiv 4 pmod 6;2^kequiv 7pmod 9$ and $mequiv 0pmod 6; 2^mequiv 1pmod 9$.

$kequiv 5 pmod 6;2^kequiv 5pmod 9$ and $mequiv 3pmod 6; 2^mequiv 9pmod 9$.

So for any $k$ there will exist infinitely many $m > k$ (Actually we don't need $m > k$ as $s$ may be negative but... nice answers are nicer) so that $2^m - 2^k equiv 3 pmod 9$.

So that means for any $k$ there will exist $s$ and $m$ (actually infinitely many $s$ and $m$) so that

$2^m - 2^k = 9s + 3$ or

$9s+3 + 2^k$ a power of $2$.

(I take a dog for a walk and three people post a similar to identical answer. sigh. Anyway hopefully this answer may (or may not) provide a possible fresh take... There's always more than one way to do or explain things.)

If $9s+3 = 3cdot 2^k$,
this will work.

Then
$3s+1 = 2^k$,
so $3|2^k-1$.

This works for even $k$.

More generally,
it works if
$9s+3 = (2^m-1)2^k$
for some $m$.

To get rid of the 3
requires $m$ even,
so write this as
$9s+3
= (4^m-1)2^k
= 3sum_{j=0}^{m-1}4^j2^k
$
or
$3s+1
= 2^ksum_{j=0}^{m-1}4^j
$.

Mod 3,
we want
$1
=2^ksum_{j=0}^{m-1}4^j
=2^km
$
so if
$2^km = 1 bmod 3$
we are done,
and this can always be done.

Suppose $k in mathbb{N} = mathbb{Z}_{>0}$ is given.

Set begin{align*}
s &= 2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) text{, and} \
n &= (-1)^{k+1} + k + 3 text{.}
end{align*}

Then $s$ and $n$ are positive integers and
$$ 9s + 3 + 2^k = 2^n text{.} $$

This looks like a job for induction, but we can show it directly.

The expression for $n$ is a sum of integers, so $n$ is an integer, and the value of the expression lies in $[k+3-1, k+3+1]$. Since $k > 0$, this entire interval contains only positive numbers, so $n$ is a positive integer.

For $s$, note that $(-2)^{k+1} - 1 cong 1^{k+1} - 1 cong 1 - 1 cong 0 pmod{3}$, so the division by $3$ yields an integer. We wish to ensure $s > 0$, so begin{align*}
2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) overset{?}{>} 0 \
2^k + frac{1}{3} left( (-1)^{k+1}2^{k+1} - 1 right) overset{?}{>} 0 \
1 + frac{1}{3} left( (-1)^{k+1}2^{1} - 2^{-k} right) overset{?}{>} 0
end{align*}
If $k$ is even, begin{align*}
1 + frac{1}{3} left( -2 - 2^{-k} right) overset{?}{>} 0 text{,}
end{align*}
$-2 -2^{-k} in (-3,-2)$, so $1 + frac{1}{3} left( -2 - 2^{-k} right) in (0,1/3)$, all elements of which are positive, so $s$ is positive when $k$ is even. If $k$ is odd, begin{align*}
1 + frac{1}{3} left( 2 - 2^{-k} right) overset{?}{>} 0 text{,}
end{align*}
$2 - 2^{-k} in (1,2)$, so $1 + frac{1}{3} left( 2 - 2^{-k} right) in (4/3, 5/3)$, all elements of which are positive, so $s$ is an integer when $k$ is odd. Therefore, $s$ is positive when $k$ is odd. Therefore, $s$ is always a positive integer.

Plugging in the above expressions into the given equation, we have
$$ 9 left( 2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) right) + 3 + 2^k = 2^{(-1)^{k+1} + k + 3} text{.} $$
After a little manipulation, this is
$$ 2^{(-1)^{k+1} + k + 2} = 5 cdot 2^k - 3(-2)^k text{.} tag{1} $$

First suppose $k$ is even, so $k = 2m$. Substituting this into (1) and simplifying a little, we have
$$ 2^{-1 + 2m + 2} = 2 cdot 2^{2m} text{,} $$
a tautology.

Then suppose $k$ is odd, so $k = 2m+1$. Sustituting this into (1) and simplifying a little, we have
$$ 2^{2m + 4} = 8 cdot 2^{2m+1} text{,} $$
a tautology.

Therefore, the given $s$ and $n$ are positive integers which satisfy the given equation.

Aside: The above choices for $s$ and $n$ do not exhaust the solution set. For instance $(k,s,n) = (2, 131,176,846,746,379,033,713, 70)$ is another solution. (This is implicit in the other answers that use the fact that the powers of $2$ are cyclic modulo $9$.)