0
$\begingroup$

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

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

$\endgroup$
5
$\begingroup$

The statement that $9s + 3 + 2^k$ is a power of $2$ for some $s\in\Bbb{N}$ is equivalent to saying $2^k + 3 \equiv 2^n \pmod 9$ for some $n\gt k$. Since the values of $2^k\bmod 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$.

$\endgroup$
  • $\begingroup$ Thank you all for the replies. I will choose this one as the answer as I find it the most concise and illuminating. Different approaches, such as Eric's down below are welcomed. $\endgroup$ – ReverseFlow Mar 31 at 6:18
2
$\begingroup$

$9\cdot 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: $2\cdot 6;\ 4\cdot 3;\ 8\cdot 6;\ 7\cdot 3;\ 5\cdot 6;\ 1\cdot 3$

So your observation is true.

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

$\endgroup$
2
$\begingroup$

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

$k\equiv 0 \pmod 6;2^k\equiv 1\pmod 9$ and $m\equiv 2\pmod 6; 2^m\equiv 4\pmod 9$.

$k\equiv 1 \pmod 6;2^k\equiv 2\pmod 9$ and $m\equiv 5\pmod 6; 2^m\equiv 5\pmod 9$.

$k\equiv 2 \pmod 6;2^k\equiv 4\pmod 9$ and $m\equiv 4\pmod 6; 2^m\equiv 7\pmod 9$.

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

$k\equiv 4 \pmod 6;2^k\equiv 7\pmod 9$ and $m\equiv 0\pmod 6; 2^m\equiv 1\pmod 9$.

$k\equiv 5 \pmod 6;2^k\equiv 5\pmod 9$ and $m\equiv 3\pmod 6; 2^m\equiv 9\pmod 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.)

$\endgroup$
1
$\begingroup$

If $9s+3 = 3\cdot 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 = 3\sum_{j=0}^{m-1}4^j2^k $ or $3s+1 = 2^k\sum_{j=0}^{m-1}4^j $.

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

$\endgroup$
1
$\begingroup$

$$ \begin{array}{c} \boldsymbol{\large 2^k+3\equiv2^m\pmod9}\\ \begin{array}{c|c|c} k\bmod6&2^k+3\bmod9&2^k\bmod9&m\bmod6\\\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 \end{array} \end{array} $$ Since $\phi(9)=6$, Euler's Theorem says that $2^6\equiv1\pmod9$; therefore, if we know $k\bmod6$, we know $2^k\bmod9$. 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+3\equiv2^m\pmod9 $$ For example, $2^{10}+3\equiv2^{12}\pmod{9}$ because, from the table, $k=10\equiv4\pmod6$ and so $m=12\equiv0\pmod6$, so we can compute $s=\frac{2^{12}-2^{10}-3}9=341$ to get $2^{10}+3+9\cdot341=2^{12}$.

$\endgroup$
  • $\begingroup$ More words around that table would be incredibly useful. What does k mod 6 tell us, and what do the colors mean? $\endgroup$ – ReverseFlow Mar 31 at 8:35
  • 1
    $\begingroup$ @ReverseFlow: I have replaced the colors with a verbal description. $\endgroup$ – robjohn Mar 31 at 9:02
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I get the feeling you are an analyst. :). Thank you for taking the time to write this, though I admit the other solutions are easier to digest. $\endgroup$ – ReverseFlow Mar 31 at 6:14

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.