10
$\begingroup$

I asked this question at Mathematics Stack Exchange but since I didn't got a satisfactory answer I decided to ask it here as well.

We write a power of 3 in bits in binary representation as follows. For example $3=(11)$, $3^2=(1001)$ which means that we let the $k$-th bit from the right be $1$ if the binary representation of this power of 3 contains $2^{k-1}$, and $0$ otherwise.

  1. Prove that the highest power of 3 that has a palindromic binary representation is $3^3 = (11011)$.

  2. Prove that $3 = (11)$ is the only power of 3 with a periodic binary representation (in the sense that it consists of a finite sequence of $1$s and $0$s repeated two or more times, like "$11$" consists of two repetitions of the bitstring "$1$").

$\endgroup$
5
  • $\begingroup$ computer checking $\endgroup$ Mar 27, 2012 at 18:10
  • 1
    $\begingroup$ Once 1 is established, 2 follows pretty easily. You might try showing that powers of 3 mod some higher power of 2 provide a block towards being a palindrome. Gerhard "Ask Me About System Design" Paseman, 2012.03.27 $\endgroup$ Mar 27, 2012 at 18:12
  • $\begingroup$ @Gerhard: how knowing the last few letters of a word you can prevent the word from being a palindrome? $\endgroup$
    – user6976
    Mar 27, 2012 at 21:21
  • $\begingroup$ I don't know how. There is some literature on how close a power of 3 can be to a power of two, but I am unfamiliar with it. The only other idea I have is to consider factors of 2^k + 1, and consider certain combinations of those, but that looks even less likely of an in. Gerhard "Ask Me About System Design" Paseman, 2012.03.27 $\endgroup$ Mar 28, 2012 at 3:10
  • $\begingroup$ I'm going to leave the following nice fact here as there's a non zero chance it's related to the proof of 1 above: Let $f:\Bbb N\to\omega^{<\omega}$ send a natural number to the lengths of consecutive ones and zeroes in its representation, e.g. $f(27)=f(11011_2)=(2,1,2)$ then it can be proven that the representation of the periodic string of $-3^{-n}\in\Bbb Z_2$ is of period $2$ for all $n\in\Bbb N$. For example $-\frac1{27}=\overline{000010010111101101}_2\mapsto(\overline{4,1,2,1,1,\text{ }\color{red}{4,1,2,1,1}})$ $\endgroup$ Oct 22, 2019 at 13:06

2 Answers 2

5
$\begingroup$

Here is an extended hint for proving 2 (an almost complete proof is in the Update below). If $3^s$ base 2 is periodic, then you can represent it as $u(1+2^m+2^{2m}+...+2^{(t-1)m})=u\frac{2^{tm}-1}{2^m-1}$ for some numbers $u,m,t$. Therefore if $q_n(x)$ denotes the $n$-th cyclotomic polynomial, then $q_{tm}(2)$ must be a power of 3 (as a divisor of $3^s$). But it looks like $q_n(2)$ is never 0 modulo 9 (this should be possible to prove rigorously but I do not have time). Hence $q_{tm}(2)$ must be equal to 3 or 1 which gives a bound on $s$.

Update Since $2^m-1=0 \mod 9$ only when $m=0 \mod 6$. it is enough to consider $q_{6k}(2)$. Since $2^3=-1 \mod 9$, we only need remainders of cyclotomic polynomials modulo $x^3+1$ with coefficients modulo 9. Here are all 50 of them $$ \begin{array}{l} 1,3,{x}^{2},8x,8{x}^{2},1+8x,5+5{x}^{2},x+1,x+8,x+8 {x}^{2},\\\ 4x+5{x}^{2},{x}^{2}+1,1+8{x}^{2}+8x,2+3x+2{x}^{2}, 2+5x+4{x}^{2},2+8x+{x}^{2},2+{x}^{2}+7x,\\\ 2+2{x}^{2}+8x,2+6 {x}^{2}+7x,3+x+8{x}^{2},3+5x+3{x}^{2},\\\ 3+6x+2{x}^{2},3+2 {x}^{2}+7x,4+6x+3{x}^{2},4+7x+4{x}^{2},4+2{x}^{2}+5x,4 +3{x}^{2}+5x,\\\ 4+4{x}^{2}+6x,5+2x+7{x}^{2},5+4x+4{x}^{2} ,5+4{x}^{2}+5x, \\\ 6+2x+6{x}^{2}, \\\ 6+4x+5{x}^{2},6+7x+2{x}^{ 2},6+5{x}^{2}+3x,6+6{x}^{2}+4x,\\\ 6+7{x}^{2}+3x,7+2x+6{x} ^{2},7+4x+7{x}^{2},\\\ 7+6{x}^{2}+3x,8+2x+7{x}^{2},8+6x+8{ x}^{2},8+8x+{x}^{2}, \\\ 8+7{x}^{2}+x,8+8{x}^{2}+2x,{x}^{2}+x+1,{x} ^{2}+8x+1 \end{array}$$ None of these polynomials become 0 when evaluated at $2 \mod 9$.

As for the last claim about the size of $q_{mt}(2)$: every root of the cyclotomic polynomial is on the unit circle, so the values at 2 grow with the degree.

This almost completes the proof of 2 (one needs to show that the set of 50 polynomials is complete, but that can be done by induction).

$\endgroup$
5
$\begingroup$

Here is an alternative (and complete) proof of 2. Following Mark Sapir, we show that the only solution of $$ \frac{2^{tm}-1}{2^m-1} = 3^r $$ in positive integer triplets $(t,m,r)$ is $(2,1,1)$ and $(2,3,2)$. I am sure this was written down before, by the way.

Our main tool is the observation that $\mathrm{ord}_{3^n}(4)=3^{n-1}$ when $n\geq 1$ (in other words $2$ is a primitive root modulo $3^n$), which implies that $v_3(4^k-1)=1+v_3(k)$. The observation follows from $4^{3^{n-2}}\equiv 1+3^{n-1}\pmod{3^n}$ when $n\geq 2$, which in turn can be proved by induction or by the binomial theorem.

In the diophantine equation $r\geq 1$, hence $tm$ is even. If $m$ is even, then $$ r=v_3\left (\frac{2^{tm}-1}{2^m-1}\right)=(1+v_3(tm))-(1+v_3(m))=v_3(t), $$ so that $t$ is divisible by $3^r$. This is a contradiction: $$ 3^r=\frac{2^{tm}-1}{2^m-1} > t \geq 3^r, $$ which proves that $m$ is odd and $t$ is even. In that case $4^m-1\mid 2^{tm}-1$, and $$ \frac{2^{tm}-1}{4^m-1} = 3^s $$ for some $0\leq s\leq r$. As before $$ s=v_3\left (\frac{2^{tm}-1}{4^m-1}\right)=(1+v_3(tm))-(1+v_3(m))=v_3(t), $$ so that $t$ is divisible by $3^s$. This is a contradiction when $t\geq 4$: $$ 3^s=\frac{2^{tm}-1}{4^m-1} > 4(t/2-1)\geq t \geq 3^s, $$ which proves that $t=2$. Now the original diophantine equation becomes $$ 2^m+1=3^r,$$ where $m$ is odd. Then $1+v_3(m)=v_3(4^m-1)=r$, so that $m$ is divisible by $3^{r-1}$. It follows that $1+2^{3^{r-1}}\leq 3^r$. It is easy to see that this holds only for $r=1$ and $r=2$, which yields $m=1$ and $m=3$, respectively.

$\endgroup$
2
  • 4
    $\begingroup$ Alternatively, one can shorten the analysis using the following theorem of Bang: $2^n-1$ has a primitive prime divisor except for $n=1$ and $n=6$. $\endgroup$
    – Anonymous
    Mar 28, 2012 at 4:40
  • $\begingroup$ @Anonymous: Thanks for the very relevant comment! $\endgroup$
    – GH from MO
    Mar 28, 2012 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.