Skip to main content
2 of 2
added 314 characters in body
Roland Bacher
  • 17.9k
  • 3
  • 45
  • 113

There seem to be only few primes of the form ${n\choose k}+1$ if $k\geq 3$ is odd

We consider the sequence $n\longmapsto {n\choose k}+1$ for $k\geq 1$ a fixed integer. For $k\geq 3$ odd, this sequence seems to contain surprisingly few prime numbers while there are many primes (perhaps roughly the expected amount) among the first terms of this sequence for even $k\geq 2$.

Is there an explanation for this observation (or is it an artefact)?

The following table gives the number of values $n\leq 10^5$ such ${n\choose k}+1$ is prime for $k=1,..,15$: $$\begin{array}{cc} k&\sharp(\mathcal P\cap \{{n\choose k}+1\ \vert\ n=k,\dots,10^5\})\\ 1&9592\\2&9863\\3&3\\4&6765\\5&5\\6&6203\\ 7&7\\8&3092\\9&8\\10&4364\\11&21\\12&2817\\13&19\\ 14&2968\\15&16 \end{array}$$ (with $\mathcal P=\{2,3,5,7,11,\ldots\}$ denoting the set of primes).

The small subsets $\mathcal S_k=\{n_1,\ldots,n_{i_k}\}_k$ of $\{1,\ldots,10^5\}$ corresponding to prime-numbers ${n\choose k}+1$ for $n\in \mathcal S_k$ and $k\geq 3$ odd are given by $$\{3,4,5\}_3,\ \{5,6,9,11,14\}_5,\ \{7,9,11,14,20,29,104\}_7,$$ $$\{9,10,14,35,39,71,119,839\}_9,$$ $$\{11,12,13,17,19,29,32,34,44,65,69,76,83,109,153,197,279,791,1385,6929,13859\}_{11}$$ $$\{13,17,20,27,34,44,51,55,69,87,104,119,142,209,251,263,359,857,923\}_{13},$$ $$\{15,16,17,19,38,83,89,90,131,714,1091,1286,2001,2309,4003,6551\}_{15}.$$

For $k=3$, I checked that there are no additional primes (of the form ${n\choose 3}+1$) for $n$ up to $10^6$.

Added after accepting the answer of user334725: The analogous phenomenon exists for ${n\choose k}-1$ and $k$ even. (This question is by the way an illustration of the fact that experimental maths cannot be done simultaneously with clear thinking: Playing with the computer shuts generally my brain down!)

Roland Bacher
  • 17.9k
  • 3
  • 45
  • 113