 mersenneforum.org Prime Gap Length with consecutive integers divisible by small primes
 Register FAQ Search Today's Posts Mark Forums Read  2016-12-11, 05:34 #1 carpetpool   "Sam" Nov 2016 1010001012 Posts 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.   2016-12-11, 18:13   #2
robert44444uk

Jun 2003
Oxford, UK

195710 Posts Quote:
 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   2016-12-11, 18:55   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 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.   2016-12-11, 20:20 #4 carpetpool   "Sam" Nov 2016 14516 Posts 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   2016-12-11, 21:13   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts Quote:
 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.   2016-12-11, 21:42 #6 carpetpool   "Sam" Nov 2016 52·13 Posts 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.   2016-12-11, 22:22   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 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   2016-12-12, 02:33 #8 carpetpool   "Sam" Nov 2016 52·13 Posts I use perl ntheory module for that: https://metacpan.org/pod/ntheory   2016-12-12, 02:40   #9
CRGreathouse

Aug 2006

597910 Posts Quote:
 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.   2016-12-12, 02:41   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts Quote:
 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.

Last fiddled with by science_man_88 on 2016-12-12 at 02:41   2016-12-12, 04:43 #11 carpetpool   "Sam" Nov 2016 52×13 Posts 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   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post mickfrancis Factoring 2 2016-05-06 08:13 XYYXF Computer Science & Computational Number Theory 0 2014-12-05 17:32 gd_barnes Riesel Prime Search 1 2007-07-30 23:26 mfgoode Puzzles 12 2007-07-24 09:43 Kees Puzzles 22 2006-07-30 15:33

All times are UTC. The time now is 00:35.

Wed Oct 27 00:35:57 UTC 2021 up 95 days, 19:04, 0 users, load averages: 1.44, 1.17, 1.10