On the number of distinct prime factors of \(nj+a^hk\). (English) Zbl 1311.11097

T. Tao [J. Aust. Math. Soc. 91, No. 3, 405–413 (2011; Zbl 1251.11089)] proved that, for any integer \(K \geq 2\), a positive proportion of the primes in the interval \([x, (1+K^{-1}) x]\) have the property that \(|pj \pm a^h k|\) is composite for every \(2 \leq a \leq K\), \(1 \leq j, k \leq K\) and \(1 \leq h \leq K \log x\). This result has the nice consequence that it is not possible to tell whether an integer is a prime without reading all of its base \(a\) digits.
The present paper generalises Tao’s result in certain aspects showing that there exists at least \(x^{1-\varepsilon}\) integers \(n \in [x, (1+K^{-1}) x]\) which have the property that \(\omega(n j \pm a^h k) \geq (\log \log \log x)^{1/3-\varepsilon}\) for every \(2 \leq a \leq K\), \(1 \leq j, k \leq K\) and \(1 \leq h \leq K \log x\), where \(\omega(m)\) denotes the number of distinct prime factors of \(m\), i.e., the author shows that there are quite many numbers \(n\) (though fewer than in Tao’s result) such that \(n j \pm a^h k\) are not just barely composite but all of them have relatively many prime factors.
The proof is a refined and more efficient version of Tao’s method which uses incomplete covers of \(\mathbb Z\).


11P32 Goldbach-type theorems; other additive questions involving primes
11A07 Congruences; primitive roots; residue systems
11B25 Arithmetic progressions
11N36 Applications of sieve methods


Zbl 1251.11089
Full Text: DOI arXiv


[1] Chan, T.H., Choi, S.K.-K., Tsang, K.M.: An extension to the Brun-Titchmarsh theorem. Q. J. Math 62, 307-322 (2011) · Zbl 1269.11097
[2] Cohen, F; Selfridge, JL, Not every number is the sum or difference of two prime powers, Math. Comput., 29, 79-81, (1975) · Zbl 0296.10029
[3] Corput, JG, On de polignac’s conjecture, Simon Stevin, 27, 99-105, (1950) · Zbl 0037.16901
[4] Erdős, P, On integers of the form \(2^k+p\) and some related problems, Summa Brasil. Math., 2, 113-123, (1950)
[5] Erdős, P.: Problems and results on combinatorial number theory. III, Number Theory Day, Proc. Conf., New York 1976, Lecture Notes in Mathematics, vol. 626, pp. 43-72 (1977)
[6] Halberstam, H., Richert, H.-E.: Sieve methods. London Mathematical Society Monographs, vol. 4. Academic Press, London (1974) · Zbl 0298.10026
[7] Hardy, G.H., Ramanujan, S.: The normal number of prime factors of a number \(n\). Q. J. Pure. Appl. Math. 48, 76-92 (1917) · JFM 46.0262.03
[8] Nathanson, M.B.: Additive number theory. The classical bases, Graduate Texts in Mathematics, vol. 164. Springer, New York (1996) · Zbl 0859.11002
[9] Sun, ZW, On integers not of the form \(± p^{a}± q^{b}\), Proc. Am. Math. Soc., 128, 997-1002, (2000) · Zbl 0959.11043
[10] Tao, T, A remark on primality testing and decimal expansions, J. Aust. Math. Soc., 91, 405-413, (2011) · Zbl 1251.11089
[11] Turán, P.: On a theorem of Hardy and Ramanujan. J. Lond. Math. Soc. 9, 274-276 (1934)
[12] Zsigmondy, K.: Zur Theorie der Potenzreste. Monatsh. Math. Phys. 3, 265-284 (1882) · JFM 24.0176.02
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.