Happy New Prime Year! - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T05:13:36Z http://mathoverflow.net/feeds/question/50624 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50624/happy-new-prime-year Happy New Prime Year! Wadim Zudilin 2010-12-29T04:17:34Z 2011-01-03T08:51:59Z <p>It happens that next year 2011 is prime, while outgoing 2010 is highly composite in the sense that the number of its distinct prime factors is 4, maximal possible for a year $&lt; 2310$.</p> <p>Let me denote by $s(n)$ the number of distinct prime factors of $n$ and note that $s(2011)=1$, $s(2012)=2$ and $s(2013)=3$. I wonder whether there is a rigorous argument or some heuristic considerations to show that, for each $k\ge1$, there exist (infinitely many integers) $n$ satisfying $s(n+1)=1$, $s(n+2)=2$, $\dots$, $s(n+k)=k$.</p> <p>This can be thought as a generalization of the infiniteness of primes ($k=1$), but I ask this question for curiosity only.</p> <p>Happy New Prime Year 2011! (Please do not count the exclamation mark as factorial.)</p> http://mathoverflow.net/questions/50624/happy-new-prime-year/50626#50626 Answer by sleepless in beantown for Happy New Prime Year! sleepless in beantown 2010-12-29T04:31:22Z 2010-12-29T20:18:18Z <p>You missed the excitement of 1998, with $1999=1999, 2000=2^4 \cdot 5^3, 2001=3 \cdot 23 \cdot 29,$ and $2002=2 \cdot 7 \cdot 11 \cdot 13$</p> <p>A quick set of thoughts, too long to fit in a comment:</p> <p>this requires finding a "prime gap" of length $k-1$, since $s(n+1)=1$ means <strike>that $n+1$ is prime</strike> that $n+1$ is either prime or a power of a prime, but the next $k-1$ digits are composite since s(n+x)>1 for $2 \le x \le k$. This also means that $s(n+2)=2$ only because $s(n+2)$ is even, thus $2$ is one of the factors and implies that $(n+2)/2$ is prime (or that $(n+2)/2^j$ is prime for some $j \in \mathbb{Z}$), since $n+2$ only has two factors and one of them is $2$ (or $2^j$). </p> <p>For $s(n+k)$ to have $k$ distinct prime factors means that it has to be at minimum a product of the first $k$ prime numbers, while it definitely has to be a multiple of the product of $k$ prime numbers. So the two key restrictions are that s(n+k) is $k$-composite (has $k$ prime factors) and that both (n+1) and (n+2)/2 are prime numbers.</p> <p>Hmm, I thought something about the fact that either s(n+2) or s(n+4) would be divisible by $4$ while the other would be divisible by $2$ but not by $4$ would play some role in this.</p> <p>Here are some quick results from running "bash", "factor", and "sed" and "awk" at the command line:</p> <p>If you want an ascending run of 1,2, and 3 prime factors, the smallest example starts at $n=63$, with $64=2^6, 65=5 \cdot 13, 66=2 \cdot 3 \cdot 11$</p> <p>If you want an ascending run of 1,2,3, and 4 prime factors, we already missed the exciting years of $n=1866$ and $n=1998$</p> <pre><code>1867: 1867 1868: 2 2 467 1869: 3 7 89 1870: 2 5 11 17 1999: 1999 2000: 2 2 2 2 5 5 5 2001: 3 23 29 2002: 2 7 11 13 </code></pre> <p>And the next few years with ascending runs of 1,2,3, and 4 prime factors will start after the years 3216, 4056, and 4176 with 3217, 4057, and 4177 as prime years. Unfortunately, these computational results are not giving me the germ of any shortcut or understanding. There are also some descending sequences in terms of the number of prime factors, and their placement also does not help.</p> <p>If you want an ascending run of 1,2,3,4, and 5 prime factors, we have to wait almost half-a-million years to get to the exciting years of $n=491850$ and $n=521880$ for $k=5$</p> <pre><code>491851: 491851 491852: 2 2 122963 491853: 3 19 8629 491854: 2 11 79 283 491855: 5 7 13 23 47 521881: 521881 521882: 2 260941 521883: 3 3 3 3 17 379 521884: 2 2 11 29 409 521885: 5 7 13 31 37 </code></pre> <p>Now with four numbers computed and found, I searched the OEIS and found the corresponding sequence. Since the Online Encyclopedia already has this sequence, I'm hanging up my computational hat and heading off to work. :)</p> <blockquote> <p><a href="http://oeis.org/A086560" rel="nofollow">http://oeis.org/A086560</a></p> <p>Start of first run of n successive numbers in which i-th number has exactly i distinct prime divisors for i = 1..n</p> <pre><code>2, 5, 64, 1867, 491851, 17681491, 35565206671 </code></pre> <p>J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 64, p. 23, Ellipses, Paris 2008.</p> </blockquote> http://mathoverflow.net/questions/50624/happy-new-prime-year/50679#50679 Answer by Micah Milinovich for Happy New Prime Year! Micah Milinovich 2010-12-29T21:31:56Z 2010-12-29T21:31:56Z <p>I believe that the question you are asking is still open. It has only (relatively) recently been shown that $s(n)=s(n+1)=A$ has infinitely many solutions for $A\ge 3$. This was shown by Schlage-Puchta in 2003. This article by Goldston, Graham, Pintz, and Yildirim discusses this and related questions:</p> <p><a href="http://arxiv.org/abs/0803.2636" rel="nofollow">http://arxiv.org/abs/0803.2636</a></p> <p>Remark: your arithmetic function $s(\cdot)$ is usually denoted $\omega(\cdot)$ nowadays, but was denoted $\nu(\cdot)$ by Ramanujan.</p> http://mathoverflow.net/questions/50624/happy-new-prime-year/50691#50691 Answer by Gerhard Paseman for Happy New Prime Year! Gerhard Paseman 2010-12-30T00:28:05Z 2010-12-30T16:08:59Z <p>I decided to share this awk code to compute s(n), primarily because I like that it uses only addition and the distributive law, and not factoring, to compute s(n). It also uses a bit of string processing and hash-table look up, but is a nice example of the use of associative arrays. I also like it because it uses $O(\pi(n)\log(n))$ bytes of memory, essentially one entry per prime number less than n. Apologies to sleepless in beantown: I prefer obfuscated awk and nice algorithms to one-liners in Perl, so do not accept his challenge made in a comment on his answer.</p> <p><PRE><br> BEGIN{ LIM = 10000 ; SEP = "," prev = count[1] = count[2] = count[3] = SENTINEL = 0 dir[1] = 1 ; dir[2] = 0 ; dir[3] = -1 str[1] = " / at " ; str[2] = " = at " ; str[3] = " \\ at " notify[1] = notify[3] = 3; notify[2] = 6</p> <p>for( n = 2 ; n &lt; LIM ; n++ ) { # cmp means composite if (n in cmp) { split(cmp[n], fl, SEP) ; delete cmp[n] } else { # n is prime; make up factor list from scratch fl[1] = n ; fl[2] = SENTINEL } for(f = fl[j=1] ; f != SENTINEL ; f = fl[++j] ) { if ((nn = (n+f)) in cmp) cmp[nn] = f SEP cmp[nn] else cmp[nn] = f SEP SENTINEL } s = j - 1 </p> <p>for (k in dir) { count[k] = (prev == (s - dir[k]))?(count[k] + 1): 1 if (count[k] > notify[k]) print count[k] str[k] n ":" s } prev = s } } </PRE></p> <p>Sample output verifies the results of sleepless in beantown, plus shows that there are long runs where s is constant: 2=s(2302)=...=s(2308) . It suggests that there is a function f(s) such that there are at most f(s) consecutive numbers with value s. I suspect f(1)=4, but do not yet have a proof.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2010.12.29</p> http://mathoverflow.net/questions/50624/happy-new-prime-year/50752#50752 Answer by Ricardo Menares for Happy New Prime Year! Ricardo Menares 2010-12-30T19:11:09Z 2010-12-30T19:11:09Z <p>As it was pointed out to me by Han Wu, 2010 wasn't that boring from the prime numbers point of view:</p> <p>2010 = 2*3*5*(7+11+13+17+19)</p> http://mathoverflow.net/questions/50624/happy-new-prime-year/50996#50996 Answer by To be cont'd for Happy New Prime Year! To be cont'd 2011-01-03T08:51:59Z 2011-01-03T08:51:59Z <p>Here is another pattern I learned from <a href="http://www.google.com/profiles/bharath4everyone#buzz" rel="nofollow">Bharath Kumar Annamaneni</a> in his buzz post.</p> <p>2011= 157 + 163 + 167 + 173 + 179 + 181 + 191 + 193 + 197 + 199 + 211 .</p> <p>2011, Being A Prime Number Itself, Is Also A Sum Of 11 Consecutive Prime Numbers . Wow.</p>