Register to reply

Divisibility question; consecutive numbers

Share this thread:
kid1
#1
Jul6-11, 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.
Phys.Org News Partner Science news on Phys.org
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
micromass
#2
Jul6-11, 12:40 PM
Mentor
micromass's Avatar
P: 18,330
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...
dodo
#3
Jul6-11, 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

micromass
#4
Jul6-11, 03:44 PM
Mentor
micromass's Avatar
P: 18,330
Divisibility question; consecutive numbers

Quote Quote by Dodo View Post
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.
dodo
#5
Jul6-11, 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 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.
kid1
#6
Jul6-11, 07:18 PM
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.


Register to reply

Related Discussions
Non-Consecutive 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