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
New type of solar concentrator desn't block the view
Researchers demonstrate ultra low-field nuclear magnetic resonance using Earth's magnetic field
Asian inventions dominate energy storage systems
micromass
#2
Jul6-11, 12:40 PM
Mentor
micromass's Avatar
P: 18,219
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,219
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