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
Abstract | References | Similar Articles | Additional Information
Abstract: Let be an integer, and let
be
admissible linear polynomials over the integers, or the pattern. We present two algorithms that find all integers
where
and all the
are prime.
- Our first algorithm takes
arithmetic operations using
space.
- Our second algorithm takes slightly more time,
arithmetic operations, but uses only
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 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 .
- [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
Retrieve articles in Mathematics of Computation with MSC (2010): 11A41, 11Y11, 11Y16, 68Q25
Retrieve articles in all journals with MSC (2010): 11A41, 11Y11, 11Y16, 68Q25
Additional Information
Jonathan P. Sorenson
Affiliation:
Department of Computer Science and Software Engineering, Butler University, Indianapolis, Indiana 46208
Email:
sorenson@butler.edu
Jonathan Webster
Affiliation:
Department of Mathematics, Statistics, and Actuarial Science, Butler University, Indianapolis, Indiana 46208
Email:
jewebste@butler.edu
DOI:
https://doi.org/10.1090/mcom/3501
Received by editor(s):
July 23, 2018
Received by editor(s) in revised form:
February 14, 2019, and October 31, 2019
Published electronically:
January 7, 2020
Additional Notes:
A preliminary version of this work was presented as a poster at the ANTS XIII conference in Madison, Wisconsin, in July of 2018.
Article copyright:
© Copyright 2020
American Mathematical Society