Consecutive integers

rebel girl 15

Having a bit of a problem with this question

Show how to write down twelve consecutive integers none of which is a prime number

My figuring is that its to show 12 composite numbers between 2 primes. Is there a formula for finding a certain gap between two primes? Honestly can't remember doing anything like it in lectures!

LeixlipRed

spent about 15 minutes thinking about this and I think you can do it using the Chinese Remainder Theorem. What I did was took 12 consecutive integers and called the first one a. Then your set C of composite numbers is {a, a+1, a+2,...,a+11}. Then I set a to be even, a+1 to be divisible by 3, a+3 to be divisible by 5 and so on. That means a = 2n and you should end up with a system of congruences in n which you can solve using CRT. Haven't done it out fully though as I should be working!

LeixlipRed

I'm not sure that works at all now tbh. Anyway, no time now to check.

bnt

Are you allowed to use Wikipedia on this topic? There's a lot of information in the Prime Gap article, including various theorems.

Fremen

LeixlipRed wrote: »

I'm not sure that works at all now tbh. Anyway, no time now to check.

Yeah, that works. Pick any twelve primes, p_1 to p_12 and apply the chinese remainder theorem to solve for x with

x = -n mod p_n

then x is the first number in your progression

Not sure I understood what you meant by a=2n, though

LeixlipRed

I just kind of forced it. Let the first number be a multiple of 2, next a multiple of 3, etc, and then you'd find one particular example. It's not the most general method, yours is that.

Fremen

Actually, I think you have to modify the construction a little. The argument outlined above only shows that each x+n is divisible by a prime p_n. That means it could actually be p_n itself, which is not what you want.

If you use p_n squared instead, then you know for sure that each x+n is divisible by the square of a prime, and therefore is composite.

Of course, you could easily check that by hand with lexlip's method.

seandoiler

can you not just use

(2.3.5.7.11.13)+2,...,(2.3.5.7.11.13)+13

this will give 12 consecutive numbers with no primes

FoxT

One bulletproof way to generate a sequence of n composite integers it to use

(n+1)! +2, (n+1)!+3, ........(n+1)! +n

The drawback with this is that (n+1)! gets enormous fast. Also it generally will not give you the lowest-value sequence of n consecutive composites.

Seandoilers line of reasoning I think is more elegant but I am not sure how to generalise it. Note that (n+1)! + 1 may be a prime. For example 3!+1 = 7.

Cheers,

FoxT

FoxT

Just re-read the OP..

"My figuring is that its to show 12 composite numbers between 2 primes"

if the question is worded exactly as you say, then I would not make that inference at all. There is not afaik a formula for finding the exact gap between 2 primes, though there are formulae that make accurate estimates of prime distribution overall.

So I think it is sufficient to just find any 12 consecutive composites.

-Foxt

seandoiler

FoxT wrote: »

Seandoilers line of reasoning I think is more elegant but I am not sure how to generalise it.

sorry should have qualified my point earlier but was just heading away...in order to generalise then i reckon as follows...

suppose we want n consecutive composite integers, find the closest prime larger than n let's call it p then proceed as follows
(2*3*5*...*p)+2,(2*3*5*...*p)+3,...,(2*3*5*...*p)+(n+1)

this should give the right answer then (i think)

FoxT

Seandoiler's explanation is spot on - and is more efficient than using (n+1)! as I outlined, because the numbers involved will be smaller. Unfortunately there is no handy function for finding the smallest prime that is greater than a given integer.

From a computer science point of view - it would be interesting to investigate which method would be more efficient in terms of resource consumption ( memory, CPU cycles, time), but that would be a digression from the OP's question!

LeixlipRed

seandoiler wrote: »

can you not just use

(2.3.5.7.11.13)+2,...,(2.3.5.7.11.13)+13

this will give 12 consecutive numbers with no primes

So simple. I love number theory

rebel girl 15

Thanks for all the replies - doing Elementary Number Theory in college, love the module but I've found it difficult in parts, just going through exam papers at the moment and that came up! I could be back again 2moro with a few more questions

Thanks!

ray giraffe

seandoiler wrote: »

sorry should have qualified my point earlier but was just heading away...in order to generalise then i reckon as follows...

suppose we want n consecutive composite integers, find the closest prime larger than n let's call it p then proceed as follows
(2*3*5*...*p)+2,(2*3*5*...*p)+3,...,(2*3*5*...*p)+(n+1)

this should give the right answer then (i think)

hmm... how small can we make them?

suppose we want n consecutive composite integers, find the largest prime no larger than n+1 let's call it p then proceed as follows
(2*3*5*...*p)-2,(2*3*5*...*p)-3,...,(2*3*5*...*p)-(n+1)

smallest for original question is 114 up to 125

goose2005

114-126 are all composite, but maybe your prof. wanted a fancier solution?

seandoiler

ray giraffe wrote: »

hmm... how small can we make them?

suppose we want n consecutive composite integers, find the largest prime no larger than n+1 let's call it p then proceed as follows
(2*3*5*...*p)-2,(2*3*5*...*p)-3,...,(2*3*5*...*p)-(n+1)

smallest for original question is 114 up to 125

of course this is pretty much equivalent to the + solution but does give a 'lower' set of numbers

not sure how the 114-125 solution is generated other than by brute force checking but is of course true

however since the OP said they were doing some form of number theory, then i'd go with either the solution proposed in my original post (or modified with the minus sign proposed by Ray)