# Happy New Prime Year!

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 $< 2310$.

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$.

This can be thought as a generalization of the infiniteness of primes ($k=1$), but I ask this question for curiosity only.

Happy New Prime Year 2011! (Please do not count the exclamation mark as factorial.)

-
Is it already the new year in Australia ? –  Chandan Singh Dalawat Dec 29 '10 at 4:22
Not yet but it will come much earlier than to other places. :-) –  Wadim Zudilin Dec 29 '10 at 4:26
Though in a cultural sense, the New Year starts (started) in Israel and India a bit earlier, as their years are phase shifted ahead of the US/EU calendars, and in China the New Year starts a bit later as their year's end is phase shifted after the calendar used to demarcate the passage of time on MO. And numerically they're using different starting points for their "zero" year along with being phase shifted as a difference. Do the Australians hang their calendars upside down? ;>) –  sleepless in beantown Dec 29 '10 at 4:57
But then, that may be why you say "(infinitely many integers)" instead of "infinitely many integers". Gerhard "Reading A Second Time Helps" Paseman, 2010.12.28 –  Gerhard Paseman Dec 29 '10 at 7:38
2011 is not just prime; it is also the sum of a prime number of consecutive primes: 2011=157+163+167+173+179+181+191+193+197+199+211 –  Steven Landsburg Jan 1 '11 at 15:04

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$

A quick set of thoughts, too long to fit in a comment:

this requires finding a "prime gap" of length $k-1$, since $s(n+1)=1$ means that $n+1$ is prime 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$).

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.

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.

Here are some quick results from running "bash", "factor", and "sed" and "awk" at the command line:

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$

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$

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


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.

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$

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


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. :)

http://oeis.org/A086560

Start of first run of n successive numbers in which i-th number has exactly i distinct prime divisors for i = 1..n

2, 5, 64, 1867, 491851, 17681491, 35565206671


J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 64, p. 23, Ellipses, Paris 2008.

-
$n+3$ has to be divisible by $3$ and must have two other prime factors not including $2$. –  sleepless in beantown Dec 29 '10 at 4:39
I meant to say that either "(n+2) or (n+4)" would be divisible by 4 while the other would be divisible by 2 but not by 4; not "s(n+2) or s(n+4)" –  sleepless in beantown Dec 29 '10 at 4:45
and as you say in your question, such a sequence requires that the base number be larger than the product of the first $k$ primes. –  sleepless in beantown Dec 29 '10 at 4:51
n+3 does not have to be a multiple of 3. 383 is prime, and 385=5x7x11. Gerhard "Ask Me About Smooth Numbers" Paseman, 2010.12.28 –  Gerhard Paseman Dec 29 '10 at 7:23
@Gerhard-Paseman, oops, I messed that up. n+1 has to be prime, n+2 has to be divisible by 2, n+3 does not have to be divisible by 3. But either n+2 or n+4 has to be divisble by 3. –  sleepless in beantown Dec 29 '10 at 7:40

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:

http://arxiv.org/abs/0803.2636

Remark: your arithmetic function $s(\cdot)$ is usually denoted $\omega(\cdot)$ nowadays, but was denoted $\nu(\cdot)$ by Ramanujan.

-
Thanks, John, for the link to related problems. With F-Jellyfish's comment above my question is definitely answered. Yes, I know about the $\omega$ (but not $\nu$) notation, although I was not convinced it is standard enough and I did not wish for respondents use 6 symbols for $\omega$ instead of just one for $s$. –  Wadim Zudilin Dec 29 '10 at 22:59
Thanks, Micah, for turning from John into Micah. Your newer name is nicer! –  Wadim Zudilin Sep 12 '11 at 12:03
I read the meta thread about posting with real names (and was convinced to do so). –  Micah Milinovich Sep 12 '11 at 13:24

As it was pointed out to me by Han Wu, 2010 wasn't that boring from the prime numbers point of view:

2010 = 2*3*5*(7+11+13+17+19)

-
Ricardo, I would expect that there is no "primary" boring year at all! :-) –  Wadim Zudilin Dec 30 '10 at 23:37
@Ricardo and @Wadim-Zudilin, yes the numerologists will see a way to make every year interesting, and the paradox of the first un-interesting year becoming interesting because of the fact that it is the first un-interesting year. ;>) Also, see Mayan, Hebrew, Chinese, Indian, and many other cultural artefacts for different origins and phase-shifts for yearly and weekly and monthly calendar objects. It's amazing how human beings have dissected the night sky and the numbers we pluck out of the sky and thin air. –  sleepless in beantown Dec 31 '10 at 1:39

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.


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

for( n = 2 ; n < 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

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
} }


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.

-
Thanks, Gerhard! It's almost the end of 2010.12.30 here... –  Wadim Zudilin Dec 30 '10 at 8:07
Since multiples of 2 are involved, showing that f(1)=4 boils down to case checking. Since there is only one pair of adjacent concsecutive powers of 2, the case checking is not that tedious. So I now think I have a proof that f(1)=4. I would have thought f(2) to be 6 or less, but simulation shows that to be in error. Gerhard "Ask Me About System Design" paseman, 2010.12.30 –  Gerhard Paseman Dec 30 '10 at 16:33

Here is another pattern I learned from Bharath Kumar Annamaneni in his buzz post.

2011= 157 + 163 + 167 + 173 + 179 + 181 + 191 + 193 + 197 + 199 + 211 .

2011, Being A Prime Number Itself, Is Also A Sum Of 11 Consecutive Prime Numbers . Wow.

-
Check Steven Landsburg's comment to the question. GRP 2011.01.03 –  Gerhard Paseman Jan 3 '11 at 9:05
Elohemahab, thanks for the link, it's cute: "[2011 is] the year terminating the smallest quadruplet of successive prime years that leaps over a millennium with increasing gaps $2^n$ ($n=1,2,3$): 1997, 1999, 2003, 2011." Let me add that 2027 ($=2011+2^4$ and prime) ends this quintuplet... –  Wadim Zudilin Jan 3 '11 at 9:48
Another piece about 2011: "The smallest four digit prime assigned as an Australian postcode. It belongs to Kings Cross and Woollomolloo, New South Wales." I am quite close to the place (although there are closer people on MO). I love Aussie names: Wool-lo-mol-loo... oooo –  Wadim Zudilin Jan 3 '11 at 10:12
Happy traveling! –  Unknown Jan 3 '11 at 11:00
Thanks, Elohemahab! To be honest, I am not traveling but living in this paradise. :-) –  Wadim Zudilin Jan 3 '11 at 12:37