Two algorithms to find primes in patterns

Sorenson, Jonathan; Webster, Jonathan

doi:10.1090/mcom/3501

Two algorithms to find primes in patterns

Authors: Jonathan P. Sorenson and Jonathan Webster
Journal: Math. Comp. 89 (2020), 1953-1968
MSC (2010): Primary 11A41, 11Y11, 11Y16, 68Q25
DOI: https://doi.org/10.1090/mcom/3501
Published electronically: January 7, 2020
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: Let $k\ge 1$ be an integer, and let $P=(f_1(x), \ldots , f_k(x) )$ be admissible linear polynomials over the integers, or the pattern. We present two algorithms that find all integers where $\max { \{f_i(x) \} } \le n$ and all the are prime.

Our first algorithm takes $O_P(n/(\log \log n)^k)$ arithmetic operations using $O(k\sqrt {n})$ space.
Our second algorithm takes slightly more time, $O_P(n/(\log \log n)^{k-1})$ arithmetic operations, but uses only $n^{1/c}$ space for a fixed constant. The correctness of this algorithm is unconditional, but our analysis of its running time depends on two reasonable but unproven conjectures.

We are unaware of any previous complexity results for this problem beyond the use of a prime sieve.

We also implemented several parallel versions of our second algorithm to show it is viable in practice. In particular, we found some new Cunningham chains of length 15, and we found all quadruplet primes up to $10^{17}$ .

[1] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781–793. MR 2123939, https://doi.org/10.4007/annals.2004.160.781
[2] A. O. L. Atkin and D. J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), no. 246, 1023–1030. MR 2031423, https://doi.org/10.1090/S0025-5718-03-01501-1
[3] Eric Bach and Lorenz Huelsbergen, Statistical evidence for small generating sets, Math. Comp. 61 (1993), no. 203, 69–82. MR 1195432, https://doi.org/10.1090/S0025-5718-1993-1195432-5
[4] Paul T. Bateman and Roger A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers, Math. Comp. 16 (1962), 363–367. MR 148632, https://doi.org/10.1090/S0025-5718-1962-0148632-7
[5] Daniel J. Bernstein, Doubly focused enumeration of locally square polynomial values, High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams, Fields Inst. Commun., vol. 41, Amer. Math. Soc., Providence, RI, 2004, pp. 69–76. MR 2075648
[6] Jack Chernick, On Fermat’s simple theorem, Bull. Amer. Math. Soc. 45 (1939), no. 4, 269–274. MR 1563964, https://doi.org/10.1090/S0002-9904-1939-06953-X
[7] Richard Crandall and Carl Pomerance, Prime numbers, Springer-Verlag, New York, 2001. A computational perspective. MR 1821158
[8] L. E. Dickson,
A new extension of Dirichlet's theorem on prime numbers,
Messenger of Mathematics 33 (1904), 155-161.
[9] Tony Forbes, Prime clusters and Cunningham chains, Math. Comp. 68 (1999), no. 228, 1739–1747. MR 1651752, https://doi.org/10.1090/S0025-5718-99-01117-5
[10] William F. Galway, Dissecting a sieve to cut its need for space, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 297–312. MR 1850613, https://doi.org/10.1007/10722028_17
[11] Daniel M. Gordon and Gene Rodemich, Dense admissible sets, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 216–225. MR 1726073, https://doi.org/10.1007/BFb0054864
[12] Richard K. Guy, Unsolved problems in number theory, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR 2076335
[13] H. Halberstam and H.-E. Richert, Sieve methods, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], London-New York, 1974. London Mathematical Society Monographs, No. 4. MR 0424730
[14] G. H. Hardy and J. E. Littlewood, Some problems of ‘Partitio numerorum’; III: On the expression of a number as a sum of primes, Acta Math. 44 (1923), no. 1, 1–70. MR 1555183, https://doi.org/10.1007/BF02403921
[15] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
[16] Harald Andrés Helfgott, An improved sieve of Eratosthenes, Math. Comp. 89 (2020), no. 321, 333–350. MR 4011545, https://doi.org/10.1090/mcom/3438
[17] W. Kahan,
Pracniques: Further remarks on reducing truncation errors,
Commun. ACM 8 (1965), no. 1, 40ff.
[18] Dominic Klyve, Explicit bounds on twin primes and Brun’s Constant, ProQuest LLC, Ann Arbor, MI, 2007. Thesis (Ph.D.)–Dartmouth College. MR 2712414
[19] H. W. Lenstra Jr. and Carl Pomerance, Primality testing with Gaussian periods, J. Eur. Math. Soc. (JEMS) 21 (2019), no. 4, 1229–1269. MR 3941463, https://doi.org/10.4171/JEMS/861
[20] Günter Löh, Long chains of nearly doubled primes, Math. Comp. 53 (1989), no. 188, 751–759. MR 979939, https://doi.org/10.1090/S0025-5718-1989-0979939-8
[21] R. F. Lukes, C. D. Patterson, and H. C. Williams, Some results on pseudosquares, Math. Comp. 65 (1996), no. 213, 361–372, S25–S27. MR 1322892, https://doi.org/10.1090/S0025-5718-96-00678-3
[22] Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, https://doi.org/10.1016/S0022-0000(76)80043-8
[23] Thomas R. Nicely, Enumeration to 10¹⁴ of the twin primes and Brun’s constant, Virginia J. Sci. 46 (1995), no. 3, 195–204. MR 1401560
[24] Carl Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), no. 156, 587–593. MR 628717, https://doi.org/10.1090/S0025-5718-1981-0628717-0
[25] Hans Riesel, Prime numbers and computer methods for factorization, 2nd ed., Progress in Mathematics, vol. 126, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1292250
[26] J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 0137689
[27] A. Schinzel and W. Sierpiński, Sur certaines hypothèses concernant les nombres premiers, Acta Arith. 4 (1958), 185–208; erratum 5 (1958), 259 (French). MR 106202, https://doi.org/10.4064/aa-4-3-185-208
[28] Jonathan P. Sorenson, The pseudosquares prime sieve, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 4076, Springer, Berlin, 2006, pp. 193–207. MR 2282925, https://doi.org/10.1007/11792086_15
[29] Jonathan P. Sorenson, Sieving for pseudosquares and pseudocubes in parallel using doubly-focused enumeration and wheel datastructures, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 6197, Springer, Berlin, 2010, pp. 331–339. MR 2721430, https://doi.org/10.1007/978-3-642-14518-6_26
[30] Jonathan Sorenson and Jonathan Webster, Strong pseudoprimes to twelve prime bases, Math. Comp. 86 (2017), no. 304, 985–1003. MR 3584557, https://doi.org/10.1090/S0025-5718-2016-03134-8
[31] Kjell Wooding and Hugh C. Williams, Doubly-focused enumeration of pseudosquares and pseudocubes, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 4076, Springer, Berlin, 2006, pp. 208–221. MR 2282926, https://doi.org/10.1007/11792086_16
[32] Ti Zuo Xuan, Integers free of small prime factors in arithmetic progressions, Nagoya Math. J. 157 (2000), 103–127. MR 1752478, https://doi.org/10.1017/S0027763000007212
[33] Yitang Zhang, Bounded gaps between primes, Ann. of Math. (2) 179 (2014), no. 3, 1121–1174. MR 3171761, https://doi.org/10.4007/annals.2014.179.3.7