"A First Course in Number Theory" discussion group

[alpertron]

Originally Posted by science_man_88

or we can do N=4 and use 0 mod 2,2 mod 3 and 4 mod 5 and get the lowest example 24,25,26,27 which will always repeat mod 30. we can also increase this to N=5.

24 is not congruent to 2 mod 3.
With my previous setting we have a=2 (mod 30), so I had to select a=32 to avoid a prime. But if we know that N>=3, we can use a=0 (mod 2), a=0 (mod 3), a=4 (mod 5) and so on and in that case we get a=24.

For N=7, using the same idea: a=0 (mod 2), a=0 (mod 3), a=4 (mod 5), a=2 (mod 7). Thus we get M = 2*3*5*7 = 210, a=114.
So the seven consecutive numbers would be 114 (multiple of 2), 115 (multiple of 5), 116 (multiple of 2), 117 (multiple of 3), 118 (multiple of 2), 119 (multiple of 7), 120 (multiple of 2).

[science_man_88]

Originally Posted by alpertron

24 is not congruent to 2 mod 3.
With my previous setting we have a=2 (mod 30), so I had to select a=32 to avoid a prime. But if we know that N>=3, we can use a=0 (mod 2), a=0 (mod 3), a=4 (mod 5) and so on and in that case we get a=24.

For N=7, using the same idea: a=0 (mod 2), a=0 (mod 3), a=4 (mod 5), a=2 (mod 7). Thus we get M = 2*3*5*7 = 210, a=114.
So the seven consecutive numbers would be 114 (multiple of 2), 115 (multiple of 5), 116 (multiple of 2), 117 (multiple of 3), 118 (multiple of 2), 119 (multiple of 7), 120 (multiple of 2).

sorry typo 0 mod 3 but the point was that there was a lower set and that mod 30 it repeats infinitely often.

[davar55]

Originally Posted by davar55

I don't understand this poster. Is he entitled to an answer?

Originally Posted by chalsall

Yes.

ok, no problem.

By the way, the series 32,33,34,35 contains four composites, but 36 is also composite.
What is the smallest sequence of N composites P+1,P+2,...,P+N with P and P+N+1 prime?

[LaurV]

Originally Posted by davar55

What is the smallest sequence of N composites P+1,P+2,...,P+N with P and P+N+1 prime?

Well, it would not make much sense for an even N, would it?
Of course, except 2, all primes are odd, therefore there is number of odd numbers between two odd numbers.
In his example N=4, therefore at least 5 composites must be there, if there are 4.
The smallest example for 4 (5) is 23-29. See prime gaps...
31-37 in the example is the second.





[edit: link and link, and many other links]
[edit 2: remark that for example gap 14 (i.e. 13 composites) appears before gap 10 (9) and gap 12 (11 composites), so again, it depends how you count]

[axn]

Originally Posted by alpertron

An idea that SM88 told me by PM in order to reduce the value of a is to reuse the factor 2 for not only the first congruence but for all odd congruences. In the case N=4 we would get a=0 (mod 2), a=2 (mod 3) and a=2 (mod 5), thus M=30 and a=32. This generates the four composite numbers 32, 33, 34 and 35.

In this case it would be difficult to express the result using a formula.

This can be generalized to all primes, not just 2. Sort of like SoE.

a = 0 (mod 2) ==> a+2, a+4, ... can be "sieved out"
a+1 (the first one not yet sieved out = 0 (mod 3) ==> a+7, a+13, a+19, ... can be sieved out
a+3 = 0 (mod 5) ==> a+13, a+23, ... can be sieved out
and so on.
Then only solve for the set of first congruence for each prime.

EDIT:- This effectively boils down to having an array of N elements with the ith element equal to the smallest factor of i. This obviously requires all primes <= N, and thus the number will be about N# But then, we can do much better by running the index from -(N/2) to (N/2). So now we need only primes <= N/2 and so the size will be roughly halved to (N/2)#

[alpertron]

But in this case it would not be possible to find an explicit formula for the first number of the sequence.

[axn]

Originally Posted by henryzz

A formula/algorithm that would work for any N.

Originally Posted by alpertron

But in this case it would not be possible to find an explicit formula for the first number of the sequence.

Formula, no. Algorithm, yes. The difference in size is big: P(N)# vs N# vs (N/2)#

EDIT:- If search is allowed, just look for m*(N/2)#, with m running from 1,2,... Except for m*(N/2)+/-1, everything in the range m*(N/2)+/-N is trivially composite. You'll probably get lucky with m=1 itself such that (N/2)#+/-1 is also composite.

[chris2be8]

Originally Posted by LaurV

Well, it would not make much sense for an even N, would it?

Except for N=0 since there are 0 composites between 2 and 3.

Chris

[science_man_88]

Originally Posted by axn

Formula, no. Algorithm, yes. The difference in size is big: P(N)# vs N# vs (N/2)#

EDIT:- If search is allowed, just look for m*(N/2)#, with m running from 1,2,... Except for m*(N/2)+/-1, everything in the range m*(N/2)+/-N is trivially composite. You'll probably get lucky with m=1 itself such that (N/2)#+/-1 is also composite.

I think you meant

(13:36) gp > forprime(x=30030-26,30030+26,print(x))
30011
30013
30029
30047

30030 being the first primorial determined not have the +1 side not be prime. however the first to have -1 and +1 not be prime is 510510.

I also think you meant (N/2)# most of the time.

[axn]

Originally Posted by science_man_88

I think you meant

Originally Posted by science_man_88

I also think you meant (N/2)# most of the time.

Correct, to both!

[science_man_88]

Originally Posted by axn

Correct, to both!

technically we can still use pn# for a though it's not always needed to be that high ( I'd think), I was mostly just suggesting that only the lowest prime divisor of the number need be used potentially. we could in theory have ways to cover more that way though with limitations it's sounding doubtful.