# Divisibility question; consecutive numbers

by kid1
Tags: consecutive, divisibility, numbers
 P: 3 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.
 PF Patron Sci Advisor Thanks Emeritus P: 15,671 Hi kid1! Lets say you have prime {2,3,5,...,p}, then you can set x=2*3*5*...*p. Then $$x+2,x+3,x+4,...,x+p,x+p+1$$ 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...
 P: 687 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
PF Patron
Thanks
Emeritus
P: 15,671

## Divisibility question; consecutive numbers

 Quote by Dodo 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
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.
 P: 687 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.
 P: 3 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.

 Related Discussions General Math 6 General Math 7 Calculus & Beyond Homework 1 Calculus & Beyond Homework 4 Precalculus Mathematics Homework 1