3 ms·

Assume n>1 . How can I prove one can only find 23 primes or less in the interval from 10n to 100+10n?

by ffhhj 5y ago

librexpr 5y ago
I'm just an amateur, but if you don't mind some brute-forcing, it's enough to prove that for every n between 1 and (2*3*5*7*11*13)/10+1=3004, exclusive of 1 but inclusive of 3004, there are at most 23 numbers between 10n and 100+10n which are not divisible by any of P={2, 3, 5, 7, 11, or 13}. Let's call numbers which are not divisible by P "potential primes". Every prime greater than 13 is a potential prime but not vice-versa. This obviously works for the n we check manually because if there are at most 23 potential primes, there are at most 23 primes. This also works for n greater than those we check manually, because potential primes in this set "loop" when you get past 30030. Because 30030 is divisible by every prime in P, for any x which is divisible by P, 30030 + x will also be divisible by P. Similarly, if x is a potential prime, 30030 + x will also be a potential prime. This means that there are all the same potential primes from 0 to 30030 as there are from 30030 to 30030*2, and from 30030*2 to 30030*3, and so on. Since by brute force, there was always at most 23 potential primes in the first loop (plus the beginning of the second loop, to make up for the fact that we start at n=2), then it must be true in every later loop. Here is code that does the brute force in ruby 3, finishing the proof: require 'prime' def get_cycle_extended(n) # Get every "potential prime" primes = Prime.each(n).to_a cycle = [] for i in 0...(primes.reduce(:*) + 200) # + 200 to be safe is_eliminated = false for prime in primes if i % prime == 0 is_eliminated = true break end end cycle << i if not is_eliminated end cycle end p get_cycle_extended(5) # just checking that get_cycle makes sense size = 13 cycle = get_cycle_extended(size) for n in 2..3004 s = 10*n e = 100 + s restricted = cycle.filter { |x| (s..e).include?(x) } if restricted.length > 23 raise "false at #{n}" else p restricted end end Edit: Since I posted about copyright not long before posting this, I'll just go and say explicitly that I'm releasing this comment to the public domain using CC0.
- librexpr 5y ago
  I've been nerdsniped haha. Just found this quora question which is the same as what you asked: <https://www.quora.com/Assume-n-1-How-can-I-prove-one-can-only-find-23-primes-or-less-in-the-interval-from-10n-to-100-10n https://www.quora.com/Assume-n-1-How-can-I-prove-one-can-onl...> But the answers seem wrong? The first one uses only the primes 2 to 7 instead of 2 to 13, but there's a reason I used 2 to 13, and it's that there's a counterexample if you use less than that. Even using 2 to 11, which is more than they use, a counterexample exists between 520 and 620, where there are 25 numbers which are not divisible by any of 2, 3, 5, 7, or 11: [521, 523, 527, 529, 533, 541, 547, 551, 557, 559, 563, 569, 571, 577, 583, 587, 589, 593, 599, 601, 607, 611, 613, 617, 619] For the proof by induction at the bottom of the page, I'll admit I just don't understand it, but at first glance it seems impossible to me that it would work given how short it is and it doing things that just don't seem to make sense. But maybe I'm missing something. Regardless, having triple-checked it, I will take pride that my proof is probably correct :P Edit: Now by double-checking this particular comment I've found that there are actually only 24 numbers between 520 and 620 which are not divisible by any prime from 2 to 11. 25 is if you use 2 to 7. This has no effect on the proof though, only this comment about the quora proofs, and even then my point stands.
gizmo686 5y ago
I think this can be done in a straight-forward brute force manner. Consider the first 7 primes [2,3,5,7,11,13,17]. Each of these primes defines a "sieves", that can be used to filter out multiples of it. For instance, 2 defines the sieve [0,2,4,6,...] while 17 defines the sieve [0,17,34,...]. Instead of infinite sieves, consider only the finite sieves that go up to 100. for instance, 17 would give the sieve [0,17,34,...,85]. Over any interval of 100 integers, all multiples of p can be filtered out by filtering out the contents of p's finite sieve with some constant offset (<p). For instance, on the interval [0,100), we can filter out all multiples of 3 by filtering out the sieve [0,3,6,...,99]. Similarly, on the interval [10,110), we can filter out the multiples of 3 using the sieve [2,5,8,...98]. The notation here is a bit backward, but makes sense if you think of the sieve as a bit-field with 100 elements labeled 0 to 99. The sieve [2,5,8,...98] then represents the bitfield where every third element is true, starting with the second element. As a notional shorthand, we can represent this sieve as [3]+2, to represent all multiples of 3, with an offset of 2 (within the range [0,100). Formally speaking: [p]+k = [p * n + k | for integers n,k where 0 <= p * n + k < 100] For sieves X,Y define X | Y to be the union of X and Y. Under the bitfield interpenetration, a bit in X | Y is set if it is set in either X or Y. For every range of 100 integers, there exists a sieve that filters out all multiples of both p and q. This sieve takes the form: [p] + k | [q] + m. We can further restrict 0<=k<p and 0<=m<q. Note that there are only finitely many such sieves. Over any sequence of 100 integers, one of those finitely many sieves will filter out all multiples of p and q. This approach can be extend to any number of primes. Construct all such sieves for the primes [2,3,5,7,11,13,17]. For each sieve, count how many elements it allows through, and find the sieve which allows the fewest elements through. This is an upper bound of the number of integers within a range of 100 that are not a multiple of the first 7 primes. Assuming your range of integers starts at at least 18, this is an upper bound on the number of primes it can have. In python: primes=[2,3,5,7,11,13,17] sieves=[set()] for p in primes: newSieves=[] for k in range(0,p): toAppend = set([ k + pp for pp in range(0,100,p) if k + pp <= 100]) for sieve in sieves: newSieves.append(sieve | toAppend) sieves = newSieves print "\n{}:".format(p) print 100-min([len(s) for s in sieves])
raverbashing 5y ago
Since your interval begins at a divisible by 10 boundary, this makes things easier If you think only about the numbers divisible by 2, 3, 5 you'll get a result pretty close to 23 (21 actually). But you can elaborate the proof to get to a closer number (just remember that after you take 100/2 and 100/3 you need to add back 100/6 which are the ones you counted twice and so on)
- tzs 5y ago
  I get that using 2, 3, 5, 7 is sufficient to prove at most 23 primes in an interval of length 101, by straightforward but inelegant code: #!/usr/bin/env python3 count = 101 span = 101 lp = [2, 3, 5, 7] for p1 in lp: count -= span//p1 for p2 in lp: if p2 <= p1: continue count += span//(p1*p2) for p3 in lp: if p3 <= p2: continue count -= span//(p1*p2*p3) for p4 in lp: if p4 <= p3: continue count -= span//(p1*p2*p3*p4) print("At most {} primes in a span of {}".format(count,span)) A version of that which includes printouts of the number removed or added at each stage gives this output: Remove 14 divisible by 7 Remove 20 divisible by 5 Remove 33 divisible by 3 Remove 50 divisible by 2 Unremove 10 divisible by 2 * 5 Unremove 16 divisible by 2 * 3 Unremove 2 divisible by 5 * 7 Unremove 4 divisible by 3 * 7 Unremove 6 divisible by 3 * 5 Unremove 7 divisible by 2 * 7 Remove 0 divisible by 3 * 5 * 7 Remove 1 divisible by 2 * 5 * 7 Remove 2 divisible by 2 * 3 * 7 Remove 3 divisible by 2 * 3 * 5 Unremove 0 divisible by 2 * 3 * 5 * 7 At most 23 primes in a span of 101
  - librexpr 5y ago
    Hmm, good try, but it's not quite right. Here's a simpler way to get all the numbers divisible by 2, 3, 5, or 7, in a 100-number range, and which I think is easier to verify that it's correct: numbers_not_divisible_by_2_3_5_7 = [] for i in range(520, 620): is_divisible = False for p in [2, 3, 5, 7]: if i % p == 0: is_divisible = True break if not is_divisible: numbers_not_divisible_by_2_3_5_7.append(i) print(numbers_not_divisible_by_2_3_5_7) print(len(numbers_not_divisible_by_2_3_5_7)) And if you run this code you'll find that it demonstrates a counterexample. Between 520 and 620 there are 25 numbers which are not divisible by 2, 3, 5, or 7: [521, 523, 527, 529, 533, 541, 547, 551, 557, 559, 563, 569, 571, 577, 583, 587, 589, 593, 599, 601, 607, 611, 613, 617, 619] You really need to use all the primes from 2 to 13 inclusive to get a limit of 23. And even then I was only able to prove it by brute-forcing up to the primorial of 13, but maybe there's a simpler way.

Assume n>1 . How can I prove one can only find 23 primes or less in the interval from 10n to 100+10n?

by ffhhj 5y ago

Assume n>1 . How can I prove one can only find 23 primes or less in the interval from 10n to 100+10n?

I'm just an amateur, but if you don't mind some brute-forcing, it's enough to prove that for every n between 1 and (2*3*5*7*11*13)/10+1=3004, exclusive of 1 but inclusive of 3004, there are at most 23 numbers between 10n and 100+10n which are not divisible by any of P={2, 3, 5, 7, 11, or 13}. Let's call numbers which are not divisible by P "potential primes". Every prime greater than 13 is a potential prime but not vice-versa. This obviously works for the n we check manually because if there are at most 23 potential primes, there are at most 23 primes. This also works for n greater than those we check manually, because potential primes in this set "loop" when you get past 30030. Because 30030 is divisible by every prime in P, for any x which is divisible by P, 30030 + x will also be divisible by P. Similarly, if x is a potential prime, 30030 + x will also be a potential prime. This means that there are all the same potential primes from 0 to 30030 as there are from 30030 to 30030*2, and from 30030*2 to 30030*3, and so on. Since by brute force, there was always at most 23 potential primes in the first loop (plus the beginning of the second loop, to make up for the fact that we start at n=2), then it must be true in every later loop. Here is code that does the brute force in ruby 3, finishing the proof: require 'prime' def get_cycle_extended(n) # Get every "potential prime" primes = Prime.each(n).to_a cycle = [] for i in 0...(primes.reduce(:*) + 200) # + 200 to be safe is_eliminated = false for prime in primes if i % prime == 0 is_eliminated = true break end end cycle << i if not is_eliminated end cycle end p get_cycle_extended(5) # just checking that get_cycle makes sense size = 13 cycle = get_cycle_extended(size) for n in 2..3004 s = 10*n e = 100 + s restricted = cycle.filter { |x| (s..e).include?(x) } if restricted.length > 23 raise "false at #{n}" else p restricted end end Edit: Since I posted about copyright not long before posting this, I'll just go and say explicitly that I'm releasing this comment to the public domain using CC0.

librexpr 5y ago
I've been nerdsniped haha. Just found this quora question which is the same as what you asked: <https://www.quora.com/Assume-n-1-How-can-I-prove-one-can-only-find-23-primes-or-less-in-the-interval-from-10n-to-100-10n https://www.quora.com/Assume-n-1-How-can-I-prove-one-can-onl...> But the answers seem wrong? The first one uses only the primes 2 to 7 instead of 2 to 13, but there's a reason I used 2 to 13, and it's that there's a counterexample if you use less than that. Even using 2 to 11, which is more than they use, a counterexample exists between 520 and 620, where there are 25 numbers which are not divisible by any of 2, 3, 5, 7, or 11: [521, 523, 527, 529, 533, 541, 547, 551, 557, 559, 563, 569, 571, 577, 583, 587, 589, 593, 599, 601, 607, 611, 613, 617, 619] For the proof by induction at the bottom of the page, I'll admit I just don't understand it, but at first glance it seems impossible to me that it would work given how short it is and it doing things that just don't seem to make sense. But maybe I'm missing something. Regardless, having triple-checked it, I will take pride that my proof is probably correct :P Edit: Now by double-checking this particular comment I've found that there are actually only 24 numbers between 520 and 620 which are not divisible by any prime from 2 to 11. 25 is if you use 2 to 7. This has no effect on the proof though, only this comment about the quora proofs, and even then my point stands.

gizmo686 5y ago

I think this can be done in a straight-forward brute force manner. Consider the first 7 primes [2,3,5,7,11,13,17]. Each of these primes defines a "sieves", that can be used to filter out multiples of it. For instance, 2 defines the sieve [0,2,4,6,...] while 17 defines the sieve [0,17,34,...]. Instead of infinite sieves, consider only the finite sieves that go up to 100. for instance, 17 would give the sieve [0,17,34,...,85]. Over any interval of 100 integers, all multiples of p can be filtered out by filtering out the contents of p's finite sieve with some constant offset (<p). For instance, on the interval [0,100), we can filter out all multiples of 3 by filtering out the sieve [0,3,6,...,99]. Similarly, on the interval [10,110), we can filter out the multiples of 3 using the sieve [2,5,8,...98]. The notation here is a bit backward, but makes sense if you think of the sieve as a bit-field with 100 elements labeled 0 to 99. The sieve [2,5,8,...98] then represents the bitfield where every third element is true, starting with the second element. As a notional shorthand, we can represent this sieve as [3]+2, to represent all multiples of 3, with an offset of 2 (within the range [0,100). Formally speaking: [p]+k = [p * n + k | for integers n,k where 0 <= p * n + k < 100] For sieves X,Y define X | Y to be the union of X and Y. Under the bitfield interpenetration, a bit in X | Y is set if it is set in either X or Y. For every range of 100 integers, there exists a sieve that filters out all multiples of both p and q. This sieve takes the form: [p] + k | [q] + m. We can further restrict 0<=k<p and 0<=m<q. Note that there are only finitely many such sieves. Over any sequence of 100 integers, one of those finitely many sieves will filter out all multiples of p and q. This approach can be extend to any number of primes. Construct all such sieves for the primes [2,3,5,7,11,13,17]. For each sieve, count how many elements it allows through, and find the sieve which allows the fewest elements through. This is an upper bound of the number of integers within a range of 100 that are not a multiple of the first 7 primes. Assuming your range of integers starts at at least 18, this is an upper bound on the number of primes it can have. In python: primes=[2,3,5,7,11,13,17] sieves=[set()] for p in primes: newSieves=[] for k in range(0,p): toAppend = set([ k + pp for pp in range(0,100,p) if k + pp <= 100]) for sieve in sieves: newSieves.append(sieve | toAppend) sieves = newSieves print "\n{}:".format(p) print 100-min([len(s) for s in sieves])

raverbashing 5y ago

Since your interval begins at a divisible by 10 boundary, this makes things easier If you think only about the numbers divisible by 2, 3, 5 you'll get a result pretty close to 23 (21 actually). But you can elaborate the proof to get to a closer number (just remember that after you take 100/2 and 100/3 you need to add back 100/6 which are the ones you counted twice and so on)

tzs 5y ago
I get that using 2, 3, 5, 7 is sufficient to prove at most 23 primes in an interval of length 101, by straightforward but inelegant code: #!/usr/bin/env python3 count = 101 span = 101 lp = [2, 3, 5, 7] for p1 in lp: count -= span//p1 for p2 in lp: if p2 <= p1: continue count += span//(p1*p2) for p3 in lp: if p3 <= p2: continue count -= span//(p1*p2*p3) for p4 in lp: if p4 <= p3: continue count -= span//(p1*p2*p3*p4) print("At most {} primes in a span of {}".format(count,span)) A version of that which includes printouts of the number removed or added at each stage gives this output: Remove 14 divisible by 7 Remove 20 divisible by 5 Remove 33 divisible by 3 Remove 50 divisible by 2 Unremove 10 divisible by 2 * 5 Unremove 16 divisible by 2 * 3 Unremove 2 divisible by 5 * 7 Unremove 4 divisible by 3 * 7 Unremove 6 divisible by 3 * 5 Unremove 7 divisible by 2 * 7 Remove 0 divisible by 3 * 5 * 7 Remove 1 divisible by 2 * 5 * 7 Remove 2 divisible by 2 * 3 * 7 Remove 3 divisible by 2 * 3 * 5 Unremove 0 divisible by 2 * 3 * 5 * 7 At most 23 primes in a span of 101
- librexpr 5y ago
  Hmm, good try, but it's not quite right. Here's a simpler way to get all the numbers divisible by 2, 3, 5, or 7, in a 100-number range, and which I think is easier to verify that it's correct: numbers_not_divisible_by_2_3_5_7 = [] for i in range(520, 620): is_divisible = False for p in [2, 3, 5, 7]: if i % p == 0: is_divisible = True break if not is_divisible: numbers_not_divisible_by_2_3_5_7.append(i) print(numbers_not_divisible_by_2_3_5_7) print(len(numbers_not_divisible_by_2_3_5_7)) And if you run this code you'll find that it demonstrates a counterexample. Between 520 and 620 there are 25 numbers which are not divisible by 2, 3, 5, or 7: [521, 523, 527, 529, 533, 541, 547, 551, 557, 559, 563, 569, 571, 577, 583, 587, 589, 593, 599, 601, 607, 611, 613, 617, 619] You really need to use all the primes from 2 to 13 inclusive to get a limit of 23. And even then I was only able to prove it by brute-forcing up to the primorial of 13, but maybe there's a simpler way.