Happy New Prime Year! - MathOverflow

Happy New Prime Year!

2010-12-29T04:17:34Z

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

Answer by sleepless in beantown for Happy New Prime Year!

2010-12-29T04:31:22Z

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.

Answer by Micah Milinovich for Happy New Prime Year!

2010-12-29T21:31:56Z

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.

Answer by Gerhard Paseman for Happy New Prime Year!

2010-12-30T00:28:05Z

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.

Gerhard "Ask Me About System Design" Paseman, 2010.12.29

Answer by Ricardo Menares for Happy New Prime Year!

2010-12-30T19:11:09Z

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)

Answer by To be cont'd for Happy New Prime Year!

2011-01-03T08:51:59Z

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.