# zbMATH — the first resource for mathematics

Sums of digits and almost primes. (Sommes des chiffres et nombres presque premiers.) (French) Zbl 0858.11050
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.

##### MSC:
 11N36 Applications of sieve methods 11B85 Automata sequences 11A41 Primes 11A63 Radix representation; digital problems
Full Text:
##### References:
 [1] Allouche, J.-P., Mend?s France, M.: On an extremal property of the Rudin-Shapiro sequence. Mathematika32 (1985) 33-38 · Zbl 0561.10025 · doi:10.1112/S0025579300010822 [2] Balog, A., Ruzsa, I.: On an additive property of stable sets. Proceedings of the Conference in honour of C. Hooley (Cardiff 1995) (? para?tre) · Zbl 0924.11011 [3] Conze, J.-P., Raugi, A.: Fonctions harmoniques pour un op?rateur de transition et applications. Bull. Soc. Math. France118 (1990), 273-310 · Zbl 0725.60026 [4] Coquet, J.: A summation formula related to the binary digits. Invent. Math.73 (1983), 107-115 · Zbl 0528.10006 · doi:10.1007/BF01393827 [5] Fine, N.J.: The distribution of the sum of digits (mod p). Bull. Amer. Math. Soc.71 (1965), 651-652 · Zbl 0148.02005 · doi:10.1090/S0002-9904-1965-11381-7 [6] Fouvry E.: Th?or?me de Brun-Titchmarsh; application au th?or?me de Fermat. Invent. Math.79 (1985), 383-407 · Zbl 0557.10035 · doi:10.1007/BF01388980 [7] Gelfond, A.O.: Sur les nombres qui ont des propri?t?s additives et multiplicatives donn?es, Acta Arith.13 (1968), 259-265 · Zbl 0155.09003 [8] Harman, G.: The distribution of ?p modulo one. J. London Math. Soc. (2)27 (1983), 9-18 · Zbl 0504.10018 · doi:10.1112/jlms/s2-27.1.9 [9] Halberstam, H., Richert, H.E.: Sieve Methods. Academic Press, New York 1974 · Zbl 0298.10026 [10] Hennion, H.: Sur un th?or?me spectral et son application aux noyaux lipschitziens. Proc. of the A.M.S.118(2) (1993), 627-634 · Zbl 0772.60049 [11] Herv?, L.: ?tude d’op?rateurs quasi-compacts positifs. Applications aux g?n?rateurs de transfert. Ann. Inst. Henri Poincar?30(3) (1994), 437-466 [12] Herv?, L.: Construction et r?gularit? des fonctions d’?chelle. SIAM J. Anal. Math.26 (1995), 1361-1385 · Zbl 0848.42023 · doi:10.1137/S0036141092240023 [13] Hildebrand, A.: On a conjecture of Balog. Proc. of the A.M.S.95 (1985), 517-523 · Zbl 0597.10056 · doi:10.1090/S0002-9939-1985-0810155-4 [14] Hooley, C.: On the Barban-Davenport-Halberstam Theorem. III, J. London Math. Soc. (2)10 (1975), 249-256 · Zbl 0304.10029 · doi:10.1112/jlms/s2-10.2.249 [15] Ionescu-Tulcea, C.T., Marinescu, G.: Th?orie ergodique pour une classe d’op?rations non compl?tement continues. Annals Math.52 (1950), 140-147 · Zbl 0040.06502 · doi:10.2307/1969514 [16] Iwaniec, H., Jutila, M.: Primes in short intervals. Arkiv Math.17 (1979), 167-176 · Zbl 0408.10029 · doi:10.1007/BF02385465 [17] Iwaniec, H., Pomykala, J.: Sums and differences of quartic norms. Mathematika40 (1993), 233-245 · Zbl 0799.11035 · doi:10.1112/S0025579300007014 [18] Iwaniec, H.: Rosser’s Sieve. Acta Arith.36 (1980), 171-202 · Zbl 0435.10029 [19] Iwaniec, H.: On sums of two norms of cubic fields. Journ?es de Th?orie additive des nombres (1977) Bordeaux, 71-89 [20] Keane, M.: Strongly Mixingg-Measures. Invent. Math.16 (1972), 309-324 · Zbl 0241.28014 · doi:10.1007/BF01425715 [21] Montgomery, H.L.: Topics in Multiplicative Number Theory, Lecture Notes in Mathematics227, Springer, Berlin 1971 · Zbl 0216.03501 [22] Newman, D.J.: On the number of binary digits in a multiple of three. Proceedings of the A.M.S.21 (1969), 719-721 · Zbl 0194.35004 · doi:10.1090/S0002-9939-1969-0244149-8 [23] Rudin, W.: Some Theorems on Fourier Coefficients. Proceedings of the A.M.S.10 (1959), 855-859 · Zbl 0091.05706 · doi:10.1090/S0002-9939-1959-0116184-5 [24] Shapiro, H.S.: Extremal Problems for Polynomials and Power Series, Doctoral Thesis, M.I.T. (1951) [25] Tenenbaum, G.: Introduction ? la th?orie analytique et probabiliste des nombres. Cours Sp?cialis?s 1 Soci?t? Math?matique de France (1995)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.