Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Divisibility question; consecutive numbers

  1. Jul 6, 2011 #1
    Does anyone know the answer to this problem: if you have a set of consecutive prime numbers (2,3,5,7...), what is the greatest amount of consecutive integers that are divisible by at least one of the prime numbers? For 2,3,and 5, I know it is 5 (2 through 6, 24 through 28, 32 through 36...), but for really big primes I can't figure it out.
  2. jcsd
  3. Jul 6, 2011 #2
    Hi kid1! :smile:

    Lets say you have prime {2,3,5,...,p}, then you can set x=2*3*5*...*p. Then


    is a sequence of consecutive integers such that one of the primes divides it. So there certainly are p consecutive integers not divisible by p. It's a good question whether p is the largest number of consecutive integers...
  4. Jul 6, 2011 #3
    The largest is probably longer, given that it's easy to find one example longer than the last prime. For {2,3,5,7}, the numbers 2 to 10 (9 of them) are divisible by some prime of the list (because 7 and 11 are not twin).

    P.S.: I googled this, if it helps someone:
    Last edited: Jul 6, 2011
  5. Jul 6, 2011 #4
    Indeed, I suspect that it is unbounded. That is, the numbers become arbitrarily large. The reason is that there are arbitrary large gaps where no primes occur.
  6. Jul 6, 2011 #5
    The sequence is probably unbounded, for the reason you state. But for a given, fixed prime, there must be a bound. This is because, if your primes are {2,3,5,...,p} and defining M=2*3*5*...*p, then all numbers of the form kM-1 are not divisible by any of the primes, so M-1 is an upper bound (by a large excess, probably).

    Here's another hint. The problem is analogous to this one: given the vector-valued function F(n) = (n mod 2, n mod 3, n mod 5, ..., n mod p), find the longest sequence of consecutive integers such that there is some zero component on all of the corresponding F(n). These vectors repeat in a pattern (modulo M), and there are relatively few vectors which have no zeroes, namely 1*2*4*...*(p-1) of them (which happens to be phi(M)). The large majority of the vectors will have some zero. For an example, for {2,3,5,7}, M=210 but only 48 are zero-free. Distributed, how? Ahhh, that's the question.
  7. Jul 6, 2011 #6
    Thank you Dodo, that link was helpful. I am dissapointed that the answer isn't just 2p-1; that was what my first guess would have been. It's really frustrating that such a simple sounding problem can be so hard! Using the zeroes of those mod functions is a good idea, but it would still be tough to figure out their distrubution, which is the essence of the problem.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook