2 ms·

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

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.
  - tzs 5y ago
    You are right. To fix mine, I'd need to take into account the actual endpoints of the interval instead of just the length of the interval. For each divisor d there would be a separate case to consider for each possible value of 10n mod d. This seems like it would greatly complicate my approach.

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.
- tzs 5y ago
  You are right. To fix mine, I'd need to take into account the actual endpoints of the interval instead of just the length of the interval. For each divisor d there would be a separate case to consider for each possible value of 10n mod d. This seems like it would greatly complicate my approach.