Let $\{x\_i\}:=\{x\_1=5, x\_2=13, x\_3=29, x\_4=37, x\_5=45, \dots \}$
be the sequence of those positive integers of the form
$$
p^{4\alpha+1}n^2$$
in increasing order where $p\equiv 5\pmod 8$ is prime and $\gcd(n,2p)=1$.
Next, define the sequence $\{y\_i\}$ by letting $y\_i:=\frac{x\_i-5}{8}$.
The first few terms of the $q$-series $\sum\_{i=1}^{\infty}q^{y\_i}$ are
$$\sum\_{i=1}^{\infty}q^{y\_i}=1+q+q^3+q^4+q^5+q^6+q^7+q^{12}+q^{13}+q^{14}+q^{18}+q^{19}+\cdots.$$
If $p(N)$ denotes the number of ordinary integer partitions of $N$, then
$$
 \sum\_{N=0}^{\infty}p(N)q^N\equiv 1+q+q^3+q^4+q^5+q^6+q^7+q^{12}+q^{13}+q^{14}+q^{16}+q^{17}
+q^{18}+\cdots\mod 2.
$$
By comparing these two $q$-series one finds for $N\leq 15$ that $p(N)$ is odd
precisely for those $N$ that are elements in the sequence $\{y\_i\}$.


If one searches for long strings of consecutive even values of
the partition function in arithmetic progressions, one immediately
finds in the progression $10\pmod{16}$ that
$$p(10)\equiv p(26)\equiv p(42)\equiv p(58)\equiv p(74)\equiv 0\pmod 2,$$
but $p(90)\equiv 1\pmod 2$.
It is curious to note that $10, 26, 42, 58, 74\not \in \{y\_i\}$ but
$90=y\_{45}$.


This motivates me to inquire:



> 
> **Question.** If $N< 16^k$, is the following true?
> $$p(N)\equiv \# \left \{ (z\_0,z\_1,\dots z\_{k-1})\ | \ 
> z\_j\in \{y\_i\}\ \text {and}\ \sum\_{j=0}^{k-1}16^jz\_j=N \right \} \mod 2.
> $$
> 
> 
> 



"strange" diophantine and parity of the partition function
Your conjecture is true! Here is one way to get it using some mod 4 generatingfunctionology. The answer got a bit long, so I divided it into two parts, as an attempt to improve readability. 




---


**Part1:** Let's denote by $Y(q)$ your generating function $\sum\_{i\geq 1}q^{y\_i}$. We will prove that
$$Y(q)\equiv \prod\_{k\geq 1}(1+q^{2k-1})(1+q^{16k})\pmod{2}.$$


Proof: One very classical theorem that dates back to Legendre states that the number of ways of writing $n\in \mathbb N$ as a sum of four triangular numbers is equal to $\sigma(2n+1)$, the sum of divisors of $2n+1$. Since the generating function of triangular numbers admits an infinite product expression from Jacobi's triple product formula, we can rewrite this theorem in the language of generating functions:
$$\sum\_{n\geq 0}\sigma(2n+1)q^n=\prod\_{k\geq 1}\frac{(1-q^{2k})^8}{(1-q^k)^4}.$$
I made use of this in [an older answer](https://mathoverflow.net/a/59185/2384), where we also pointed out the following simple corollary:
$$\sum\_{n\geq 0}\sigma(4n+1)q^n\equiv\prod\_{k\geq 1}\left(\frac{1-q^{4k}}{1-q^k}\right)^2=\prod\_{k\geq 1}(1+q^{2k-1})^2(1+q^{2k})^4\pmod{4}.$$
Let us denote $$A(q)=\sum\_{n\geq 0}\sigma((2n+1)^2)q^{\binom{n+1}{2}}.$$ 
The next lemma will allow us to split $\sum\_{n\geq 0}\sigma(2n+1)q^n \pmod{4}$ into its even and odd parts. More precisely it will show
$$\sum\_{n\geq 0}\sigma(2n+1)q^n\equiv A(q^2)+2qY(q^2) \pmod{4}$$


**Lemma:** The value of $\sigma(4n+1)$ is $1,3\pmod{4}$ iff 4n+1 is a perfect square, and it is $2\pmod{4}$ iff $n=2y\_i+1$ for some $i$.


Proof of lemma: An odd number $m$ has a factorization $\prod p\_i^{\alpha\_i}q\_j^{\beta\_j}$ where $p\_i$'s are primes $1\pmod 4$ and $q\_j$'s are primes $3\pmod{4}$. The function $\sigma$ is multiplicative, so we just need to check the prime powers individually.
$$\sigma(p\_i^{\alpha\_i})=\frac{p\_i^{\alpha\_i+1}-1}{p\_i-1}\equiv \alpha\_i+1\pmod{4}$$
$$\sigma(q\_j^{\beta\_j})=\frac{q^{\beta\_j+1}-1}{q\_j-1}\equiv\left\{
\begin{array}{ll}
 1\pmod{4} & \beta\_j\text{ is even} \\
 0\pmod{4} & \beta\_j\text{ is odd} \\
\end{array} 
\right.$$
Using the fact that $\sigma(m)=\prod \sigma(p\_i^{\alpha\_i})\sigma(q\_j^{\beta\_j})$ we see that $\sigma(m)$ is odd iff each $\alpha\_i$ and $\beta\_j$ are even, iff $m$ is a perfect square. We also see that $\sigma(m)=2\pmod{4}$ iff all $\beta\_j$ are even, and exactly one $\alpha\_i$ is $1\pmod{4}$, which is equivalent to saying that $m$ is one of the elements of your $x\_i$ sequence. Now, $4n+1=x\_i \implies n=2y\_i+1$, so this concludes the proof of the lemma.


Some algebraic manipulations give us
$$\prod\_{k\geq 1}(1+q^{2k-1})^2(1+q^{2k})^4=\prod\_{k\geq 1}(1+q^{4k-2})(1+q^{2k})^4\prod\_{k\geq 1}(1+2\frac{q^{2k-1}}{1+q^{4k-2}})$$
$$\equiv \prod\_{k\geq 1}(1+q^{4k-2})(1+q^{2k})^4\left(1+2\sum\_{k\geq 1} \frac{q^{2k-1}}{1+q^{4k-2}}\right)\pmod{4}.$$
Therefore we have an expression for $Y(q)\pmod{2}$
$$Y(q)\equiv \prod\_{k\geq 1}(1+q^{2k-1})(1+q^{k})^4\left(\sum\_{k\geq 1} \frac{q^{k-1}}{1+q^{2k-1}}\right)\pmod{2}$$
$$\equiv \prod\_{k\geq 1}(1+q^{2k-1})(1+q^{k})^4\left(\sum\_{k\geq 1} \frac{q^{k-1}}{1-q^{2k-1}}\right)\pmod{2}.$$
Next we notice that the coefficient of $q^n$ in $\sum\_{k\geq 1} \frac{q^{k-1}}{1-q^{2k-1}}$ counts the number of integers $r\geq 0,k\geq 1$ such that $n=k-1+r(2k-1)$, which can be rewritten as $2n+1=(2k-1)(2r+1)$. The number of solutions to this equation is precisely the number of divisors of $2n+1$, and since the divisors of an odd number are odd, the number of divisors of $2n+1$ has the same parity as the sum of divisors of $2n+1$. Therefore $\sum\_{k\geq 1} \frac{q^{k-1}}{1-q^{2k-1}}$ is also equal to $\sum\_{n\geq 0}\sigma(2n+1)q^n\pmod{2}$. Plugging this in our equation gives
$$Y(q)\equiv \prod\_{k\geq 1}(1+q^{2k-1})(1+q^{k})^4\frac{(1-q^{2k})^8}{(1-q^k)^4}\equiv \prod\_{k\geq 1}(1+q^{2k-1})(1+q^{16k})\pmod{2}$$
and this finishes our proof. $\blacksquare$




---


**Part2:** Your conjecture would follow easily from the equality
$$\prod\_{k\geq 1}\frac{1}{1-q^k}\equiv \prod\_{i\geq 0}Y(q^{16^i})\pmod{2}.$$
Indeed the coefficient of $q^n$ on the left represents the parity of $p(n)$, the number of partitions of $n$, whereas the right hand side represents the number of ways of writing $n=z\_0+16z\_1+16^2z\_2+\cdots$ where each $z\_j$ is equal to some $y\_i$. 


In order to prove this we will use the mod 2 identity
$$\prod\_{k\geq 1}(1+q^{2k-1})=\prod\_{k\geq 1}\frac{1+q^k}{1+q^{2k}}=\prod\_{k\geq 1}\frac{1+q^k}{(1+q^k)^2}=\prod\_{k\geq 1}\frac{1}{1+q^k}\pmod{2}$$
which implies that 
$$\prod\_{k\geq 1}(1+q^{16k})=\prod\_{k\geq 1}\frac{1}{1+q^{16(2k-1)}}\pmod{2}.$$
We can use this in our expression for $Y(q)$ to get
$$Y(q)=\prod\_{k\geq 1}\frac{1+q^{2k-1}}{1+q^{16(2k-1)}}$$
which shows that the product $Y(q)Y(q^{16})Y(q^{16^2})\cdots$ telescopes to $\prod\_{k\geq 1} (1+q^{2k-1})$ which is equal to the partition function $\pmod{2}$ thanks to the same identity above.


