Question

I bet if you give me any number, I can find an interval where there are no prime numbers.

For instance, if you give me 3, I will tell you look between 7 and 11 and you will find that 8, 9 and 10 are your 3 non prime numbers.

Answer 1

42.

Answer 2

Ok check between 60415263063373835637355132068513997507264512000000002 and 60415263063373835637355132068513997507264512000000043 inclusive =P

Answer 3

why you gotta make it soooo harddddddddddd

Answer 4

Since OS is questionable between working and broken, I'll go ahead and post the secret:

n!+2 to n!+n are the end points I'm using since we know that all consecutive numbers there are composite. Here's an example if we want a gap of 5 numbers we look here:

6!+2, 6!+3, 6!+4, 6!+5, 6!+6

See, all 5 of these are consecutive and we can divide the first by 2, the second by 3, the next by 4, etc... haha. XD

Answer 5

So there are a billlion consecutive non prime numbers between (a billion and one)!+2 and (a billion and one)! + (a billion and one)

Answer 6

we can find a sequence of smaller consecutive composite numbers. check 42 integers starting from :

1017800908206812

Answer 7

Oh instead of n! you're using the lcm(1...n) I think? So like instead of 6! you're just using 2^2 * 3^1 * 5^1 since it will be divisible by the same amount of numbers.

Answer 8

i have used chinese remainder thm and eliminated most of the repeated factors... it is a similar idea as lcm stuf..

Answer 9

the method is straightforward if we are familiar with inverses and chinese remainder thm.
we want to find \(x\) such that the sequence \(\{x, x+1, x+2, \cdots, x+n-1\}\) has \(n\) composite integers.

for n=42, after playing with sieve of eratosthenes a bit, we arrive at below linear congrunces which can be solved by using chinese remainder thm :
\[\begin{align} y &\equiv 1\pmod {3\cdot 5\cdot 7\cdot 13\cdot 19\cdot 31 }\\~\\y &\equiv 2\pmod{11\cdot 17\cdot 23\cdot 41} \\~\\&y\equiv 3\pmod{29\cdot 37}\end{align}\]

solving gives \(y \equiv 508900454103406 \pmod{\frac{13\#}{2}} \)
\(x = 2y\) are the starting integers of sequences of 42 consecutive composite numbers

Answer 10

My internet/OS wasn't working lately so I had to leave. I have heard of the Chinese remainder theorem before but can't say that I understand it too well, but I kind of get the idea. I thought I understood the sieve of eratosthenes but I am not sure how you came up with a system of equations doing so.

Can you maybe show a few more steps, I'm not seeing how you figured out that solving these 3 congruences would give us an answer.

Answer 11

yea sure nobody will understand as it was just an outline :)

Answer 12

Haha ok good, I am ready to learn now =)

Answer 13

we can split those 3 congruences into a system of 13 congrunces (number of primes less than or equal to 42)

Answer 14

we will be using below result :
If
\(x = a \pmod{p_1}\)
\(x = a \pmod{p_2}\)

then \(x\equiv a \pmod {p_1\times p_2}\)

Answer 15

all it says is that if \(x-a\) is divisible by \(p_1\) and \(p_2\) then it is also divisible by \(p_1\times p_2\)

Answer 16

for example :
7-1 is divisible by 2 and 3
so 7-1 is also divisble by 2*3

Answer 17

Does p1 and p2 have to be prime, or only relatively prime?

Answer 18

for our proof lets follow the convention \(p_i\) means prime and all other variables are random integers

Answer 19

I'm not sure I understand what x and a represent in these equations:

\(x = a \pmod{p_1}\)
\(x = a \pmod{p_2}\)

then \(x\equiv a \pmod {p_1\times p_2}\)

Can I just replace it like this then?

\(0 = 6 \pmod{2}\)
\(0 = 6 \pmod{3}\)

then \(0\equiv 6 \pmod {6}\)

Answer 20

yes that looks fine
i made a notation mistake : \(=\) should be replaced with \(\equiv\)

Answer 21

here is the definition of congrunce expression :

\(x \equiv a \pmod {n}\) means \(x-a\) is divisible by \(n\)

Answer 22

\(13\equiv 1 \pmod {3}\)
\(13\equiv 1 \pmod {4}\)

so we have \(13\equiv 1 \pmod{3\times 4}\)

Answer 23

Ok I see that now, I guess I need to play around with it a little more since this seems true in particular but I don't really see how I'd find this in general

\(7\equiv 1 \pmod{2}\)
\(7 \equiv1 \pmod{3}\)

then \(7\equiv 1 \pmod {6}\)

It is kind of interesting to me to understand this because it seems like a very useful trick to understand. Maybe we should just move forward with the problem and it will become more clear when we're done if you like and I'll ask more questions later.

Answer 24

proof is trivial but yeah lets get back to this in the end maybe

Answer 25

The rule seems more obvious if you're reversing it, suppose I have

\(1\equiv 21\pmod {20}\)

which is pretty simple to find, then I can just say:

\(1\equiv 21\pmod {4}\) or \(1\equiv 21\pmod {5}\)

ok I think I get it well enough, I just want to be able to use it better. Onwards!

Answer 26

yes getting back to our original problem,
we want to find \(x\) such that \(x, x+1, x+2,\cdots, x+{n-1}\) are composite.

it is easy to see that we can construct these composite numbers by making each of them divisible by our chosen prime numbers.

lets make \(x\) composite by making it divisible by \(2\) :
\[x \equiv 0 \pmod{2}\]

It follows that all the numbers of form \(x+2k\) in our list are divisible by \(2\) as well.
Notice this constraint on \(x\) makes half of the numbers in our list composite

Answer 27

thats our first congruence in the system ^

Answer 28

This makes sense so far

Answer 29

so far, we are starting with an even number and our next goal is to make all the odd numbers in our list composite

Answer 30

if it helps imagine we removed all the numbers of form x+2k and we focus on below reduced list :
{x+1, x+3, x+5, x+7, ... }

Answer 31

we know none of these are divisible by 2
so a natural thing to constrain is to let x+1 divisible by 3 :
\[x+1\equiv 0 \pmod{3}\]

Notice again, this makes all the numbers of form \(x+1+3k\) in our list divisible by 3 as well. Essentially this constrains 1/3 of the numbers in our list

Answer 32

keep reducing the list till it vanishes gives a set of congruences

Answer 33

Alright so I see how we're pulling in the sieve. Eventually we will have covered all the numbers this way after creating a couple of equations and then using CRT we can solve I suppose. Now I kind of feel like I understand more or less what the plan is.

Answer 34

Exactly ^

Answer 35

with this method we will get 13 congrunces as there are 13 primes <= 42

we combine them using the result we saw earlier and make it simple for feeding into CRT

Answer 36

btw CRT doesnt bother about number of congrunces... we can work all the 13 congruences separately but it just takes too many steps..

Answer 37

Oh ok, so the 3 equations you came up with to solve were just a random choice you could have made 2 or 4 equations if you wanted?

Answer 38

we can split those 3 congrunces into exactly 13 simpler congruences

Answer 39

\[y\equiv 3\pmod{29\cdot 37}\]

splits into
\[y\equiv 3\pmod{29}\]
\[y\equiv 3\pmod{ 37}\]

Answer 40

we are allowed to do that because if \(p_1\times p_2\) divides \(t\) then each of the primes divide \(t\) as well

Answer 41

for example 3*7 divides 63,
so 3 divides 63 and 7 divides 63

Answer 42

Ok, right because of the same rules of earlier that we talked about.

Answer 43

yes the reverse of this is bit more interesting :)

Answer 44

\(p_1\times p_2 | a \implies p_1|a\) and \(p_2|a \)

yeah most of the properties of primes we are using in this thread also work for coprime integers

Answer 45

this is equivalent to the property we talked about earlier:
\(p_1|a \) and \(p_2|a\) \( \implies~p_1p_2 | a\)

Answer 46

So how are we determining 1,2,3 as the numbers in the three equations?

Answer 47

right, thats the only missing piece

Answer 48

we need to continue reducing the list to see that

Answer 49

so far we have
\[\begin{align}x&\equiv 0 \pmod{2}\\
x+1&\equiv 0\pmod{3}
\end{align}\]

continuing the previous process further gives below set of extra congruences
\[\begin{align}x+3&\equiv 0 \pmod{5}\\
x+5&\equiv 0\pmod{7}\\
x+7&\equiv 0\pmod{11}\\
x+11&\equiv 0\pmod{13}\\
x+13&\equiv 0\pmod{17}\\
x+17&\equiv 0\pmod{19}\\
x+19&\equiv 0\pmod{23}\\
x+23&\equiv 0\pmod{29}\\
x+29&\equiv 0\pmod{31}\\
x+31&\equiv 0\pmod{37}\\
x+37&\equiv 0\pmod{41}\\

\end{align}\]

Answer 50

they all reduce to one of the four remainders from {0,2,4,6}
making x = 2y reduces it to remainders {1,2,3}

Answer 51

I see, so essentially we can combine (x+3 mod 5) with (x mod 3) to make (x mod 15)

Answer 52

kindof.. let me break the steps

Answer 53

\[

\begin{align}
x&\equiv 0 \pmod{2} \implies x\equiv 0 \pmod{2}\\
x+1&\equiv 0\pmod{3}\implies x\equiv 2\pmod{3}\\
x+3&\equiv 0\pmod{5} \implies x\equiv 2\pmod{5}\\
x+5&\equiv 0\pmod{7} \implies x\equiv 2\pmod{7}\\
x+7&\equiv 0\pmod{11} \implies x\equiv 4 \pmod{11}\\
x+11&\equiv 0\pmod{13} \implies x\equiv 2\pmod{13}\\
x+13&\equiv 0\pmod{17} \implies \cdots \\
x+17&\equiv 0\pmod{19}\\
x+19&\equiv 0\pmod{23}\\
x+23&\equiv 0\pmod{29}\\
x+29&\equiv 0\pmod{31}\\
x+31&\equiv 0\pmod{37}\\
x+37&\equiv 0\pmod{41}\\

\end{align}
\]

Answer 54

Alright sorry I'm getting ahead of myself here XD

Answer 55

notice how the remainders are just one of {0, 2, 4, 6}
so we combine the congruences with same remainders using the earlier result...

Answer 56

x leaves a remainder of 2 when it is divided by 3, 5, 7, 13, 19, 31

we combine all of them as one congrunce :
\(x\equiv 2\pmod {3\cdot 5\cdot 7 \cdot 13\cdot 19\cdot 31} \)

Answer 57

we combine remaining congruences based on remaining remainders

Answer 58

brb going for eating..

Answer 59

Alright I'll see if I can figure the rest of it out.

Answer 60

can it be any integer?