Register to reply 
Divisibility question; consecutive numbers 
Share this thread: 
#1
Jul611, 12:59 AM

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.



#2
Jul611, 12:40 PM

Mentor
P: 18,079

Hi kid1!
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... 


#3
Jul611, 03:36 PM

P: 688

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 


#4
Jul611, 03:44 PM

Mentor
P: 18,079

Divisibility question; consecutive numbers



#5
Jul611, 04:15 PM

P: 688

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 kM1 are not divisible by any of the primes, so M1 is an upper bound (by a large excess, probably).
Here's another hint. The problem is analogous to this one: given the vectorvalued 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*...*(p1) 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 zerofree. Distributed, how? Ahhh, that's the question. 


#6
Jul611, 07:18 PM

P: 3

Thank you Dodo, that link was helpful. I am dissapointed that the answer isn't just 2p1; 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.



Register to reply 
Related Discussions  
NonConsecutive Fibonacci Numbers...  General Math  6  
Product of r consecutive numbers divisible by r!  General Math  7  
Consecutive odd natural numbers  one is composite. Prove!  Calculus & Beyond Homework  1  
Help 4 consecutive numbers divisible by 4  Calculus & Beyond Homework  4  
The only 3 consecutive odd numbers that are primes are 3,5,7  Precalculus Mathematics Homework  1 