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.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ 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! $\endgroup$– Darrell PlankCommented Jan 20, 2011 at 11:27
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
3
$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 a run of $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.
answered Jan 18, 2011 at 18:22
-
13$\begingroup$ $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. $\endgroup$ Commented Jan 18, 2011 at 18:30
-
1$\begingroup$ 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? $\endgroup$– JBLCommented Jan 18, 2011 at 23:38
-
2$\begingroup$ 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. $\endgroup$ Commented Jan 19, 2011 at 0:43
$\begingroup$
$\endgroup$
4
Tony Forbes' paper (and its references) is a good place to start.
Fifteen Consecutive Integers with Exactly Four Prime Factors
-
1$\begingroup$ It is a good paper. However it counts $40=2^35$ as having 4 prime factors so it is not the same question. $\endgroup$ Commented Jan 19, 2011 at 2:55
-
$\begingroup$ 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. $\endgroup$ Commented Jan 19, 2011 at 6:23
-
$\begingroup$ 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. $\endgroup$ Commented Jan 19, 2011 at 17:04
-
$\begingroup$ Aaron is, strictly speaking, correct, but it's a really interesting paper anyway. Thanks for the link! $\endgroup$ Commented Jan 20, 2011 at 6:50
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ 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. $\endgroup$– kcrismanCommented Jan 18, 2011 at 21:46
-
$\begingroup$ I verified @Aaron Meyerowitz about the run of 9 by brute force up to 125 million as well. Nice work. $\endgroup$– kcrismanCommented Jan 19, 2011 at 13:25
-
$\begingroup$ I think $\omega(n)$ is standard now; $\nu(n)$ was popular at the beginning of the 20th century but not so much at present. $\endgroup$– CharlesCommented Jan 19, 2011 at 19:40
$\begingroup$
$\endgroup$
Check out the related question 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
answered Jan 18, 2011 at 22:59