# Maximal gaps in prime factorizations (“wheel factorization”)

A wheel factorization is when you remove all the multiples of primes (up to a prime number P) from the product of all primes up to and including P. Examples:

For P=5, you remove all the multiples of 2,3 and 5 from 1 to 2x3x5=30

You are then left with the set {1, 7, 11, 13, 17, 19, 23, 29}

For P=7, you would remove all the multiples of 2,3,5,7 from 1 to 2x3x5x7=210

You are then left with the set {1, 11, 13, 17, ......... 199, 209} etc.

(Just for the record, I am aware this does NOT generate a set of prime numbers, e.g. 209 = 11x19)

My question is, for a certain P, what is the maximum gap / difference between successive elements of the set and how do I go about proving it?

When P=3 with the set {1, 5}, the maximum gap is 4

When P=5 with the set {1, 7, 11, 13, 17, 19, 23, 29}, the maximum gap is 6

When P=7 with the set {1, 11, 13, 17, .... 199, 209}, the maximum gap is 10

When P=11, the maximum gap is 14

I am currently putting together a program to calculate maximum gaps for higher values of P.

Once I am confident of a pattern, how could I go about proving this (maximum gaps)? I have no idea where to even begin!

Thanks.

• An update with regards to the program to calculate maximum gaps for higher values of P. For P=13, maximum gap is 22. For P=17, maximum gap is 26. There is a clear pattern emerging! However I have no clue how to prove it! – Mister Dog Feb 5 '14 at 4:46
• The pattern is maximal gap = 2xp_n-1. I have given a proof that this is the LOWER BOUND of the maximal gap below. It is very difficult to get a "neat" upper bound however (one that doesn't use tons of sieve theory) – Mister Dog Feb 8 '14 at 4:40

The Jacobsthal function $j(n)$ is the maximal gap between integers relatively prime to $n$. Hence the desired function is the Jacobsthal function of the primes up to $p$: $j(p\#).$ It is Sloane's A048670 and it has been widely studied.

It is equal to twice the n-th prime for the first few terms, but then diverges:

4, 6, 10, 14, 22, 26, 34, 40, 46, 58, 66, 74, 90, 100, 106, 118, 132, 152, 174, 190, 200, ...

In fact, it follows from a result of Pintz [1] that the two can be equal only finitely often. Probably 74 is the last term of this sort.

[1] János Pintz, Very large gaps between consecutive primes, Journal of Number Theory 63 (1997), pp. 286–301.

• Hi Charles, thanks for this post. I had no idea this sequence existed and I probably would have assumed it equals twice the previous prime! I took a look at the OEIS page and one result for the pattern was that, a(n) << n^2 ln(n), where n is the nth prime. I was wondering, do you know if there is a result in terms of the maximum prime p, rather than the n number of primes? So for example, if dealing with the 5th prime 11, a result in terms of 11, as opposed to 5 as is in the OEIS page? Thanks. – Mister Dog Feb 6 '14 at 8:55
• Well, you can substitute in bounds on the n-th prime to get an answer if you like. Be careful with the error terms! Alternately, with more effort you can extract a better (I think) result directly from the corollary in Iwaniec, see p. 2 here: matwbn.icm.edu.pl/ksiazki/aa/aa19/aa1911.pdf – Charles Feb 7 '14 at 8:36

Proof that 2 x p_n-1 is not the maximal gap, but the lowest bound of the maximal gap.

If you take the set of primes {2,3,5,7....p_n-1, p_n)

By the Chinese remainder theorem you can derive an x such that

x = 0 mod N (where N = 2x3x5x7....p_n-2)

x = 1 mod p_n-1

x = -1 mod p_n

This would create a gap of 2.p_n-1 centred around x.

Thus the lowest bound of the maximal gap is 2p_n-1.

Comparing 2p_n-1 with the Jacobstahl conjecture it seems they match for the first few pairs as Charles mentioned, and then diverge.

I haven't found any proof for this, but I'm pretty sure the formula is $$G_i = 2\cdot p_{i-1} \text{, for}~ i\geq 3$$ where $G_i$ is the maximum gap in question and $p_i$ is i-th prime number.

For example,

• for $i=3$, $p_3=3$ and $G_3=2\cdot 2=4$

• for $i=4$, $p_4=5$ and $G_4=2\cdot 3=6$

• for $i=5$, $p_5=7$ and $G_5=2\cdot 5=10$

Let's fix an $i=i_0$. The formula states that there is an $n\leq \prod_{j=1}^{i_0} p_j$ such that $\forall m \in \{n+1,n+2p_{{i_0}-1}-1\}$, $$\gcd(\prod_{j=1}^{i_0} p_j,m)=p_{j_0}\text{, for some}~j_0 \leq i_0$$

• Thanks for your comment. Here is a proof that 2 x previous prime is not the maximal gap, but the lowest bound of the maximal gap. If you take the set of primes {2,3,5,7....p_n-1, p_n), by the Chinese remainder theorem you can derive an x such that x = 0 mod N (where N = 2x3x5x7....p_n-2) | x = 1 mod p_n-1 | x = -1 mod p_n This would create a gap of 2p_n-1 centred around x. Thus the lowest bound of the maximal gap is 2p_n-1. Comparing 2p_n-1 with the Jacobstahl conjecture it seems they match for the first few pairs as Charles mentioned, and then diverge. – Mister Dog Feb 8 '14 at 4:30

Thanks to Charles, who made me aware of the Jacobsthal function applied to the product of the first n primes. This seems to have answered my question completely. I only have two additional questions...

1) According to the OEIS page https://oeis.org/A048670 , a(n) << n^2 ln(n), where n is the nth prime. Does anyone know if there is a result in terms of the maximum prime p, rather than n? So for example, if dealing with the 5th prime 11, a result in terms of 11, instead of 5 (as is in the OEIS page)?

2)Is there a reason why the Jacobsthal function applied to the product of the first n primes is so "irregular"? I spent ages trying to figure out a way to construct the longest gaps or equivalently, the longest sequences of integers that are coprime to a primorial.. and as you can imagine it was an exercise in futility.