Otdfbt

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

For any $k in mathbbN$, there exist $s in mathbbN$ such that the expression

$$9s+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 $sinBbbN$ 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...5equiv 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-14^j2^k
$
or
$3s+1
= 2^ksum_j=0^m-14^j
$.

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

$$
beginarrayc
boldsymbollarge 2^k+3equiv2^mpmod9\
beginarrayc
kbmod6&2^k+3bmod9&2^kbmod9&mbmod6\hline
0&4&1&2\
1&5&2&5\
2&7&4&4\
3&2&8&1\
4&1&7&0\
5&8&5&3
endarray
endarray
$$
Since $phi(9)=6$, Euler's Theorem says that $2^6equiv1pmod9$; therefore, if we know $kbmod6$, we know $2^kbmod9$. Thus, we can compute columns $2$ and $3$ mod $9$ from column $1$. To compute column $4$ for row $A$, read column $2$ from row $A$, and find that value in column $3$ of row $B$ and read the value in column $1$ from row $B$ and put that value in column $4$ of row $A$. Then, for each row,
$$
2^k+3equiv2^mpmod9
$$
For example, $2^10+3equiv2^12pmod9$ because, from the table, $k=10equiv4pmod6$ and so $m=12equiv0pmod6$, so we can compute $s=frac2^12-2^10-39=341$ to get $2^10+3+9cdot341=2^12$.

Suppose $k in mathbbN = mathbbZ_>0$ is given.

Set beginalign*
s &= 2^k + frac13 left( (-2)^k+1 - 1 right) text, and \
n &= (-1)^k+1 + k + 3 text.
endalign*

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 pmod3$, so the division by $3$ yields an integer. We wish to ensure $s > 0$, so beginalign*
2^k + frac13 left( (-2)^k+1 - 1 right) overset?> 0 \
2^k + frac13 left( (-1)^k+12^k+1 - 1 right) overset?> 0 \
1 + frac13 left( (-1)^k+12^1 - 2^-k right) overset?> 0
endalign*
If $k$ is even, beginalign*
1 + frac13 left( -2 - 2^-k right) overset?> 0 text,
endalign*
$-2 -2^-k in (-3,-2)$, so $1 + frac13 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, beginalign*
1 + frac13 left( 2 - 2^-k right) overset?> 0 text,
endalign*
$2 - 2^-k in (1,2)$, so $1 + frac13 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 + frac13 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. tag1 $$

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