Sums of digits and almost primes (Q1923247)

This paper is devoted to the problem of existence of almost primes in sets of integers generated by finite automata (where words are identified with integers via their expansion in a base). It is proved that for every irreducible automaton there is a constant \(k\) such that the generated sequence contains infinitely many numbers having at most \(k\) prime factors. The sets defined by \(\{n:s(n) \equiv b \pmod q\}\), where \(s(n)\) is the sum of binary digits of \(n\), are particular cases, and these are investigated in detail. It is proved that these always contain infinitely many numbers (even \(\gg x/ \log x\) below \(x)\) with at most two prime factors. If \({\mathcal Q}\) is a set of residue classes modulo \(q\) and \(|{\mathcal Q} |\geq 0.722q\), then there are infinitely many primes \(p\) such that the residue of \(s(p)\) modulo \(q\) is in \({\mathcal Q}\). These results are achieved by proving (analytically) a statistical result on the joint distribution of \(n\) modulo \(d\) and \(s(n)\) modulo \(q\), analogous to the Bombieri-Vinogradov theorem on primes, and applying weighted sieve methods.