# Is there an 11-term arithmetic progression of primes beginning with 11?

i.e. does there exist an integer $C > 0$ such that $11, 11 + C, ..., 11 + 10C$ are all prime?

• @kodlu : You can write $2\times10^7$ or $2\cdot10^7.$ The use of an asterisk for that purpose is a workaround for occasions where one is limited to the characters on the keyboard. – Michael Hardy Aug 10 '18 at 17:51
• Magma says $C>2\times 10^7$ and crashes somewhere before $C<2\times 10^8$. – kodlu Aug 11 '18 at 2:56

Such an integer $C$ exists. The smallest $C$ with this property is $C=1536160080$.

I found this $C$ by computing the analogous number $C$ for a $3$-term prime arithmetic progression beginning with $3$, a $5$-term prime arithmetic progression beginning with $5$ and a $7$-term prime arithmetic progression beginning with $7$. This gave me the numbers $2,6,150$. When I plugged these into OEIS I found that the next term in this sequence is $1536160080$. You can see the relevant OEIS page here.

• There are some other possibilities for $C$: oeis.org/A206045 – José Hdz. Stgo. Aug 10 '18 at 1:34
• That's a nice strategy for finding an answer. – Kim Aug 10 '18 at 1:35
• @Kim: provided it's known already... – Yaakov Baruch Aug 10 '18 at 11:51
• $1536160080$ appears eight times in OEIS so there may be more than one approach – Henry Aug 11 '18 at 9:14
• D'oh! I made a mistake, otherwise I would have found it yesterday. – Gerald Edgar Aug 11 '18 at 13:34

Siemion Fajtlowicz has been promoting the topic of $p$-long arithmetic progressions of primes which start with $p$ during 1993-4 (or longer). He and his colleague Micha Hofri got an $11$-long progression. Then, soon after, I got a small theorem which allowed me to get bunches of such $11$-progressions very fast, and also a lot of $13$-progressions (of $13$ primes starting with $13$) almost as quickly.

On the other hand, I conjectured that only a finite number of primes $p$ start $p$-progressions. Moreover, I believe that no prime $p>13$ starts any. Perhaps there is already none for $\ p=17$. (I got my results during 1994).

• According to the OEIS page referenced there are such for $p=13,$ $p=17$ and $p=19.$ The minimal $d$ for $p=7,11,13,17,19$ are roughly $7^{2.5},11^8,13^{11.6},17^{16.6}$ and $19^{19.03}$ That slightly blows my rather slapdash estimation that $d=p^p$ should be about right. I'd think a more careful calculation would give credible bounds (which might be impossible to confirm in our lifetimes for primes past $30$ or so.) – Aaron Meyerowitz Aug 10 '18 at 7:20
• What was your theorem? – Charles Aug 11 '18 at 1:55
• Don't standard conjectures (Dickson) imply there should be (infinitely many) $p$-progressions for every $p$? – Wojowu Aug 11 '18 at 8:27
• @Wojowu Could you elaborate on the precise statement of this conjecture? – Kim Aug 11 '18 at 9:56
• – Wojowu Aug 11 '18 at 12:50

For the sake of easy education let me mention the first simplest step toward finding $p$-long arithmetic progressions of primes which start with $p$.

Let $q$ be an arbitrary prime. Then the arithmetic progressions of more than $q$ integers must have a term divisible by $q$ when the difference of the progression is not divisible by $q$.

Now, let $\ p_0<p_1<\ldots\$ be the sequence of all primes. Let there be a $p_n$-progression as described in this thread (in the first sentence of this answer/post). Then the difference of the progression must be divisible by the product of the previous primes, i.e. by

$$\prod_{k<n}p_k.$$

Now, it is enough to check consecutive multiples of this product as the possible differences of the required progression.

Today, this remark would suffice toward a fast computation of the 11-progressions but around y.1992 it would make a computing station sweat for long hours (or days). But even in those days, the next step (a small theorem) was already good enough for computing even 13-progressions (but not 17-progressions).

There seems to be an interest in $p$-app ($p$-long prime arithmetic progressions) which start with prime $p$. Thus, I've decided to put some $\LaTeX$ sweat into more information, as elementary as it is.

A $p$-app is an arithmetic progression $\ (p+t\!\cdot\! d\ :\ t=0\ldots n\!-\!1)\$ such that all its terms are primes, and integer $\ d>1.\$ Then a simple theorem assures us that

$$\prod \mathbf P(p-1)\ |\ d$$

Where $\ \mathbf P(x)\$ is the set of all primes $\ \le\ x.$

Given any prime $p$ we would like to find all we can about the $p$-app's (do they exist, etc.).

Let $\ D:=\prod\mathbf P(n_1)\$ as above. In particular, we would like to know everything about $\ r\$ such $\ d=r\cdot D,\$ where $\ d\$ is the difference of arbitrary $p$-app.

Thus, let $\ q\$ be any prime not in the said $p$-app. Then

$$d\not\equiv 0\mod q\quad \Longrightarrow\quad \forall_{0\le k< p}\quad p+k\cdot d\ \not\equiv 0 \mod q$$

Notations:   Let $\ \ /_n\ \$ be the $\mod n\$ division by non-$0$ integers which are not factors of $\ n,\$ with the division value in $\ \{0\ldots\ n\!-\!1.$

Thus,

$$d\not\equiv 0\mod q\quad \Longrightarrow\quad \forall_{0\le k< p}\quad k\ \ne (-p)\,\ /_q\,\ d$$

In other words, looking at the division remaining options (and under the established notation),

THEOREM 1 $$d\not\equiv 0\mod q\quad \Longrightarrow\quad p\ \ \le\ \ (-p)\,\ /_q\,\ d\ \ <\ \ q$$

This significantly reduces the number of options for $\ d\$ when it is (easily!) applied to all primes $\ q>p\$ at the same time (in the same computer program).

APPLICATIONS

• Let prime $\ p>3\$ be a younger sibling of prime $q:=p+2.\$ Then

$$(-p)\,\ /_q\,\ d\,\ =\,\ -\!1\,\ \mbox{or}\ -\!2$$

$\qquad$ (Thus, even one prime $\ q\$ contributes to the computational savings).

• Let $\ p:=11\$. The (see above) $\ D=2\cdot 3\cdot 5\cdot 7=210,\$ and let $\ d := r\cdot D\$ be the respective difference of an arbitrary $11$-app. Then, by the above THEOREM 1, when $\ d\not\equiv 0 \mod 13\$ (i.e. $\ d\not\equiv 0 \mod 13)\$ then

$$2\,\ /_{13}\ d\ \equiv\ -\!1\,\ \mbox{or}\ -\!2\quad \mod 13$$ or $$d\ \equiv\ -\!1\,\ \mbox{or}\ -\!2\quad \mod 13$$

Since $\,\ d = r\cdot D = r\cdot 210 \equiv 2\cdot r\,\ \mod 13,\$ and allowing for the divisibility $13\,|\,r,\$ we finally obtain,

$$r\,\ \equiv\,\ 0\ \mbox{or}\ 6\ \mbox{or}\ 12 \mod 13$$

This reduces the amount of computation $\frac 3{13}\$ time.

Then, taking into account another prime, $\ q:=17,\$ we reduce the computation time again $\ \frac 7{17}\$ times, or for a total saving

$$\frac 3{13}\cdot\frac 7{17}\ =\ \frac {21}{221}$$

times (more then ten times faster), etc.