mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Prime Gap Searches

Reply
 
Thread Tools
Old 2016-12-11, 05:34   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2·3·53 Posts
Default Prime Gap Length with consecutive integers divisible by small primes

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.
carpetpool is offline   Reply With Quote
Old 2016-12-11, 18:13   #2
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

11·173 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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
robert44444uk is offline   Reply With Quote
Old 2016-12-11, 18:55   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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.
science_man_88 is offline   Reply With Quote
Old 2016-12-11, 20:20   #4
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2×3×53 Posts
Default

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.

Last fiddled with by carpetpool on 2016-12-11 at 20:41
carpetpool is offline   Reply With Quote
Old 2016-12-11, 21:13   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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.
science_man_88 is offline   Reply With Quote
Old 2016-12-11, 21:42   #6
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2×3×53 Posts
Post

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.
carpetpool is offline   Reply With Quote
Old 2016-12-11, 22:22   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-12-12, 02:33   #8
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

13E16 Posts
Default

I use perl ntheory module for that: https://metacpan.org/pod/ntheory
carpetpool is offline   Reply With Quote
Old 2016-12-12, 02:40   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111001100102 Posts
Default

Quote:
Originally Posted by carpetpool View Post
I use perl ntheory module for that: https://metacpan.org/pod/ntheory
Yes, that's another great tool for that purpose.
CRGreathouse is offline   Reply With Quote
Old 2016-12-12, 02:41   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20B116 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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.

Last fiddled with by science_man_88 on 2016-12-12 at 02:41
science_man_88 is offline   Reply With Quote
Old 2016-12-12, 04:43   #11
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

31810 Posts
Post

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.

Last fiddled with by carpetpool on 2016-12-12 at 04:43
carpetpool is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve mickfrancis Factoring 2 2016-05-06 08:13
Consecutive p-smooth integers XYYXF Computer Science & Computational Number Theory 0 2014-12-05 17:32
k's with consecutive small primes gd_barnes Riesel Prime Search 1 2007-07-30 23:26
Consecutive integers. mfgoode Puzzles 12 2007-07-24 09:43
On consecutive integers Kees Puzzles 22 2006-07-30 15:33

All times are UTC. The time now is 19:18.

Mon Nov 23 19:18:36 UTC 2020 up 74 days, 16:29, 2 users, load averages: 2.27, 2.50, 2.56

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.