I'm trying to find the longest consecutive set of composite numbers

Question

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.

Answer 1

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$

Answer 2

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)

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

I wish to point out 2 ideas which arent as good as the primorial idea nor as good as some of the other ideas, but which are enhancements of the idea mentioned that $n!+2, n!+3, n!+4, .... n!+n$ are composite, which is that

$n!-2, n!-3, n!-4, ... n!-n$ will be composite provided $n!-m=(n!/m-1)*m$ has both factors greater than 1 for $m=2,3,...n$. clearly the second factor $m$ is ok, for the other factor we need $n!/m-1>=2$ ie $n!/m>=3$ ie $n!>=3m$, this will be true for all the $m$ if $n!>=3n$ ie $(n-1)!>=3$ which is true if $n-1>=3$, ie $n>=4$

so for $n>=4$, the consecutive numbers $n!-2, n!-3, ...., n!-n$ are composite!

The other enhancement is that if $N=lcm(2,3,4,5,6,...,n)$, then $N-2,N-3,...,N-n$ are composite provided $N-m=(N/m-1)*m$ has both factors greater than 1. The second factor is clearly alright.

so we need $N/m-1>=2$ ie $N/m>=3$ ie $N>=3*m$. Now $(m-1)$ and $m$ are coprime, so $N>=(m-1)*m$. Thus for $m-1>=3$ ie $m>=4$ this is true. We thus need to check $m<4$ namely $m=2,3$. for $m=2$ we need $N>=3*2=6$ which will be true for $n>=3$ because 2 and 3 are coprime and thus $N>=2*3=6$. And for $m=3$ we need $N>=3*3=9$ which will be true for $n>=4$ because 3 and 4 are coprime, hence $N>=3*4=12>9$.

so for $n>=4$, $N-2, N-3, ...., N-n$ are composite!

I agree entirely that this is not as good a result as some of the other ones given, but I give this as the idea simply because it is different and somewhere in between the results given.

Here follows an enhancement of the primorial argument:

if we consider $n\#-2, n\#-3,...,n\#-n$, and choose $2<=m<=n$, and let $p$ be a prime factor of $m$, then $p$ is a factor of both $n\#$ and $m$. So $n\#-m=p*((n\#-m)/p)$, and this is composite if the second factor is greater than 1, ie $(n\#-m)/p>1$, ie $n\#>p+m$. If we can show that $n\#>=3n$ for $n>=5$, then $n\#>=3n>p+m$ and thus $n\#-m$ is composite.

In fact via another post, $n\#>=3m$ for $n>=5$, namely:

Prove by elementary means that $n\#\geq 3n$ for $n\geq 5$, where $n\#$ is the primorial function.

so for $n>=5$, $n\#-2, n\#-3,...,n\#-n$ are consecutive composite numbers in descending order. The result is false for $n=4$ because $4\#-3=3$ and $4\#-4=2$ which are primes.