Return to Answer

Claim: $p_{n,j}(1)$ vanishes modulo $2$ if and only there is a carry when adding $j$ and $n+1-j$ in base-$2$.

Proof: Let us write $x^n+1 \equiv x^n-1= \prod_{d \mid n} \Phi_d(x)$ where $\Phi_d$ is the $d$th cyclotomic polynomial. Then, since there are $\lfloor m/d\rfloor$ multiplies of $d$ in $\{1,2,\ldots,m\}$, $$p_{n,j}(x) = \prod_{d=2}^{n} \Phi_d(x)^{\lfloor \frac{n+1}{d} \rfloor- \lfloor \frac{j}{d}\rfloor - \lfloor \frac{n-j+1}{d}\rfloor }.$$ The value of $\Phi_d(x)$ at $x=1$ is well-understood. One can use the property $x^n-1= \prod_{d \mid n} \Phi_d(x)$ to show $\Phi_d(1)$ is $1$ unless $d$ is a prime power $p^k$ in which case $\Phi_d(1)=p$ (this is classical, see here for proofs). This implies $$p_{n,j}(1) \equiv \prod_{p^k \le n} p^{\lfloor \frac{n+1}{p^k} \rfloor- \lfloor \frac{j}{p^k}\rfloor - \lfloor \frac{n-j+1}{p^k}\rfloor }.$$ Since $2$ is the only even prime, $$p_{n,j}(1) \equiv \prod_{2^k \le n} 2^{\lfloor \frac{n+1}{2^k} \rfloor- \lfloor \frac{j}{2^k}\rfloor - \lfloor \frac{n-j+1}{2^k}\rfloor }.$$ So your expression vanishes modulo $2$ if and only if $$ \sum_{2 \le 2^k \le n} \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor\ge 1.$$

Let us express this criterion using base-$2$ representation. If $j = \sum_{i \ge 0} a_i 2^i$, $n-j+1 = \sum_{i \ge 0} b_i 2^i$ and $n+1 = \sum_{i \ge 0} c_i 2^i$ then $$ \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor =\sum_{i \ge k} (c_i-a_i-b_i) 2^{i-k} $$ so that $$\begin{align} \sum_{2 \le 2^k \le n} \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor &= \sum_{i \ge 0} (c_i-a_i-b_i)(2^{i-1}+2^{i-2}+\ldots+1) \\ &= \sum_{i \ge 0} (c_i-a_i-b_i)(2^{i}-1)\\ &= n+1 - (j + (n+1-j)) - \sum_{i \ge 0} (c_i-a_i-b_i)\\ &= \sum_{i \ge 0} (a_i+b_i-c_i). \end{align}$$ Let $s_2(m)$ be the sum of digits of $m$ in base-$2$. We see that $p_{n,j}(1)\equiv 0$ if and only if $s_2(j) + s_2(n+1-j) > s_2(n+1)$.

In general, $s_2(a)+s_2(b)-s_2(a+b)$ is the number of carries when adding $a$ and $b$ in base-$2$ (can be proved by induction, goes back to Kummer).

Claim: $p_{n,j}(1)$ vanishes modulo $2$ if and only there is a carry when adding $j$ and $n+1-j$ in base-$2$.

Proof: Let us write $x^n+1 \equiv x^n-1= \prod_{d \mid n} \Phi_d(x)$ where $\Phi_d$ is the $d$th cyclotomic polynomial. Then, since there are $\lfloor m/d\rfloor$ multiplies of $d$ in $\{1,2,\ldots,m\}$, $$p_{n,j}(x) = \prod_{d=2}^{n} \Phi_d(x)^{\lfloor \frac{n+1}{d} \rfloor- \lfloor \frac{j}{d}\rfloor - \lfloor \frac{n-j+1}{d}\rfloor }.$$ Note that $\lfloor a+b \rfloor \ge \lfloor a\rfloor + \lfloor b \rfloor$ so your expression is necessarily a polynomial (and not a strictly rational function).

The value of $\Phi_d(x)$ at $x=1$ is well-understood. One can use the property $x^n-1= \prod_{d \mid n} \Phi_d(x)$ to show $\Phi_d(1)$ is $1$ unless $d$ is a prime power $p^k$ in which case $\Phi_d(1)=p$ (this is classical, see here for proofs). This implies $$p_{n,j}(1) \equiv \prod_{p^k \le n} p^{\lfloor \frac{n+1}{p^k} \rfloor- \lfloor \frac{j}{p^k}\rfloor - \lfloor \frac{n-j+1}{p^k}\rfloor }.$$ Since $2$ is the only even prime, $$p_{n,j}(1) \equiv \prod_{2^k \le n} 2^{\lfloor \frac{n+1}{2^k} \rfloor- \lfloor \frac{j}{2^k}\rfloor - \lfloor \frac{n-j+1}{2^k}\rfloor }.$$ So your expression vanishes modulo $2$ if and only if $$ \sum_{2 \le 2^k \le n} \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor\ge 1.$$

Let us express this criterion using base-$2$ representation. If $j = \sum_{i \ge 0} a_i 2^i$, $n-j+1 = \sum_{i \ge 0} b_i 2^i$ and $n+1 = \sum_{i \ge 0} c_i 2^i$ then $$ \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor =\sum_{i \ge k} (c_i-a_i-b_i) 2^{i-k} $$ so that $$\begin{align} \sum_{2 \le 2^k \le n} \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor &= \sum_{i \ge 0} (c_i-a_i-b_i)(2^{i-1}+2^{i-2}+\ldots+1) \\ &= \sum_{i \ge 0} (c_i-a_i-b_i)(2^{i}-1)\\ &= n+1 - (j + (n+1-j)) - \sum_{i \ge 0} (c_i-a_i-b_i)\\ &= \sum_{i \ge 0} (a_i+b_i-c_i). \end{align}$$ Let $s_2(m)$ be the sum of digits of $m$ in base-$2$. We see that $p_{n,j}(1)\equiv 0$ if and only if $s_2(j) + s_2(n+1-j) > s_2(n+1)$.

In general, $s_2(a)+s_2(b)-s_2(a+b)$ is the number of carries when adding $a$ and $b$ in base-$2$ (can be proved by induction, goes back to Kummer).

Let $s_2(n)$ be the sum of digits of $n$ in base-$2$.

Claim: $p_{n,j}(1)$ vanishes modulo $2$ if and only if $s_2(j) + s_2(n+1-j) > s_2(n+1)$.

Proof: Let us write $x^n+1 \equiv x^n-1= \prod_{d \mid n} \Phi_d(x)$ where $\Phi_d$ is the $d$th cyclotomic polynomial. Then, since there are $\lfloor m/d\rfloor$ multiplies of $d$ in $\{1,2,\ldots,m\}$, $$p_{n,j}(x) = \prod_{d=2}^{n} \Phi_d(x)^{\lfloor \frac{n+1}{d} \rfloor- \lfloor \frac{j}{d}\rfloor - \lfloor \frac{n-j+1}{d}\rfloor }.$$ The value of $\Phi_d(x)$ at $x=1$ is well-understood. One can use the property $x^n-1= \prod_{d \mid n} \Phi_d(x)$ to show $\Phi_d(1)$ is $1$ unless $d$ is a prime power $p^k$ in which case $\Phi_d(1)=p$ (this is classical, see here for proofs). This implies $$p_{n,j}(1) \equiv \prod_{p^k \le n} p^{\lfloor \frac{n+1}{p^k} \rfloor- \lfloor \frac{j}{p^k}\rfloor - \lfloor \frac{n-j+1}{p^k}\rfloor }.$$ Since $2$ is the only even prime, $$p_{n,j}(1) \equiv \prod_{2^k \le n} 2^{\lfloor \frac{n+1}{2^k} \rfloor- \lfloor \frac{j}{2^k}\rfloor - \lfloor \frac{n-j+1}{2^k}\rfloor }.$$ So your expression vanishes modulo $2$ if and only if $$ \sum_{2 \le 2^k \le n} \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor\ge 1.$$

Let us express this criterion using base-$2$ representation. If $j = \sum_{i \ge 0} a_i 2^i$, $n-j+1 = \sum_{i \ge 0} b_i 2^i$ and $n+1 = \sum_{i \ge 0} c_i 2^i$ then $$ \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor =\sum_{i \ge k} (c_i-a_i-b_i) 2^{i-k} $$ so that $$\begin{align} \sum_{2 \le 2^k \le n} \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor &= \sum_{i \ge 0} (c_i-a_i-b_i)(2^{i-1}+2^{i-2}+\ldots+1) \\ &= \sum_{i \ge 0} (c_i-a_i-b_i)(2^{i}-1)\\ &= n+1 - (j + (n+1-j)) - \sum_{i \ge 0} (c_i-a_i-b_i)\\ &= \sum_{i \ge 0} (a_i+b_i-c_i). \end{align}$$

Claim: $p_{n,j}(1)$ vanishes modulo $2$ if and only there is a carry when adding $j$ and $n+1-j$ in base-$2$.

Proof: Let us write $x^n+1 \equiv x^n-1= \prod_{d \mid n} \Phi_d(x)$ where $\Phi_d$ is the $d$th cyclotomic polynomial. Then, since there are $\lfloor m/d\rfloor$ multiplies of $d$ in $\{1,2,\ldots,m\}$, $$p_{n,j}(x) = \prod_{d=2}^{n} \Phi_d(x)^{\lfloor \frac{n+1}{d} \rfloor- \lfloor \frac{j}{d}\rfloor - \lfloor \frac{n-j+1}{d}\rfloor }.$$ The value of $\Phi_d(x)$ at $x=1$ is well-understood. One can use the property $x^n-1= \prod_{d \mid n} \Phi_d(x)$ to show $\Phi_d(1)$ is $1$ unless $d$ is a prime power $p^k$ in which case $\Phi_d(1)=p$ (this is classical, see here for proofs). This implies $$p_{n,j}(1) \equiv \prod_{p^k \le n} p^{\lfloor \frac{n+1}{p^k} \rfloor- \lfloor \frac{j}{p^k}\rfloor - \lfloor \frac{n-j+1}{p^k}\rfloor }.$$ Since $2$ is the only even prime, $$p_{n,j}(1) \equiv \prod_{2^k \le n} 2^{\lfloor \frac{n+1}{2^k} \rfloor- \lfloor \frac{j}{2^k}\rfloor - \lfloor \frac{n-j+1}{2^k}\rfloor }.$$ So your expression vanishes modulo $2$ if and only if $$ \sum_{2 \le 2^k \le n} \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor\ge 1.$$

Let us express this criterion using base-$2$ representation. If $j = \sum_{i \ge 0} a_i 2^i$, $n-j+1 = \sum_{i \ge 0} b_i 2^i$ and $n+1 = \sum_{i \ge 0} c_i 2^i$ then $$ \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor =\sum_{i \ge k} (c_i-a_i-b_i) 2^{i-k} $$ so that $$\begin{align} \sum_{2 \le 2^k \le n} \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor &= \sum_{i \ge 0} (c_i-a_i-b_i)(2^{i-1}+2^{i-2}+\ldots+1) \\ &= \sum_{i \ge 0} (c_i-a_i-b_i)(2^{i}-1)\\ &= n+1 - (j + (n+1-j)) - \sum_{i \ge 0} (c_i-a_i-b_i)\\ &= \sum_{i \ge 0} (a_i+b_i-c_i). \end{align}$$ Let $s_2(m)$ be the sum of digits of $m$ in base-$2$. We see that $p_{n,j}(1)\equiv 0$ if and only if $s_2(j) + s_2(n+1-j) > s_2(n+1)$.

In general, $s_2(a)+s_2(b)-s_2(a+b)$ is the number of carries when adding $a$ and $b$ in base-$2$ (can be proved by induction, goes back to Kummer).

Let us write $x^n+1 \equiv x^n-1= \prod_{d \mid n} \Phi_d(x)$ where $\Phi_d$ is the $d$th cyclotomic polynomial. Then, since there are $\lfloor m/d\rfloor$ multiplies of $d$ in $\{1,2,\ldots,m\}$, $$p_{n,j}(x) = \prod_{d=2}^{n} \Phi_d(x)^{\lfloor \frac{n+1}{d} \rfloor- \lfloor \frac{j}{d}\rfloor - \lfloor \frac{n-j+1}{d}\rfloor }.$$ The value of $\Phi_d(x)$ at $x=1$ is well-understood. One can use the property $x^n-1= \prod_{d \mid n} \Phi_d(x)$ to show $\Phi_d(1)$ is $1$ unless $d$ is a prime power $p^k$ in which case $\Phi_d(1)=p$ (this is classical, see here for proofs). This implies $$p_{n,j}(1) \equiv \prod_{p^k \le n} p^{\lfloor \frac{n+1}{p^k} \rfloor- \lfloor \frac{j}{p^k}\rfloor - \lfloor \frac{n-j+1}{p^k}\rfloor }.$$ Since $2$ is the only even prime, $$p_{n,j}(1) \equiv \prod_{2^k \le n} 2^{\lfloor \frac{n+1}{2^k} \rfloor- \lfloor \frac{j}{2^k}\rfloor - \lfloor \frac{n-j+1}{2^k}\rfloor }.$$ So your expression vanishes modulo $2$ if and only if $$ \sum_{2 \le 2^k \le n} \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor\ge 1.$$

Let us express this criterion using base-$2$ representation. If $j = \sum_{i \ge 0} a_i 2^i$, $n-j+1 = \sum_{i \ge 0} b_i 2^i$ and $n+1 = \sum_{i \ge 0} c_i 2^i$ then $$ \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor =\sum_{i \ge k} (c_i-a_i-b_i) 2^{i-k} $$ so that $$\begin{align} \sum_{2 \le 2^k \le n} \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor &= \sum_{i \ge 0} (c_i-a_i-b_i)(2^{i-1}+2^{i-2}+\ldots+1) \\ &= \sum_{i \ge 0} (c_i-a_i-b_i)(2^{i}-1). \end{align}$$

Let $s_2(n)$ be the sum of digits of $n$ in base-$2$.

Claim: $p_{n,j}(1)$ vanishes modulo $2$ if and only if $s_2(j) + s_2(n+1-j) > s_2(n+1)$.

Proof: Let us write $x^n+1 \equiv x^n-1= \prod_{d \mid n} \Phi_d(x)$ where $\Phi_d$ is the $d$th cyclotomic polynomial. Then, since there are $\lfloor m/d\rfloor$ multiplies of $d$ in $\{1,2,\ldots,m\}$, $$p_{n,j}(x) = \prod_{d=2}^{n} \Phi_d(x)^{\lfloor \frac{n+1}{d} \rfloor- \lfloor \frac{j}{d}\rfloor - \lfloor \frac{n-j+1}{d}\rfloor }.$$ The value of $\Phi_d(x)$ at $x=1$ is well-understood. One can use the property $x^n-1= \prod_{d \mid n} \Phi_d(x)$ to show $\Phi_d(1)$ is $1$ unless $d$ is a prime power $p^k$ in which case $\Phi_d(1)=p$ (this is classical, see here for proofs). This implies $$p_{n,j}(1) \equiv \prod_{p^k \le n} p^{\lfloor \frac{n+1}{p^k} \rfloor- \lfloor \frac{j}{p^k}\rfloor - \lfloor \frac{n-j+1}{p^k}\rfloor }.$$ Since $2$ is the only even prime, $$p_{n,j}(1) \equiv \prod_{2^k \le n} 2^{\lfloor \frac{n+1}{2^k} \rfloor- \lfloor \frac{j}{2^k}\rfloor - \lfloor \frac{n-j+1}{2^k}\rfloor }.$$ So your expression vanishes modulo $2$ if and only if $$ \sum_{2 \le 2^k \le n} \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor\ge 1.$$

Let us express this criterion using base-$2$ representation. If $j = \sum_{i \ge 0} a_i 2^i$, $n-j+1 = \sum_{i \ge 0} b_i 2^i$ and $n+1 = \sum_{i \ge 0} c_i 2^i$ then $$ \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor =\sum_{i \ge k} (c_i-a_i-b_i) 2^{i-k} $$ so that $$\begin{align} \sum_{2 \le 2^k \le n} \left\lfloor \frac{n+1}{2^k} \right\rfloor- \left\lfloor \frac{j}{2^k}\right\rfloor- \left\lfloor \frac{n-j+1}{2^k}\right\rfloor &= \sum_{i \ge 0} (c_i-a_i-b_i)(2^{i-1}+2^{i-2}+\ldots+1) \\ &= \sum_{i \ge 0} (c_i-a_i-b_i)(2^{i}-1)\\ &= n+1 - (j + (n+1-j)) - \sum_{i \ge 0} (c_i-a_i-b_i)\\ &= \sum_{i \ge 0} (a_i+b_i-c_i). \end{align}$$