Prime Sequences

Age

16 to 18

Challenge level

This group tasks allows you to search for arithmetic progressions in the prime numbers. How many of the challenges will you discover for yourself?

Thinking mathematically tags

Mathematical mindsets tags

Being curious Being resourceful Being resilient Being collaborative

Problem

In 2004 an exciting new result was proved in Number Theory by two young mathematicians Ben Green and Terence Tao. They proved that if you look in a long enough list of the prime numbers then you will be able to find numbers which form an arithmetic progression containing as many numbers as you choose! In this question we explore some of the interesting issues surrounding arithmetic progressions of prime numbers.

An $AP-k$ sequence is $k\geq 3$ primes in arithmetic progression. See examples

This problem involves several linked parts leading up to a final challenge. Try some of the earlier questions to gain insights into the final challenge. These can be attempted in any order. You might find that you naturally ask yourself questions which are found later in the list of questions and you might find that one part helps in the consideration of another part. Of course, you are welcome to go straight to the final challenge. However, you might also wish to start with one of the earlier challenges and see how many of the other challenges you naturally discover whilst exploring the underlying mathematical structure.

Consider some of these three questions first:
Question A	Can you find an arithmetic progression of four primes?
Question B	How many prime APs beginning with $2$ can you find?
Question C	How many other arithmetic progressions of prime numbers from the list of primes below can you find?
Next consider some of these three questions:
Question A	Why is $3, 5, 7$ the only prime AP with common difference $2$?
Question B	What is the maximum length of a prime AP with common difference of $6$?
Question C	If the common difference of a prime AP is $N$ then the maximum length of the prime AP is $N-1$.
Now consider some of these three questions:
Question A	What is the maxiumum length of a prime AP with common difference $10$?
Question B	What is the max length of a prime AP with common difference $100, 1000, 10000$ ?
Question C	What are the possible lengths of prime APs with common difference $2p$, where $p$ is prime? Consider $p=3$ and $p> 3$ separately.

When you have thought about some of the previous problems you might like to try the final challenge

In doing these problems you might like to see this list of primes

Student Solutions

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

Teachers' Resources

Using NRICH Tasks Richly describes ways in which teachers and learners can work with NRICH tasks in the classroom.

Why do this problem?

This problem involves a significant 'final challenge' which is broken down into a sequence of three groups of mini-challenges. The mini-challenges are not arranged in any particular order within each group and the problem is structured such that students are likely to 'discover' some of the mini-challenges for themselves as they strive to solve other mini-challenges.

These notes are designed for classes who are able to work in groups.

At the outset all challenges are hidden to the learner to maximise the chance of discovery for the learners.

The purpose of this is two-fold: first to scaffold learners to help them solve a difficult challenge; second to show that mathematics is a natural subject where certain questions naturally arise through the consideration of other questions. This will firstly help students to structure their mathematical thinking and secondly to help them to realise that mathematics is not externally or meaninglessly imposed.

Possible approach

There are three groups of 3 mini-challenges and the final challenge. Leave these all hidden to begin with.

Throughout the challenge the focus will be on constructing clear, concise proof and on thinking of possible extension questions.

Very able students might wish to start on the Final Challenge, but it will be good to give them a single mini-challenge and see where their thinking and invention takes them. Indeed, the best and most inventive students might even 'discover' the final challenge for themselves.

It is suggested that the following approach be taken

1) (10 minutes) Students individually given one of the first mini-challenges to think about and work on. Spread the different mini-challenges amongst the group -- don't allow students to see any of the other challenges or talk about this with their neighbours. Students are to think about their challenges and explicitly write down any other thoughts or questions that arise. Encourage those that think they have an answer to construct the clearest proof possible or to think about possible extensions.

2) (5 minutes) A selection of students to describe their challenge, proofs and other questions arising. It is likely that some of the questions arising will be the problems other students were working on directly.

3) (10 minutes) Ask the class to organise themselves in pairs so as to get insight into solving their mini-challenge or proposed extensions. It might be that students pair with people working on the same mini-challenge or pair with someone who was thinking about a related problem. Give the pairs a new challenge from the second grouping to work on.

4) Repeat step 2 and group into 4s, whilst giving the fours a mini-challenge from the third grouping to work on.

5) Throughout encourage the class to propose their own extension questions.

At some point students might solve their challenges or pose the final challenge for themselves. When appropriate move the discussion onto the construction of a clear proof of the final challenge. This will be ideally a group effort.

Key questions

As you think about your mini-challenge, what questions and extensions arise?

Complete the sentence: I am finding this task difficult because ...

Complete the sentence: I wonder if ....

Complete the sentence: I would be more able to solve my challenge if I knew ...

Can you explain your proof clearly in words?

Possible extension

Solution of the final challenge on its own is a tough challenge.

Possible support

This task is designed for group work -- encourage groups not to move on until all in the group understand.

Some students might be uncomforable with posing their own questions or verbalizing their difficulties. Encourage an atmosphere where all questions and difficulties are valid.

2	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71
73	79	83	89	97	101	103	107	109	113	127	131	137	139	149	151	157	163	167	173
179	181	191	193	197	199	211	223	227	229	233	239	241	251	257	263	269	271	277	281
283	293	307	311	313	317	331	337	347	349	353	359	367	373	379	383	389	397	401	409
419	421	431	433	439	443	449	457	461	463	467	479	487	491	499	503	509	521	523	541
547	557	563	569	571	577	587	593	599	601	607	613	617	619	631	641	643	647	653	659
661	673	677	683	691	701	709	719	727	733	739	743	751	757	761	769	773	787	797	809
811	821	823	827	829	839	853	857	859	863	877	881	883	887	907	911	919	929	937	941
947	953	967	971	977	983	991	997	1009	1013	1019	1021	1031	1033	1039	1049	1051	1061	1063	1069

Or search by topic

Number and algebra

Geometry and measure

Probability and statistics

Working mathematically

Advanced mathematics

For younger learners