# Question about a certain class of primes

I've come across a set of primes in a problem I'm working on, and I'm wondering if there's more information available about them. I'm guessing not much, particularly since the question of infinitude for the largest subset of these is open. For now, until I see a reference somewhere else, I've been referring to them as primes in harmonic progression, or $H_k$.

$H_2$ are the primes such that $p$ is prime, and $\frac{p+1}{2}$ is also prime. These are $\{3,5,13,37,61,...\}$

$H_3$ are the primes such that $p$ is prime, $\frac{p+1}{2}$ is prime, and $\frac{p+2}{3}$ is prime. These are $\{13,37,157,877\}$

$H_7$ has $p$ prime, and $\frac{p+1}{2}$ ... $\frac{p+6}{7}$ are also prime. The first one of these is at $5516281$.

I haven't been able to find any references to the following kinds of primes except for the case of $k=2$.

• The case $k=2$ is tabulated at oeis.org/A005383. I think the related sequence oeis.org/A005382 of primes $p$ such that $2p-1$ is also prime, is more natural. $H_3$ is tabulated at oeis.org/A036570 (it seems you left out 541). – Gerry Myerson Mar 17 '14 at 23:37
• You're right, I did leave out 541. The sequences you point to are exactly what I'm looking for. – Foo Barrigno Mar 18 '14 at 10:57
• If you type 5516281 into oeis.org, you will find several more sequences of some relevance. – Gerry Myerson Mar 18 '14 at 11:15

Let $q:=k!$. The set of integers $n$ for which each of $\frac{n+1}{2},\dots,\frac{n+k-1}{k}$ is an integer is a union of residue classes modulo $q$. Let $a$ be such a residue class, and consider the $k$-tuple of linear forms $qn+a, \frac{q}{2}n+\frac{a+1}{2},\dots,\frac{q}{k}n+\frac{a+k-1}{k}$, and note that each linear form has integral coefficients by our choice of $q$ and $a$. To see whether this "should" represent infinitely many primes, one should check whether the product of the linear forms has a fixed prime divisor; I haven't done this, but I expect it doesn't, and certainly, there should be an $a$ for which it doesn't. Assuming that there is no fixed prime divisor, this tuple of forms is admissible, and we expect that there should be infinitely many $n$ for which each form is prime. Moreover, there should be a constant times $x/\log^k x$ such $n$ up to $x$. Using the Selberg sieve, one can prove an unconditional upper bound that is $2^k k!$ times as large. This is in Iwaniec and Kowalski, for example.
It's tempting to use the recent results of Zhang, Maynard, and Polymath to say something here, but we have to be careful. For example, we know that once $k$ is at least 51, there will be infinitely many $n$ for which at least two of the forms are prime. But this does not say that there are infinitely many primes $p$ for which one of $\frac{p+1}{2},\dots, \frac{p+k-1}{k}$, because we cannot guarantee that one of the two forms that simultaneously represent primes is the first form.
ADDED: Instead of looking mod $k!$, one can of course also look modulo $\mathrm{lcm}(1,2,\dots,k)=:L$, and restrict to $n$ that are $1 \pmod{L}$. This gives us some information about the size of the smallest element of the set. In particular, if we just look for the first prime $p \equiv 1 \pmod{L}$, this will give us a lower bound for the first prime in $H_k$. By Linnik's theorem, we know that the first such prime is $\leq L^c$ for some $c>0$; we know, due to Xylouris, that $c=5$ works. Of course, this is a coarser question than identifying the smallest element of $H_k$, but, given that I doubt we can prove that $H_k$ is non-empty for large $k$, I doubt we can do any better.
• Very impressive analysis, I have a lot of reading to do there. I'll probably approach the question from a computational perspective in finding the largest example for a given k and the largest k such that I can find such a k. Being able to prove even $H_2$ is finite or infinite is out of my grasp, but it may be realistic that I can prove there are no solutions for a certain k, assuming not all of the sets are infinite. – Foo Barrigno Mar 17 '14 at 21:05
• Rio: $a=1$ guarantees that the product of the linear polynomials (not forms) has no fixed prime divisor, since the product equals $1$ at $n=0$. (Probably that's why the OP chose these specific polynomials.) FB: remember that it's not possible even in theory to computationally establish that any of these systems has no prime solutions; maybe the first solution is just after the computation stopped.... – Greg Martin Mar 17 '14 at 23:42