Are all zeros of $g(n)$ one less than a power of 2?

Question

$f(n)$ is defined such that if $n = 2$, $f(n) = 1$, if $n$ is prime and $1$ more than a multiple of $4$, $f(n) = 1$, if $n$ is prime and $3$ more than a multiple of $4$, $f(n) = -1$, and if $n$ is composite,

$$f(n) = f(a_1),f(a_2),f(a_3),\cdots,f(a_m)$$

, where $a_1,a_2,\cdots,a_m$ are the prime factors of $n$. $g(x)$ is defined such that

$$g(n) = f(2) + f(3) + f(4) + \cdots + f(n)$$

I have written a python program that checks all integers from $2$ to $5000$ for $n$-values where $g(n) \le 0$, and the program found that there were no $n$-values where $g(n)$ was negative, and the $n$-values where $g(n)$ was $0$ were $3$, $7$, $15$, $31$, $63$, $127$, $255$, $511$, $1023$, $2047$, and $4095$. However, I am aware that this is not a proof that the only zeros of $g(n)$ are one less than a power of $2$.

You can get a vertically centred ellipsis with proper spacing to surrounding binary operators like $+$ using \cdots. — joriki, Apr 18 '20 at 18:30
@joriki Er, no? $21$ is not writable in this manner, yet $f(21)=1$... — Parcly Taxel, Apr 18 '20 at 18:43
@ParclyTaxel: You're right. It's the total number of prime factors $\equiv3\bmod4$ that's even if $f(n)=1$, whereas for the two-squares property the number of factors of each such prime must be even. — joriki, Apr 18 '20 at 18:52
Your $g(n)$ is OEIS sequence A037834. Your $f(n)$ is OEIS sequence A112347. — Somos, Apr 18 '20 at 18:59
This is quite suprising (to me). How did you come up with this? (I've checked it up to $2^{26}$.) — joriki, Apr 18 '20 at 19:36

score 1 · Answer 1 · answered Apr 18 '20 at 20:13

$f(n)=-1$ iff an odd number of the prime factors of $n$ are of the form $4k+3$ iff $n=2^m(4k+3)$ for some $m,k\ge0$.

Now, for an arbitrary $N$ and $n=2,3,\dots,N$, write an opening bracket $(_n$ if $f(n)=1$ and a closing bracket $)_n$ if $f(n)=-1$. If $)_{2^m(4k+3)}$ is written, $(_{2^m(4k+1)}$ must have been written before it, and we pair these brackets – except $)_3$ which we pair with $(_a$ where $a$ is the highest power of $2$ less than $N$. All closing brackets up to $N$ can be paired like this, which proves $g(n)\ge0$ for all $n\ge2$.

Suppose $N$ is not of the form $2^s-1$. Consider the leftmost $10$ in its binary representation, e.g. $$1\underline{10}1101011$$ Change this to $01$ and all bits to its right to $0$: $$1\underline{01}0000000$$ This number $M$ is smaller than $N$ and is of the form $2^m(4k+1)$. $M$'s bracket is paired with the closing bracket of a number greater than $N$ (replace the underlined $01$ in $M$ by $11$). Hence $(_M$ is unpaired and $g(N)>0$.

But going from an opening bracket to its paired closing bracket does not increase the bitsize of the underlying numbers. Thus, if $N=2^s-1$, the opening brackets of all numbers less than $N$ can be successfully paired with the closing brackets of all numbers less than or equal to $N$ using the scheme described in the second paragraph of this answer, which shows $g(N)=0$ in this case.

In summary, $g(n)\ge0$ for all $n\ge2$, and $g(n)=0$ iff $n$ is a Mersenne number.

Are all zeros of $g(n)$ one less than a power of 2?

1 Answers1