Which is the lowest or most accurate upper bound formula for the maximum gap in sieve of Eratosthenes after a particular iteration?

103 Views Asked by At

Consider a function $a(x)$ which gives the larget gap in the sieve of Eratosthenes after the $x^{th}$ iteration.

So,

$a(0) = 0$

$a(1) = 1$, After removing the multiples of 2.

$a(2) = 3$, After removing the multiples of 3.

$a(3) = 5$, After removing the multiples of 5.

$a(4) = 9$, After removing the multiples of 7.

Is there a formula to calculate $G(x)$ for any given number? If a specific formula is not available, is there an upper bound formula which gives the upper bound for $G(x)$


P.S: After the $x^{th}$ iteration of the sieve, there seems to emerge a repeating pattern with the cycle width of product of all the prime numbers used till the $x^{th}$ iteration. After the $1^{st}$ iteration there is a pattern cycle of width two. After the $2^{nd}$ iteration a width of six(2×3). After the $3^{rd}$ iteration the width of the cycle is 30(2×3×5).


Bounty Edit: The answer by Greg Martin says there is no closed formula and it points to OEIS A058989 series page, which says

Iwaniec proved that a(n) << n^2*(log n)^2. - Charles R Greathouse IV, Sep 08 2012

So there seems to be an upper bound to this function. The upper bound says the maximum gap is lesser than $n^2*(log n)^2$, here $n$ is the nth prime number.

Can we use this to somehow to prove that $$a(n) << q^2 - q$$ where $q$ is $n^{th}$ prime number.

Or

$$a(n) << p^2 - q$$ where $p$ is $(n+1)^{th}$ and $q$ is $n^{th}$ prime number.

1

There are 1 best solutions below

2
On

This is one less than the Jacobsthal function evaluated at the product of the first $n$ primes. The exact sequence on OEIS (which we should always search to see if our sequence is already known) is sequence A058989; see sequence A048670 for more information. No closed formula is known, (And yes, after the $x$th sieve iteration, the pattern is periodic with length equal to the product of the first $x$ primes.)