Two algorithms to find primes in patterns

DOI10.1090/MCOM/3501zbMATH Open1461.11017arXiv1807.08777OpenAlexW2884734563MaRDI QIDQ4960081FDOQ4960081

Authors: Jonathan Webster, Jonathan P. Sorenson 

Publication date: 8 April 2020

Published in: Mathematics of Computation (Search for Journal in Brave)

Abstract: Let $kge1$ be an integer, and let $P=(f_1(x),ldots,f_k(x))$ be $k$ admissible linear polynomials over the integers, or extit{the pattern}. We present two algorithms that find all integers $x$ where $max{f}_i(x)len$ and all the $f_i(x)$ are prime. Our first algorithm takes at most $O_P(n/(loglogn{)}^k)$ arithmetic operations using $O(ksqrtn)$ space. Our second algorithm takes slightly more time, $O_P(n/(loglogn{)}^{k-1})$ arithmetic operations, but uses only $n^{1/c}$ space for a constant $c>2$. We prove correctness unconditionally, but the running time relies on two unproven but reasonable 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}$.

Full work available at URL: https://arxiv.org/abs/1807.08777

Recommendations

• Constructing finite field extensions with large order elements
• Testing numbers of the form for primality
• Constructing Finite Field Extensions with Large Order Elements
• scientific article; zbMATH DE number 917769
• A sublinear additive sieve for finding prime number
• Primality tests and factorization algorithms. I
• A space-efficient fast prime number sieve
• Decision problem \texttt{PRIMES}
• scientific article; zbMATH DE number 7556735

zbMATH Keywords

primesprimality teststwin primesCunningham chainsprime sievesprime patternsquadruplets primes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Primes (11A41) Primality (11Y11)

Cites Work

• Title not available (Why is that?)
• Unsolved problems in number theory
• Riemann's hypothesis and tests for primality
• PRIMES is in P
• Title not available (Why is that?)
• On the Distribution of Pseudoprimes
• Approximate formulas for some functions of prime numbers
• Bounded gaps between primes
• Title not available (Why is that?)
• Prime numbers and computer methods for factorization.
• Primality testing with Gaussian periods
• Sur certaines hypothèses concernant les nombres premiers
• A Heuristic Asymptotic Formula Concerning the Distribution of Prime Numbers
• Algorithmic Number Theory
• Algorithmic Number Theory
• Title not available (Why is that?)
• An improved sieve of Eratosthenes
• Prime sieves using binary quadratic forms
• Statistical Evidence for Small Generating Sets
• Long Chains of Nearly Doubled Primes
• Prime clusters and Cunningham chains
• Strong pseudoprimes to twelve prime bases
• Integers free of small prime factors in arithmetic progressions
• Sieving for pseudosquares and pseudocubes in parallel using doubly-focused enumeration and wheel datastructures
• Title not available (Why is that?)
• Some results on pseudosquares
• Title not available (Why is that?)

Cited In (4)

• Title not available (Why is that?)
• Sieving for large twin primes and Cunningham chains of length 2 of the second kind
• An algorithm and computation to verify Legendre's conjecture up to \(7\cdot 10^{13}\)
• Title not available (Why is that?)

This page was built for publication: Two algorithms to find primes in patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4960081)