It is easy to determine if a number is divisible by 2,3 or 5, so in my experiment i am concentrating on a consecutive list of composite numbers that are not divisible by 2,3 or 5.

My question is if there is a maximum gap limit between such numbers, and if so what is it?

Please review the image as an example:

enter image description here

  • 2
    $\begingroup$ The gap is at most $d=2\cdot3\cdot5\cdot7$. To see this look at the arithmetic progression $7+kd$, $k\in \Bbb N$. All numbers in that sequence are divisible by $7$, but not by $2,3$ or $5$. Looking at your example this $d$ is probably a very bad upper bound. $\endgroup$ – leoli1 Jan 26 at 12:00
  • 2
    $\begingroup$ The "eligible" numbers are the residue classes of $1, 7, 11, 13, 17, 19, 23, 29$ modulo $30$. Although there are infinitely many primes in each of these residue classes (Dirichlet), the density of primes becomes less as the numbers increase in value. So very likely the biggest gaps will occur earliest. $\endgroup$ – Mark Bennet Jan 26 at 12:09
  • 2
    $\begingroup$ $7×(30n+1,7,11,13,17,19,23,29)$ has a maximum gap of 42 $\endgroup$ – Empy2 Jan 26 at 12:18
  • 2
    $\begingroup$ The numbers $2310n+1260+[11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]$ between $2310n+1260+7$ and $2310n+1260+49$ have no specific reason to include a composite. They are an admissible 11-tuple, and it is conjectured that every admissible k-tuple consists of all primes for infinitely many $n$. That would give a maximum gap of 42 for all of those $n$. $\endgroup$ – Empy2 Jan 26 at 12:54
  • 2
    $\begingroup$ A gap of zero (as you have at $539$ and $637$) is pushing the definition of "gap" boldly... $\endgroup$ – Joffan Jan 26 at 13:59

I am not sure how $42$ became the answer to every question in the Universe, but it is an answer to this question. Given any composite number $N$ that is prime to $2×3×5=30$, the next larger composite number prime to $30$ must be no greater than $N+42$. The bound is proven to be a sharp one, but requires a large value of $N$ to saturate it.

By hypothesis, $N\in\{1,7,11,13,17,19,23,29\}\bmod 30$. Suppose $N\equiv 1\bmod 30$. Then we examine the next several qualifying numbers, by subtracting $1$ from each allowed residue to obtain the difference with $N$. Thus








Now watch what happens when we take residues $\bmod 7$:

$N+6\equiv N+\color{blue}{6}\bmod7$

$N+10\equiv N+\color{blue}{3}\bmod7$

$N+12\equiv N+\color{blue}{5}\bmod7$

$N+16\equiv N+\color{blue}{2}\bmod7$

$N+18\equiv N+\color{blue}{4}\bmod7$

$N+22\equiv N+\color{blue}{1}\bmod7$

$N+28\equiv N+\color{blue}{0}\bmod7$

Note that the increments shown cover all the different residues $\bmod 7$. Perforce if $N$ is one greater than a multiple of $30$, then some larger number prime to $30$ but less than or equal to $N+28$ must be composite by being a multiple of $7$. Also, since the incremental residues $1,2,3,4,5,6$ all occur earlier than $28$, that gap for $N\equiv1\bmod30$ can be achieved only if $N$ is a multiple of $7$.

What if we start with $N$ having a different residue $\bmod30$, such as $7$? If $N$ has that residue, then the increments to larger numbers prime to $30$ will be different from those above, leading to a different pattern of residues $\bmod 7$. Thus a different bound on the gap to a guaranteed multiple of $7$. Put in numbers:

$N+4\equiv11\bmod30$&$N+4\bmod 7$

$N+6\equiv13\bmod30$&$N+6\bmod 7$

$N+10\equiv17\bmod30$&$N+3\bmod 7$

$N+12\equiv19\bmod30$&$N+5\bmod 7$

$N+16\equiv23\bmod30$&$N+2\bmod 7$

$N+22\equiv29\bmod30$&$N+1\bmod 7$

$N+24\equiv1\bmod30$&$N+3\bmod 7$

$N+30\equiv7\bmod30$&$N+2\bmod 7$

$N+34\equiv11\bmod30$&$N+6\bmod 7$

$N+36\equiv13\bmod30$&$N+1\bmod 7$

$N+40\equiv17\bmod30$&$N+5\bmod 7$

$N+42\equiv19\bmod30$&$N+0\bmod 7$

In this case we cover all incremental residues $\bmod 7$, and thus assure a multiple of $7$, at $N+42$ making $42$ the maximum possible gap in this case. Here again the full gap requires $N$ to be a multiple of $7$. Given all the "extra" iterations in this case we might suppose that a different divisor, such as $11$, might produce a lower limit, but we find that covering all eleven incremental residues $\bmod 11$ also requires allowing a maximum gap of $42$.

We do a similar analysis with $N\equiv11\bmod30,N\equiv13\bmod30$, etc, and in all cases a multiple of $7$ is forced on or before $N+42$. A gap of $42$ requires $N$ to be both $\in\{7,11\}\bmod 30$ and a multiple of $7$. So if every question in the Universe is ultimately governed by gaps between composite numbers having no factors of $2,3,$ or $5$, then $42$ is indeed a universal answer.

Probalistic considerations would seem to suggest that the largest gaps would occur with smaller numbers, but gradually the maximum observed gap increases beyond the value of $28$ in the OP's original list. The smallest case that exceeds a gap of $28$ is $N=1273$, which gives a gap of $36$ up to $N+36=1309$. The numbers $1273$ and $1309$ collectively contain the prime factors $7,11,17,19$ leaving relatively few factors that might have broken up an intermediate string of four-digit primes. In the comments a gap of $38$ is reported between $113141$ and $113179$ by Joffan. Finally, Empy2 in another answer gives a gap of $42$, saturating the bound, with $N=1418575498571$ along with larger values.

  • $\begingroup$ I am sorry for pushing my limit, but do you expect the gap of 42 to end at one point, or is it expected to appear through infinity? $\endgroup$ – Isaac Brenig Jan 26 at 19:16
  • 1
    $\begingroup$ @IsaacBrenig There's a gap of $38$ between $113141$ and $113179$. This is the only gap as big as this up to a value of $200$ million. $\endgroup$ – Joffan Jan 26 at 21:45

These numbers are prime

1418575498609, 1418575498607, 1418575498603, 1418575498601, 1418575498597, 1418575498591, 1418575498589, 1418575498583, 1418575498579, 1418575498577, 1418575498573

which gives a gap of 42 between 1418575498571 and 1418575498613

They are 614101948*2310 - 1260 -[11,13,17,19,23,29,31,37,41,43,47]

Edit Suppose we look at numbers near $N$, which might be $10^{13}$.

The chance a number $x$ is prime is $1/\ln(N)$. Prime factors up to 11 are ruled out by the 2310 formula, so the chance of being prime is increased to
$$P=\frac{\frac21\frac32\frac54\frac76\frac{11}{10}}{\ln N}$$ The chance all eleven numbers are prime is $P^{11}$.
The 2310 formula gives two opportunities every 2310, namely $2310k+1260+[11,...]$ and $2310k-1260-[11,...]$
So an estimate for the number of solutions within $N/2$ of $N$, so between $N/2$ and $3N/2$, is
$$\frac{P^{11}N}{1155}$$ That suggests about 4 near $N=10^{12}$, but I have only found one.

  • $\begingroup$ Wow! so the idea that "it is very likely the biggest gaps will occur earliest" is wrong, makes me wonder what is the next 42 gap $\endgroup$ – Isaac Brenig Jan 28 at 6:38
  • 1
    $\begingroup$ My program just found 917002091*2310 - 1260 - [11,13,...] $\endgroup$ – Empy2 Jan 28 at 13:44
  • $\begingroup$ I incorporated your findings into my answer, please have a look. I believe your second $N$ in my nomenclature would be $2118274828901$. $\endgroup$ – Oscar Lanzi Jan 28 at 19:37

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.