11
$\begingroup$

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?

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

1 Answer 1

22
$\begingroup$

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)

$\endgroup$

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.