7

2

Let $P(m,n)$ mean that there is a number, $M$, such that starting with $M$ there are $m$ consecutive numbers each having exactly $n$ distinct prime factors. Is it obvious that $P(m,n)$ is true for all $m$ and $n$? My gut says "obviously" and $P(4,4)$ and $P(5,5)$ are definitely true (for 134043 and 129963314 respectively). It seems like some sort of pigeonhole proof based on the number of factors available might work, but upon reflection, I'm not so sure. Maybe I'm missing something obvious.

flag
Could someone please add a number theory tag to this? Thanks. – Matthew Conroy Jan 18 2011 at 20:40
I gave the answer to Aaron though it's hard to pick. I'm not sure what order the answers come out here - they're all just marked "yesterday". I thought the primorial was a good general point. Anyway, thanks to all for some thought provoking insights! – Darrell Plank Jan 20 2011 at 11:27

4 Answers

8

P(4,1) is true because of 2,3,4,5 but I strongly doubt that P(5,1) is true. Indeed P(4,1) is only true that once and even P(3,1) happens for the last time at 7,8,9. Of any 210 consecutive integers one is divisible by 2,3,5,7 so P(210,3) fails. I'm sure that can be improved. It does generalize .

As noted in the comments, there are two cases (at least) of 8 consecutive integers each with two distinct prime factors and 12 can be ruled out. Actually it seems extremely unlikely that there are any cases of 9, let alone 10 or 11: Such a run of 9 would have to include 7 integers $3(a-1),2(b-1),*,2^i3^j,*,2(b+1),3(a+1)$ where $a\pm1=2^{i}3^{j-1}\pm1$ and $b\pm1=2^{i-1}3^{j}\pm1$ are two pairs of twin primes (or merely twin prime powers). I would expect only finitely many cases where $2^u3^v\pm1$ are both prime powers (I find 35 such up to $10^{50}$ with $u,v \ge 1$, let alone getting two such pairs as above ( I find 4 cases, 36,144,216 and $2^{33}3^9$.) This leaves out the requirements that we would also need $2^{i}3^{j}\pm1$ to each have two distinct prime factors (ruling out the smallest and largest) and have at least one of $2^{i}3^{j}\pm4$ to be 4 times a prime power, and more.

link|flag
12 
 $P(5,1)$ is indeed false. Of five consecutive numbers, at least two are even, so you have two powers of 2 which are a distance of at most 4 apart. This leaves only a few small possible cases which are easily checked. – Chris Eagle Jan 18 2011 at 18:30
1 
 Okay, and we can use the same idea to show that $P(24 , 2)$ is false: among any 24 consecutive integers, there exist twelve which are even, and six of these are divisible by 2 but not by 4. Take the odd parts of these numbers; we get six consecutive odd numbers, each a prime power. Two of these must be divisible by 3, so they must be 3 and 9; we see that the unique possibility is 3, 5, 7, 9, 11, 13. But it's easy to see that this doesn't yield a valid set of 24 numbers. Can this be pushed further? – JBL Jan 18 2011 at 23:38
2 
 If I understand Gerhard Paseman's answer correctly, $P(m,2)$ is false for $m\gt11$. Any 12 consecutive integers contain numbers $6a$ and $6(a+1)$. There are only finitely many cases where $a$ and $a+1$ are both of the form $2^b3^c$ and you can just check them. – Gerry Myerson Jan 19 2011 at 0:43
1 
 You mean a + 1 +- 1 and b + 1 +- 1 being near powers. You might also see how using 5 or 7 as a factor constrains things. Gerhard "Ask Me About System Design" Paseman, 2011.01.19 – Gerhard Paseman Jan 19 2011 at 8:32
Right Gerhard. Thanks, I fixed it. – Aaron Meyerowitz Jan 19 2011 at 9:22
3

Check out the related question http://mathoverflow.net/questions/50624/happy-new-prime-year . I have some code posted there which tracks constant sequences as well as increasing and decreasing sequences. (Check out 2302 to 2308.)

A comment made by someone else and then deleted contained the observation that multiples m of the nth primorial had s(m) >= n, so that runs of values less than n must have length less than the nth primorial. Also, if you look at multiples of 6, you get that s(m)=2 for at most 11 consecutive values instead of at most 29, so there is room for improvement in the upper bound to such lengths.

Gerhard "Reduce, Reuse, Recycle for Rep" Paseman, 2011.01.18

link|flag
8

Tony Forbes' paper (and its references) is a good place to start.

Fifteen Consecutive Integers with Exactly Four Prime Factors

link|flag
I've fixed your link. – Andres Caicedo Jan 18 2011 at 20:27
Thanks, Andres. – Matthew Conroy Jan 18 2011 at 20:39
1 
 It is a good paper. However it counts $40=2^35$ as having 4 prime factors so it is not the same question. – Aaron Meyerowitz Jan 19 2011 at 2:55
The OP didn't indicate that they'd viewed any literature, so I figured this paper, with its references, would help them see some of the results in the field, i.e. it would be a place to start. Please go ahead and give a more relevant reference if you've got one. – Matthew Conroy Jan 19 2011 at 6:23
I agree that it is a great reference, relevant to this question, and maybe a better question. I enjoyed seeing the paper. Just wanted to mention the differences. – Aaron Meyerowitz Jan 19 2011 at 17:04
show 1 more comment
2

It would be interesting to know what generalization might be true about the starting numbers of such sequence, or at least the smallest such.

For instance, $P(7,2)$ and $P(8,2)$ are both true at 141 (and 212), so the smallest such number for only 7 is 323. The next smallest is 2302 (also for 7 only), and there are no others under a million.

Sorry for putting this in an 'answer'; it seems odd to me that one needs additional rep to put in a comment. Though I think that bounds on such numbers would be quite interesting.

link|flag
Not being able to comment on other answers is really annoying... Anyway, the Forbes paper is about $\Omega(n)$, but here the question is about $\nu(n)$, the number of distinct prime divisors (see, for instance, Shapiro's NT text for this notation). So it's relevant, but not about the same question. From that paper: "The smallest example with m = 2 is {33,34,35}" - but of course that is not the maximum length with the OPs question, since the naive upper bound of $2^m-1$ (in the paper's notation) is no longer relevant. – kcrisman Jan 18 2011 at 21:46
I verified @Aaron Meyerowitz about the run of 9 by brute force up to 125 million as well. Nice work. – kcrisman Jan 19 2011 at 13:25
I think $\omega(n)$ is standard now; $\nu(n)$ was popular at the beginning of the 20th century but not so much at present. – Charles Jan 19 2011 at 19:40

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.