44
$\begingroup$

Hello and I'm quite new to Math SE.

I am trying to find the largest consecutive sequence of composite numbers. The largest I know is:

$$90, 91, 92, 93, 94, 95, 96$$

I can't make this series any longer because $97$ is prime unfortunately.

I can however, see a certain relation, if suppose we take the numbers like (let $a_1, a_2, a_3,...,a_n$denote digits and not multiplication):

$$a_1a_2a_3...a_n1,\ a_1a_2a_3...a_n2,\ a_1a_2a_3...a_n3,\ a_1a_2a_3...a_n4,\ a_1a_2a_3...a_n5,\ a_1a_2a_3...a_n6,\ a_1a_2a_3...a_n7,\ a_1a_2a_3...a_n8,\ a_1a_2a_3...a_n9,\ a_1a_2a_3...(a_n+1)0$$

The entire list of consecutive natural numbers I showed above can be made composite if:

  1. The number formed by digits $a_1a_2a_3...a_n$ should be a multiple of 3
  2. The numbers $a_1a_2a_3...a_n1$ and $a_1a_2a_3...a_n7$ should be composite numbers

If I didn't clearly convey what I'm trying to say, I mean like, say I want the two numbers (eg: ($121$, $127$) or ($151$, $157$) or ($181$, $187$)) to be both composite.

I'm still quite not equipped with enough knowledge to identify if a random large number is prime or not, so I believe you guys at Math SE can help me out.

$\endgroup$
  • 10
    $\begingroup$ Eight consecutive composite numbers: $$9!+2,\ 9!+3,\ 9!+4,\ 9!+5,\ 9!+6,\ 9!+7,\ 9!+8,\ 9!+9,$$ $\endgroup$ – bof Jun 6 '17 at 6:50
  • 64
    $\begingroup$ ... and it works for any value of $9$... $\endgroup$ – Robert Israel Jun 6 '17 at 6:52
  • 13
    $\begingroup$ You can have list of consecutive composite numbers as long as you like. A classical example is $n! + 2, n! + 3, n!+4 + \cdots + n!+n$. This is a list of $n-1$ consecutive composite numbers. Look at OEIS A008950 for the position where you first find a list of $n$ consecutive composite numbers. $\endgroup$ – achille hui Jun 6 '17 at 6:52
  • 13
    $\begingroup$ You are looking for prime gaps en.wikipedia.org/wiki/Prime_gap. The numbers from 114 to 126 are all composite - which makes an unusually large gap between primes in comparison with the size of the numbers involved. $\endgroup$ – Mark Bennet Jun 6 '17 at 6:55
  • 6
    $\begingroup$ See, the numbers $9!\pm11$ just happen to be composite as well, so there are even more. Actually, all numbers between the primes $362867$ and $362897$ are composite! $\endgroup$ – Ivan Neretin Jun 6 '17 at 7:46
71
$\begingroup$

marwalix's answer is great, but it is possible to 'optimize' the given sequence even more using a very simple 'trick'.

Simply replace $n!$ by $n\#$, the primorial: $$n\#=\prod_{i=1}^{\pi(n)}p_i$$ The sequence now becomes: $$n\#+2,n\#+3,\ldots n\#+n$$

Say you want to find a sequence of length $15$. marwalix's original answer would give you the sequence: $$20922789888002,20922789888003,20922789888004,20922789888005,20922789888006,20922789888007,20922789888008,20922789888009,20922789888010,20922789888011,20922789888012,20922789888013,20922789888014,20922789888015,20922789888016$$ while this way of constructing the sequence gives: $$30032,30033,30034,30035,30036,30037,30038,30039,30040,30041,30042,30043,30044,30045,30046$$ and those numbers are way smaller.

Why does this work? Well say we have some $n,m\in\mathbb{N}$ with $n\#+m$ prime. Then $p\nmid n\#+m$ for all primes $p\le n$, but $p\mid n\#$ for all $p\le n$, so $p\nmid m$ for all $p\le n$. Therefore $m=1$ or $m$ is a prime greater than $n$. In any case, we won't have $2\le m\le n$, so the intergers $n\#+2,n\#+3,\ldots, n\#+n$ are all composite.

A simple algorithm

There is an algorithmic way to 'join' two primegaps together to form a new, larger prime gap. Let me give an example. By a similiar argument as before, for all non-negative integers $k$, the numbers: $$30k+20,30k+21,30k+22$$ and $$30k+24,30k+25,30k+26,30k+27,30k+28$$ are all composite, but $23$ is prime. We would like to restrict the values of $k$ such that $30k+23$ is also composite, say divisible by $7$. We solve $30k+23\equiv 0\pmod 7$: $$30k+23\equiv 0\pmod 7$$ $$2k+ 2\equiv 0\pmod 7$$ $$k\equiv 6\pmod 7$$ So write $k=7m+6$. Now the number $30k+23=30(7m+6)+23$ is divisible by $7$ and therefore composite. We get the sequence of composite numbers: $$210m+200,210m+201,210m+202,\ldots 210m+208$$ for all non-negative $m$. We also find that $210m+198$ is always composite, but $199$ is prime. We would like to restrict $m$ such that $210m+199$ is divisible by $11$. We get: $$210m+199\equiv 0\pmod {11}$$ $$m+1\equiv 0\pmod {11}$$ $$m\equiv 10\pmod {11}$$ So write $m=11k+10$. We now get that for all non-negative integers $k$, the integers $$2310k+2298,2310k+2299,\ldots,2310k+2308$$ are all composite. We can continue this process for as long as we want and there is a chance it will yield even better results than the previous approach, though I don't know for sure. (the best-case result is certainly better and the worst-case result is a lot worse, but I don't know about the average result of the algorithm)

$\endgroup$
  • 2
    $\begingroup$ Wait, I don't understand what you mean by primorial. And also in $$\sum_{i=1}^{\pi (n)}p_i$$ what does $\pi (n)$ mean? $\endgroup$ – Pritt Balagopal Jun 6 '17 at 9:29
  • 3
    $\begingroup$ @PrittBalagopal $\pi(n)$ is the amount of primes up to and including $n$. For instance $\pi(10)=4$. If you don't know what the primorial is, you should take a look at en.wikipedia.org/wiki/Primorial $\endgroup$ – Mastrem Jun 6 '17 at 9:33
  • 3
    $\begingroup$ This is a great answer! I remember watching one of Terence Tao's talks where he mentioned exactly this theme of generating gaps. My personal highlight of the talk was when he referred to generating gaps using factorials as "wasteful" and then went on to talk about the wonders of primorials. Nicely written. $\endgroup$ – Linus Rastegar Jun 7 '17 at 1:46
  • 2
    $\begingroup$ There are $17$ primes between $523$ and $541$ which are even smaller than your primorial example $\endgroup$ – Henry Jun 7 '17 at 17:26
  • 1
    $\begingroup$ @Henry You mean composite numbers, right? $\endgroup$ – Arnaud D. Jun 8 '17 at 9:47
88
$\begingroup$

You can have a sequence as long as you wish. Consider $n\in\Bbb{N}$ then the set

$$S_n=\{n!+2,n!+3,\cdots,n!+n\}$$

is made of composite consecutive numbers and is of length $n-1$

$\endgroup$
  • 8
    $\begingroup$ Item of interest: if $n\ge3$ then this set can be extended to length $n$, because $n!+1$ and $n!+n+1$ cannot both be prime. $\endgroup$ – David Jun 8 '17 at 6:04
14
$\begingroup$

Let me offer a different view to this.

Suppose there was a longest consecutive set of composite numbers. Denote the length by $L$. Then at least every $(1+L)$th natural number must be a prime, so that the density of primes, $$ \lim_{N\to\infty}\frac{\text{number of primes less than }N}{N}, \tag{1} $$ is at least $1/(L+1)$.

However, the density is zero: the bigger $N$ is, the smaller the fraction of primes in the set $\{1,\dots,N\}$. (Well, not exactly. The limit is zero, but the sequence is not monotone. The point should be clear enough, though.) But since $0<1/(L+1)$, we have a contradiction. Therefore there cannot be a longest run of composite numbers.

The only non-elementary part is the fact that the limit (1) is indeed zero. For example, this follows from the prime number theorem, which asserts that the ratio in (1) is roughly $1/\log(N)$.

$\endgroup$
4
$\begingroup$

There is definitely something to be said, again, in terms of the compound arithmetic progression for James Maynard's concept of Large Gaps. Not only does this require us to go far beyond the simple Twin Prime sieve in the $\sigma$-ring of compound arithmetic progressions, it requires a description of De Polignac's Conjecture (1849) as a sequence in that ring to go beyond primorial descriptions of the largest prime gap under a magnitude or interval of consecutive composite numbers.

Conjecture (De Polignac, 1849). If $\mathbb{P}^{\gamma} = \{p_i, p_{i+1}\} \subset \mathbb{P}$ and $p_{i+1} -p_i= 2n$, for any given $n \in \mathbb{Z}^+$, there exist infinitely many $\mathbb{P}^{\gamma}$ satisfying the relation.

Proof is not part of the problem. Look up on Vixra if you want a more precise topological definition; a 2015 paper by a professor from Morocco is superbly concise and draws upon Fürstenberg's topological proof of the infinitude of primes in no uncertain terms. The numerical landmarks are obtained from compound arithmetic progressions, however, which I have already described in my answer to Prime Gaps in Residue Classes.

Conjecture. Let $\Delta \mathbb{P}_2$ be defined as the set of numbers for which $$\lambda \in \Delta \mathbb{P}_2 \implies \{6\lambda -1, 6\lambda +1\}\subset \mathbb{P} $$

Then if we let $T_C(r, m)$ be the composite topology in $[r]_m$ $$\Delta \mathbb{P}_2 = \mathbb{Z}^+ \setminus \bigcup_{r\in (\mathbb{Z}/6\mathbb{Z})^*}\{ T_C(r,6) \}$$

And expanding out to each matrix representation of the compound arithmetic progressions produced we can write $\Delta \mathbb{P}_2$ such that it is an element of the $\sigma$-ring of compound arithmetic progressions using the following shorthand (again, see the definition of the matrix representation):

$$\Delta \mathbb{P}_2 = \mathbb{Z}^+ \setminus \bigcup \{ M^{-1} \begin{pmatrix} -1 & n \\ 6 & 1 \end{pmatrix}, M^{-1} \begin{pmatrix} 1 & n \\ 6 & -1 \end{pmatrix}, M^{-1} \begin{pmatrix} 1 & n \\ 6 & 1 \end{pmatrix}, M^{-1} \begin{pmatrix} -1 & n \\ 6 & -1 \end{pmatrix} \}$$

For a gap size of 4, $\lambda \in \Delta \mathbb{P}_4$ implies that $\{6\lambda + 1, 6\lambda+5\} \subset \mathbb{P}$. The reasoning is that the use of negative numbers for the residue should be minimized and that this $6\lambda + 5 = 6(\lambda + 1) - 1$, so that the only difference between $\Delta \mathbb{P}_2$ and $\Delta \mathbb{P}_4$ is that one of the subtracted composite topologies is the translate in the representation.

$$\Delta \mathbb{P}_4 = \mathbb{Z}^+ \setminus \bigcup \{ T_C(1,6), T_C(-1,6) \oplus 1 \}$$

And $\lambda \in \Delta \mathbb{P}_6$ implies that $\{6\lambda - 1, 6\lambda +5\} \subset \mathbb{P}$ and ${6\lambda + 1} \not\in \mathbb{P}$ or $\{6\lambda + 1, 6\lambda + 7\} \subset \mathbb{P}$ and ${6\lambda + 5} \not\in \mathbb{P}$. So there is, in fact, two possible k-tuples, both with a composite region.

In terms of this structure, the composite topologies representing the composite region in the k-tuple ensure that the frontier prime elements are consecutive in the sequence of prime numbers, and therefore form an intersection of similarly translated composite topologies.

Therefore the results for $\Delta \mathbb{P}_6$ and the De Polignac sequence $\Delta \mathbb{P}_{2n}$ are as follows (in terms of composite topologies):

If $n\in \{1\pmod{3}\}, k := \frac{n-1}{3}$ $$\Delta \mathbb{P}_{2n} = \bigcap^{k}_{m=0}\{T_C(1,6) \oplus m \cap T_C(-1,6) \oplus (m+1)\} \setminus \bigcup\{ T_C(-1,6) \cup T_C(1,6)\oplus k\}$$

If $n\in \{2\pmod{3}\}, k := \frac{n-2}{3}$ $$\Delta \mathbb{P}_{2n} = \bigcap^{k}_{m=0}\{T_C(1,6) \oplus (m+1) \cap T_C(-1,6) \oplus (m+1)\} \setminus \bigcup\{ T_C(1,6) \cup T_C(-1,6)\oplus (k+1)\}$$

And finally if $n \in \{ 0\pmod 3\}, n>0$ there are again, two ways to form the k-tuple for the gap, so in terms of composite toplogies:

$$\Delta \mathbb{P}_{2n} = \{\bigcap^{k}_{m=0}\{T_C(1,6) \oplus m \cap T_C(-1,6) \oplus (m+1)\} \cap \{T_C(1,6)\oplus k\}\} \setminus \bigcup\{ T_C(-1,6) \cup T_C(-1,6)\oplus (k+1)\} \cup $$ $$ \{\bigcap^{k}_{m=0}\{T_C(1,6) \oplus (m+1) \cap T_C(-1,6) \oplus (m+1)\} \cap \{T_C(-1,6)\oplus (k+1)\}\} \setminus \bigcup\{ T_C(-1,6) \cup T_C(-1,6)\oplus (k+1)\} $$

Which is what I was able to derive for the general form of the De Polignac Sequence in the above mentioned ring. And it is possible to analyze the infima of each element of the sequence or for a gap size that you are more curious about, or if you want to find a sequence of consecutive composite numbers . That's how it's done. Large gaps is a difficult problem. The notation looks like the machine language of a computer and it could take a volume to try to decompile it. But $\phi(6) = 2$, so there are at most 2 CAPs per composite topology and then in the long hand $inf \bigcup{[ax+b]^+_{(cx+d)}} = (a+c)x+(b+d)$, it is possible to use the case where $x:=1$ so that the figure becomes $a+b+c+d$, where the matrix form is $\begin{pmatrix} -a & n-b \\ c & d \end{pmatrix}$

Have fun with that, for now.

$\endgroup$
  • $\begingroup$ This is a summary of a "brut force" method in terms of a "weak"-type sieve. $\endgroup$ – user1329514 Aug 13 '17 at 2:29
4
$\begingroup$

In addition to @marwalix's answer:

It is basically very basic result in study of prime numbers. It is usually stated as a theorem in number theorem books:

There are arbitrarily large gaps in the series of primes and an equivalent statement is Given any positive integer $k$, there are $k$ consecutive composite integers.

We generate these $k$ consecutive integers as $(k+1)!+2,(k+1)!+3,(k+1)!+4,(k+1)!+5,\cdot\cdot\cdot\cdot (k+1)!+(k+1)$. Note that every $(k+1)!+j$ in this sequence is divisible by $j$ so each of these is composite.

Interestingly, this theorem gives us an idea that primes are spaced rather irregualarily which is why we do not expect a simple formula for $\pi(n)$.

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