Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
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 $ 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 [Enhancements On Off] (What's this?)

Similar Articles

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

Jonathan Webster
Affiliation: Department of Mathematics, Statistics, and Actuarial Science, Butler University, Indianapolis, Indiana 46208

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