4 ms·
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 pyth
by 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 agoHmm, 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 agoYou 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.