Divisibility question; consecutive numbers

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

    micromass 19,188
    Staff Emeritus
    Science Advisor
    Education Advisor

    Hi kid1! :smile:

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

    [tex]x+2,x+3,x+4,...,x+p,x+p+1[/tex]

    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. 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:
    http://oeis.org/A058989
     
    Last edited: Jul 6, 2011
  5. micromass

    micromass 19,188
    Staff Emeritus
    Science Advisor
    Education Advisor

    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. 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. 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.
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?