# Number of 1's in binary expansion of $a_n = \frac{2^{\varphi(3^n)}-1}{3^n}$

My question is about the Hamming Weight (or number of 1's in binary expansion) of $$a_n = \frac{2^{\varphi(3^n)}-1}{3^n}$$ A152007

For example, $$a_3 = 9709 = (10110111101001)_2$$ has nine 1's in binary expansion

I guess the answer is $$3^{(n-1)}$$ but I can't prove it

Is that correct?

• Verified up to $n=17$ (CoCalc didn't let me check higher). It is a very intriguing result if it holds in general. Jun 27, 2021 at 22:36

It is, indeed, correct. Notice first that $$2-(-1)=3$$ is divisible by $$3$$, so by lifting-the-exponent lemma the number $$A=\frac{2^{3^{n-1}}-(-1)^{3^{n-1}}}{3^n}=\frac{2^{3^{n-1}}+1}{3^n}$$ is an integer. Notice also that for $$n>0$$ it has less than $$3^{n-1}$$ binary digits. Assume that it has $$m$$ binary digits. We have $$\frac{2^{\varphi(3^{n})}-1}{3^n}=\frac{2^{2\cdot 3^{n-1}}-1}{3^n}=A(2^{3^{n-1}}-1).$$ Next, let $$l=3^{n-1}-m$$, $$B=2^l-1$$ and $$C=2^m-A$$. We claim that your number's binary expansion looks like a concatenation of $$A-1$$, $$B$$ and $$C$$, where we also add some zeros in expansion of $$C$$ until we get exactly $$m$$ digits. So, we should have $$a_n=C+2^mB+2^{m+l}(A-1).$$ This equality is true, because $$C+2^mB+2^{m+l}(A-1)=2^m-A+2^m(2^l-1)+2^{m+l}(A-1)=$$ $$=(A-1)(2^{m+l}-1)+2^{m+l}-1=A(2^{m+l}-1)=A(2^{3^{n-1}}-1).$$ Now, if the sum of digits of $$A-1$$ is equal to $$s$$, then the sum of digits of $$C$$ is $$m-s$$ and the sum of digits of $$B$$ is, of course, $$l$$, so the sum of digits of $$a_n$$ is $$s+m-s+l=m+l=3^{n-1},$$ as needed.

For the particular case $$n=3$$, described in the post, $$A=10011_2=19=\frac{2^9+1}{27}$$ and $$C=2^5-A=13=01101_2$$ (notice the added zero)