[librexpr]

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]

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-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.