Two algorithms to find primes in patterns
HTML articles powered by AMS MathViewer
- by Jonathan P. Sorenson and Jonathan Webster HTML | PDF
- Math. Comp. 89 (2020), 1953-1968 Request permission
Abstract:
Let $k\ge 1$ be an integer, and let $P=(f_1(x), \ldots , f_k(x) )$ be $k$ admissible linear polynomials over the integers, or the pattern. We present two algorithms that find all integers $x$ where $\max { \{f_i(x) \} } \le n$ and all the $f_i(x)$ 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 $c>2$ 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}$.
References
- Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781–793. MR 2123939, DOI 10.4007/annals.2004.160.781
- A. O. L. Atkin and D. J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), no. 246, 1023–1030. MR 2031423, DOI 10.1090/S0025-5718-03-01501-1
- Eric Bach and Lorenz Huelsbergen, Statistical evidence for small generating sets, Math. Comp. 61 (1993), no. 203, 69–82. MR 1195432, DOI 10.1090/S0025-5718-1993-1195432-5
- 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, DOI 10.1090/S0025-5718-1962-0148632-7
- 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
- Jack Chernick, On Fermat’s simple theorem, Bull. Amer. Math. Soc. 45 (1939), no. 4, 269–274. MR 1563964, DOI 10.1090/S0002-9904-1939-06953-X
- Richard Crandall and Carl Pomerance, Prime numbers, Springer-Verlag, New York, 2001. A computational perspective. MR 1821158, DOI 10.1007/978-1-4684-9316-0
- L. E. Dickson, A new extension of Dirichlet’s theorem on prime numbers, Messenger of Mathematics 33 (1904), 155–161.
- Tony Forbes, Prime clusters and Cunningham chains, Math. Comp. 68 (1999), no. 228, 1739–1747. MR 1651752, DOI 10.1090/S0025-5718-99-01117-5
- 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, DOI 10.1007/10722028_{1}7
- 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, DOI 10.1007/BFb0054864
- Richard K. Guy, Unsolved problems in number theory, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR 2076335, DOI 10.1007/978-0-387-26677-0
- H. Halberstam and H.-E. Richert, Sieve methods, London Mathematical Society Monographs, No. 4, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1974. MR 0424730
- 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, DOI 10.1007/BF02403921
- 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
- Harald Andrés Helfgott, An improved sieve of Eratosthenes, Math. Comp. 89 (2020), no. 321, 333–350. MR 4011545, DOI 10.1090/mcom/3438
- W. Kahan, Pracniques: Further remarks on reducing truncation errors, Commun. ACM 8 (1965), no. 1, 40ff.
- Dominic Klyve, Explicit bounds on twin primes and Brun’s Constant, ProQuest LLC, Ann Arbor, MI, 2007. Thesis (Ph.D.)–Dartmouth College. MR 2712414
- 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, DOI 10.4171/JEMS/861
- Günter Löh, Long chains of nearly doubled primes, Math. Comp. 53 (1989), no. 188, 751–759. MR 979939, DOI 10.1090/S0025-5718-1989-0979939-8
- 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, DOI 10.1090/S0025-5718-96-00678-3
- Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, DOI 10.1016/S0022-0000(76)80043-8
- Thomas R. Nicely, Enumeration to $10^{14}$ of the twin primes and Brun’s constant, Virginia J. Sci. 46 (1995), no. 3, 195–204. MR 1401560
- Carl Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), no. 156, 587–593. MR 628717, DOI 10.1090/S0025-5718-1981-0628717-0
- 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, DOI 10.1007/978-1-4612-0251-6
- J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
- 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, DOI 10.4064/aa-4-3-185-208
- 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, DOI 10.1007/11792086_{1}5
- 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, DOI 10.1007/978-3-642-14518-6_{2}6
- Jonathan Sorenson and Jonathan Webster, Strong pseudoprimes to twelve prime bases, Math. Comp. 86 (2017), no. 304, 985–1003. MR 3584557, DOI 10.1090/mcom/3134
- 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, DOI 10.1007/11792086_{1}6
- Ti Zuo Xuan, Integers free of small prime factors in arithmetic progressions, Nagoya Math. J. 157 (2000), 103–127. MR 1752478, DOI 10.1017/S0027763000007212
- Yitang Zhang, Bounded gaps between primes, Ann. of Math. (2) 179 (2014), no. 3, 1121–1174. MR 3171761, DOI 10.4007/annals.2014.179.3.7
Additional Information
- Jonathan P. Sorenson
- Affiliation: Department of Computer Science and Software Engineering, Butler University, Indianapolis, Indiana 46208
- MR Author ID: 334195
- Email: sorenson@butler.edu
- Jonathan Webster
- Affiliation: Department of Mathematics, Statistics, and Actuarial Science, Butler University, Indianapolis, Indiana 46208
- MR Author ID: 903429
- Email: jewebste@butler.edu
- 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.
- © Copyright 2020 American Mathematical Society
- Journal: Math. Comp. 89 (2020), 1953-1968
- MSC (2010): Primary 11A41, 11Y11, 11Y16, 68Q25
- DOI: https://doi.org/10.1090/mcom/3501
- MathSciNet review: 4081924