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

  • 1
    $\begingroup$ @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. $\endgroup$ – Michael Hardy Aug 10 '18 at 17:51
  • $\begingroup$ Magma says $C>2\times 10^7$ and crashes somewhere before $C<2\times 10^8$. $\endgroup$ – 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.

| cite | improve this answer | |
  • 9
    $\begingroup$ There are some other possibilities for $C$: oeis.org/A206045 $\endgroup$ – José Hdz. Stgo. Aug 10 '18 at 1:34
  • 30
    $\begingroup$ That's a nice strategy for finding an answer. $\endgroup$ – Kim Aug 10 '18 at 1:35
  • 3
    $\begingroup$ @Kim: provided it's known already... $\endgroup$ – Yaakov Baruch Aug 10 '18 at 11:51
  • $\begingroup$ $1536160080$ appears eight times in OEIS so there may be more than one approach $\endgroup$ – Henry Aug 11 '18 at 9:14
  • $\begingroup$ D'oh! I made a mistake, otherwise I would have found it yesterday. $\endgroup$ – 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).

See also: http://primerecords.dk/aprecords.htm

| cite | improve this answer | |
  • 5
    $\begingroup$ 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.) $\endgroup$ – Aaron Meyerowitz Aug 10 '18 at 7:20
  • 1
    $\begingroup$ What was your theorem? $\endgroup$ – Charles Aug 11 '18 at 1:55
  • 1
    $\begingroup$ Don't standard conjectures (Dickson) imply there should be (infinitely many) $p$-progressions for every $p$? $\endgroup$ – Wojowu Aug 11 '18 at 8:27
  • $\begingroup$ @Wojowu Could you elaborate on the precise statement of this conjecture? $\endgroup$ – Kim Aug 11 '18 at 9:56
  • $\begingroup$ @Kim primes.utm.edu/glossary/xpage/DicksonsConjecture.html $\endgroup$ – 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).

| cite | improve this answer | |

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


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


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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.