Prime Sequences

Age 16 to 18

Challenge Level Yellow star

Amy from Birmingham answers the first set of questions.

Can you find an arithmetic progression of four primes?
$5, 11, 17, 23$ is an arithmetic progression starting at $5$ with a difference of $6$.
This can also be extended to a progression of $5$ primes by $5, 11, 17, 23, 29$

How many prime APs beginning with $2$ can you find?
There can't be any prime APs beginning with $2$ because $2$ is the only even prime number. So the arithmetic progression difference can not be an even number. So if you add an odd number on to get to a prime, say add $2k+1$ where $k$ a whole number, so $2+2k+1 = 2k+3$ is a prime number. Then if we add on the common difference again to get $p+2k+1 = 2k+3+2k+1 = 4k+4 = 4(k+1)$ which is an even number and so cannot be a prime number. So APs beginning with $2$ can only have $2$ components, and so are not an AP.

How many other arithmetic progressions of prime numbers from the list of primes below can you find?
We know from above that they must have common differences of even numbers. Eg.
$3, 5, 7$ - difference 2
$3, 7, 11$ - 4
$3, 11, 19$ - 6
$3, 13, 23$ - 10
$3, 17, 31$ - 14
$3, 23, 43$ - 20
$3, 31, 59$ - 28
$3, 37, 71$ - 34
$3, 41, 79$ - 38
and so on. So there are lots and lots.
The only progression with common difference $10$ is $3, 13, 23$ because one of them will always divide by $3$. We know the digits in a number that divides by $3$ will always add up to $3, 6$ or $9$ so if all the digits in a number $p$ add up to $k$ then $p+10$ adds up to $k+1$ and $p+20$ adds up to $k+2$, and one of $k, k+1, k+2$ will always be divisible by $3$ as three consecutive numbers will always have one that divides by $3$.

Good answers Amy, and well done on developing your ideas to show that $3, 13, 23$ is the only prime AP with common difference $10$. Can anyone think of a more concise way of expressing Amy's ideas? Can anyone find any more of the many prime APs?
.
Clark managed to complete the next few using modular arithmetic. If you are unfamiliar with this area of maths you might want to read the article Modular Arithmetic first.

Why is $3, 5, 7$ the only prime AP with common difference 2?
Because one of them will always divide by $3$. A sequence of numbers $p, p+2, p+4$ will always have one number which divides by three. If we use modular arithmetic, and take $p, p+2, p+4$ modulo 3 then we have $3$ options.

p	p+2	p+4
0	2	1
1	0	2
2	1	0

Where the top row is the number itself, and then each row shows what this would equal if $p=0, 1, 2$ mod $3$. As we can see, there is always a zero in each row, and so in any sequence of $3$ numbers where the difference is $2$, one will always divide by three, and so cannot be prime. So as $3$ itself is the only prime number divisible by $3$, the only AP of difference $2$ must include $3$, and so the only prime AP of common difference $2$ is $3, 5, 7$

What is the maximum length of a prime AP with common difference 6?
Using a similar method to above, we can show that a sequence of $5$ numbers of difference $6$ will always have a member that is divisible by $5$. Looking at a sequence $p, p+6, p+12, p+18, p+24$ and putting into a table as above, so a looking at what each sequence would be equal to modulo $5$ given that $p=0,1,2,3,4$

p	p+6	p+12	p+18	p+24
0	1	2	3	4
1	2	3	4	0
2	3	4	0	1
3	4	0	1	2
4	0	1	2	3

So the only sequence of length $5$ with common difference $6$ is the one including $5$, as that is the only prime divisible by $5$. So $5, 11, 17, 23, 29$

Otherwise the length of all sequences with common difference $6$ will be $4$ or less.

Eg, $41, 47, 53, 59$ or $61, 67, 73, 79$

Claim: If the common diference of a prime AP is $N$ then the maximum length of the prime AP is $N-1$
I have noticed a pattern in the examples above, that is the longest sequence involves starting on the prime number that is the length of the sequence. Compiling a similar table, I shall show that the sequence $p, p+N, p+2N, ... , p+(N-3)N, p+(N-2)N$ will always have one component that divides by $N-1$, so if a sequence of this length exists, it must start on the prime $N-1$. This also relies on the sequence $p, p+N, ... , p+(N-2)N$ being all primes, which is unlikely. But supposing this to be true, I shall continue. The table, as above, shows what each of $p, p+N, ... , p+(N-2)N$ would be equal to modulo $N-1$ if $p=0, 1, 2, ... , N-2$

p	p+N	p+2N	...	p+(N-3)N	p+(N-2)N
0	1	2	...	N-3	N-2
1	2	3	...	N-2	0
2	3	4	...	0	1
...	...	...	...	...	...
N-3	N-2	0	...	N-5	N-4
N-2	0	1	...	N-4	N-3

And so we can see, as before, that one number in the sequence is always equal to zero mod $N-1$, and so is divisible by $N-1$.

So if a prime AP of length $N-1$ with common difference $N$ exists, it must start on the prime number $N-1$, and no AP longer than $N-1$ can exist.

What is the maximum length of a prime AP with common difference 10?

I shall build on Amy's description in the $3rd$ question. Using my table method with modulo 3:

p	p+10	p+20
0	1	2
1	2	0
2	0	1

Which says exaclty what Amy noticed, that with any starting prime, one member of the sequence starting at $p$ with common difference $10$ will always divide by $3$. So the only AP of length $3$ will be when the starting prime is $3$. So $3, 13, 23$

What is the maximum length of a prime AP with common difference 100, 1000, 10000?

Similarly as above, if they exist the longest will be of length $3$, and start at the number $3$. By writing $100=10^{2}$ and $200=2\times 10^{2}$ and similarly for $1000$ and $10000$, then I can compile the table as usual considering modulo 3.

Because $99, 999, 9999$ are all divisible by three then

p	p+$10^{n}$	p+$2\times 10^{n}$
0	1	2
1	2	0
2	0	1

for all $n$ whole numbers. In this case, we are just considering $n=2, 3, 4$. So we have that if a prime AP of length $3$ exists, it must start at $3$, for reasons discussed earlier. Now to check that in the cases $n=2, 3, 4$ these exist.

For $n=2$, common difference is $100$, so the AP would need to be $3, 103, 203$ but $203=29\times 7$ and so this AP does not exist.

For $n=3$ the common difference is $1000$, so the AP would be $3, 1003, 2003$ but $1003=17\times 59$ so AP does not exist.

And for $n=4$ the common difference is $10000$, so the AP would need to be $3, 10003, 20003$, but $10003=7\times 1429$, and so the AP does not exist.

And so there does not exist a prime AP with common difference $100, 1000$ or $10000$

What are the possible lengths of prime APs with common difference $2p$, where $p$ is prime?

Case 1) $p=3$

When $p=3$ then $2p=6$ and this case was discussed above under question $5$. The possible lengths of prime APs are $3, 4$ or $5$/

Case 2) $p> 3$

Suppose we are starting with a number $n$ in the sequence. Then the sequence will be $n, n+2p, n+4p, n+6p, ...$. I claim that the sequence can only ever be $3$ long.

I shall divide into 2 cases, when $2p-1$ is divisible by $3$ and when $2p+1$ is divisible by $3$. I do not need to consider $2p$ divisible by $3$ as this cannot occur, as $2p$ has prime factorisation $2p = 2 \times p$

Case 2 A) $2p \equiv 1$ mod $3$ - eg, $p=5, 11$

Then the table of possible progressions modulo $3$ is

n	n+2p	n+4p
0	1	2
1	2	0
2	0	1

And so as before we see there is always one number divisible by $3$, and so the only possibility is starting at $3$ and having three members in the sequence.

Case 2 B) $2p \equiv 2$ mod $3$ - eg, $p=7, 13$

n	n+2p	n+4p
0	2	1
1	0	2
2	1	0

And as we would expect, the sequence of three numbers must contain one that is divisible by three, and so the only possibility are ones starting at $3$

Putting these together, for all primes $> 3$ the prime AP with common difference $2p$ starts at $3$ and is three terms long, if that.

For example when $p=11, 2p=22$ and as $25$ not prime, this has no APs as we demanded the length be longer than $2$.

This leads me to claim that for prime APs of length longer than $3$ to exist, then the common difference must be a multiple of $6$, so that if it is started on a prime $> 3$, it shall never pass through a multiple of $3$. Though it may obviously pass through other non prime numbers, and so not exist for all multiples of $6$.

Well done Clark! Some excellent proofs and clear points. I particularly like that you have continued your investigation and have summed up your findings with a new claim. Can anyone think how to prove or disprove Clark's claim?

Can you see how Clark's claim is linked into the final question? Can anyone link them and prove one with the other? Can anyone prove outright either claim?

Good luck!

Prove that if an AP-$k$ does not begin with the prime $k$, then the common difference is a multiple of the primorial $k$#$=2 \cdot 3 \cdot 5 \cdot ... \cdot j$, where $j$ is the largest prime not greater than $k$.

Number and algebra

Geometry and measure

Probability and statistics

Working mathematically

Advanced mathematics

For younger learners

Prime Sequences