6
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Mister Dog Feb 5 '14 at 4:46
  • $\begingroup$ 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) $\endgroup$ – Mister Dog Feb 8 '14 at 4:40
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mister Dog Feb 6 '14 at 8:55
  • $\begingroup$ 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 $\endgroup$ – Charles Feb 7 '14 at 8:36
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

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$$

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Mister Dog Feb 8 '14 at 4:30
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.