Prime Gap Length with consecutive integers divisible by small primes

[carpetpool]

I see this sub-forum is about prime gaps, and a long list of consecutive composites can be obtained by restricting that each number from n to n+k has at least one prime factor < s where s is the factor bound.

For instance there are at most 5 consecutive integers such that each of them is divisible by 2, 3, or 5. There at most 9 consecutive integers such that each of them is divisible by 2, 3, 5, or 7. This pattern continues here. Does someone know the modular congruence for 257 consecutive integers, each of them is divisible by at least one prime less than 100? Thanks if so.

Here, there is a 159 "minimum" prime gap, since each integer from n to n+158 is divisible by either 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, or 97. n = 1447667319088187212520359882964797112

According to the Oeis sequence I found, there are at least 98 more integers that can be divisible by at least one of the primes < 100 (257 total). I could have written out the modular congruence for the example I gave, but it would take too long, so I used factordb.com instead.

[robert44444uk]

Originally Posted by carpetpool

I see this sub-forum is about prime gaps, and a long list of consecutive composites can be obtained by restricting that each number from n to n+k has at least one prime factor < s where s is the factor bound.

...

Does someone know the modular congruence for 257 consecutive integers, each of them is divisible by at least one prime less than 100? Thanks if so.

I don't know about 257 - recently I looked at a gap of 2310 with 113 primes providing cover and the results of that were posted at

http://www.mersenneforum.org/showthread.php?t=20825

[science_man_88]

Originally Posted by carpetpool

I see this sub-forum is about prime gaps, and a long list of consecutive composites can be obtained by restricting that each number from n to n+k has at least one prime factor < s where s is the factor bound.

For instance there are at most 5 consecutive integers such that each of them is divisible by 2, 3, or 5. There at most 9 consecutive integers such that each of them is divisible by 2, 3, 5, or 7. This pattern continues here. Does someone know the modular congruence for 257 consecutive integers, each of them is divisible by at least one prime less than 100? Thanks if so.

Here, there is a 159 "minimum" prime gap, since each integer from n to n+158 is divisible by either 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, or 97. n = 1447667319088187212520359882964797112

According to the Oeis sequence I found, there are at least 98 more integers that can be divisible by at least one of the primes < 100 (257 total). I could have written out the modular congruence for the example I gave, but it would take too long, so I used factordb.com instead.

each prime lowers the number of values left that can divide by the other primes after deleting all even numbers 1/3 of the remaining will divide by 3 key word heere is remaining so only 1/3*1/2 = 1/6 of all numbers need three to be eliminated at the earliest possible. there will be 2/6 or 10/30 of the number remaining after that 2/6 *1/5 = 2/30 are deleted after that point etc. this will help set the number of primes needed as the next one eliminates 1/7 of the remaining roughly which is 8/30 *1/7 = 8/210 of course this doesn't actually happen this way completely because all multiples of 2,3, and 5 are eliminated so 2*7, 3*7, 4*7, 5*7, 6*7, 8*7,9*7,10*7,12*7,14*7,15*7,16*7,18*7,20*7,21*7,22*7,24*7,25*7,26*7,27*7,28*7,30*7 .... are all eliminated shifted to match the correct alignment.

[carpetpool]

Sm88, I formed my example above my matching numbers that have not been "eliminated" with other factors I have not used yet. For example,

let

(2*3*5*7*13*17*19*29*31*37*41*43*47*53*59*61*71*73*79*83*97) | n

11 | n+1

Now each number k that is 1 (mod 11), 11 | n+k. In this case, n+{23, 67, 89} are all divisible by 11, so making each of them (23, 67, and 89) not divide n "saves" prime numbers we could align later with numbers that don't have a specified factor < 100. If

n-1 | 23

and

n+11 | 67, n-11 | 89

or

n+11 | 89, n-11 | 67

There are now at least 123 consecutive integers such that each is divisible by a prime < 100. Here n-22 = 1962136467370308094802867946933361058.

[science_man_88]

Originally Posted by carpetpool

Sm88, I formed my example above my matching numbers that have not been "eliminated" with other factors I have not used yet. For example,

let

(2*3*5*7*13*17*19*29*31*37*41*43*47*53*59*61*71*73*79*83*97) | n

11 | n+1

Now each number k that is 1 (mod 11), 11 | n+k. In this case, n+{23, 67, 89} are all divisible by 11, so making each of them (23, 67, and 89) not divide n "saves" prime numbers we could align later with numbers that don't have a specified factor < 100. If

n-1 | 23

and

n+11 | 67, n-11 | 89

or

n+11 | 89, n-11 | 67

There are now at least 123 consecutive integers such that each is divisible by a prime < 100. Here n-22 = 1962136467370308094802867946933361058.

you can basically create a gap on any length the real hard part I think is finding the first time it happens or the lowest in a set of gaps. at n! for example n!+2 divides by 2 n!+k divides by k the only case that could be prime between certain values is n!+1 for k<n at least.

[carpetpool]

Things are simpler when dealing with n# (product of all primes less than n). Just remove one prime factor q from n# (but not 2) and divide n# by all the prime congruent to 1 (mod q). You can use all the primes 1 (mod q) to align with other numbers which don't have a specified factor < 100, which is what I did.

Another alternative is by trial and error:

choose some starting value n and find a prime factor < 100 for all numbers n, n+1, n+2, n+3,..... n+200.

2 | n, and 2 | n+k if k is even

Find the number of integers relatively prime to 2 less than 200, and take each one mod 3. Take the modulo result that occurs the most (either 0, 1, or 2) and which ever one it is (actually it is 1) align 3 as a factor for that specific modular group. Eg.

3 | n+1, and 3 | n+k for all k = 1 (mod 3).

Do this with 5 (find all the numbers relatively prime to 6 less than 200 and take each one mod 5, and find the mode m, of the modular results) Align n+m | 5.

And so on.

I find this approach practically useless in some cases because the previous modular congruence will affect the next prime's congruence and so on. There are 2305567963945518424753102147331756070 to which all the prime factors can be aligned, about half of these combinations are impossible because of the congruence divisibility by 2.

[science_man_88]

Originally Posted by carpetpool

Things are simpler when dealing with n# (product of all primes less than n). Just remove one prime factor q from n# (but not 2) and divide n# by all the prime congruent to 1 (mod q). You can use all the primes 1 (mod q) to align with other numbers which don't have a specified factor < 100, which is what I did.

Another alternative is by trial and error:

choose some starting value n and find a prime factor < 100 for all numbers n, n+1, n+2, n+3,..... n+200.

2 | n, and 2 | n+k if k is even

Find the number of integers relatively prime to 2 less than 200, and take each one mod 3. Take the modulo result that occurs the most (either 0, 1, or 2) and which ever one it is (actually it is 1) align 3 as a factor for that specific modular group. Eg.

3 | n+1, and 3 | n+k for all k = 1 (mod 3).

Do this with 5 (find all the numbers relatively prime to 6 less than 200 and take each one mod 5, and find the mode m, of the modular results) Align n+m | 5.

And so on.

I find this approach practically useless in some cases because the previous modular congruence will affect the next prime's congruence and so on. There are 2305567963945518424753102147331756070 to which all the prime factors can be aligned, about half of these combinations are impossible because of the congruence divisibility by 2.

you could use the PARI/gp console program chinese command

[carpetpool]

I use perl ntheory module for that: https://metacpan.org/pod/ntheory

[CRGreathouse]

Originally Posted by carpetpool

I use perl ntheory module for that: https://metacpan.org/pod/ntheory

Yes, that's another great tool for that purpose.

[science_man_88]

Originally Posted by carpetpool

I use perl ntheory module for that: https://metacpan.org/pod/ntheory

in PARI you could also use fold() to do it for a vector of modular remainders in a row you could also just think about how all primes greater than 3 are 1 or 5 mod 6 and go from there as then 258/6 = 43 and at most 2 in each set of those to check so a total of 86 that haven't got knocked out by 2 and 3 on average.

[carpetpool]

FYI I have Pari/GP too. However the perl ntheory module uses less memory on my computer than the Pari/GP interface so I use that more often.