Suggested by [this problem](https://mathoverflow.net/q/405252/9924):



> 
> Do the sets of all odious / evel numbers meet every infinite arithmetic progression?
> 
> 
> 


A number is [odious](https://oeis.org/A000069) if it contains an odd number of digits $1$ in its binary representation; otherwise, it is [evel](https://oeis.org/A000069). Alternatively, the odious numbers specify the positions of the nonzero values in the Thue–Morse sequence.


Equivalently:



> 
> Is it true that any arithmetic progression $an+b$, with $a>0$ and $b$ integers, has a term with an odd number of $1$'s and a term with an even number of $1$'s?
> 
> 
> 


I expect that the answer is in the affirmative unless I am overlooking some simple obstruction.


Without loss of generality, one can assume that the progression is of the form $(an+1)b$ with $a=2^k-1$. Another potentially useful observation: the parity of the number of $1$'s in the binary representation of the integer $z$ is the same as the parity of the sum
$z + \lfloor z/2\rfloor + \lfloor z/4\rfloor + \lfloor z/8\rfloor + \dotsb$



Where odious numbers meet arithmetic progressions
Yes, we even know that the density of such $n$ is the expected one.


A. O. Gelfond proved in 1968, in a short paper ("Sur les nombres qui ont des propriétés additives et multiplicatives données", Acta Arithmetica 13, pages 259-265) that, for all $b \bmod a$ and $j \bmod m$,
$$(\star) \, \lim\_{N \to \infty}\frac{1}{N/a}\#\{ 1 \le n \le N: n \equiv b \bmod a, \, s\_q(n) \equiv j \bmod m\}=\frac{1}{m}.$$
Here $a,q,m$ are fixed positive integers, $s\_q$ is the sum of digits in base-$q$, and $\gcd(m,q-1)=1$ (otherwise there are obvious obstructions, due to the congruence $n \equiv s\_q(n) \bmod {q-1}$).


Now apply this with $q=m=2$ to get your answer.


Regarding the error term in $(\star)$: already Gelfond proved a power saving result. This means that the expression in the limit in $(\star)$ is $1/m$ plus $O\_{a,m,q}(N^{-c})$ for some concrete $c$ depending on $m$ and $q$.


An optimal value for $c$ when $q=m=2$ was determined in 2009 by V. Shevelev ("Exact exponent in the remainder term of Gelfond's digit theorem in the binary case", Acta Arithmetica 136, pages 91-100).


