## Brainteaser 1721: Prime leaps

**From The Sunday Times, 10th September 1995** [link]

The history-cum-maths teacher asked the class to name some years which the knew from history lessons. Johnny named 1066, the Battle of Hastings, and 1939, the outbreak of the Second World War. The teacher then asked him to calculate the difference between the two and Johnny got the correct answer of 873.

The teacher then asked Johnny if this difference was prime and Johnny answered correctly that it was not because, for example, it was divisible by three.

The teacher then asked the class to find the longest list of years they could from 0, 1, 2, …, 1999, 2000 so that for any two numbers in the list their difference was not prime.

Which numbers are in the longest such list?

This puzzle was included in the book *Brainteasers* (2002, edited by Victor Bryant). The puzzle text above is taken from the book.

[teaser1721]

## Jim Randell 5:05 pm

on29 September 2019 Permalink |First, lets treat the list as a sequence of consecutive integers starting at 0. (We’re only interested in differences, so it doesn’t really matter where we start).

If we consider the set of numbers (0, 4, 8, 12, 16, …) (i.e. the multiples of 4) then we see the difference between any two numbers is also a multiple of 4, and hence not prime. This allows us to select ⌈n / 4⌉ numbers from a sequence of

nnumbers.And this is the best we can manage. Every segment of size 4 has 1 number (and if there is a shorter segment left over from chopping the sequence into fours, then that also has one number).

To do better we would have to have a segment of size 4 with (at least) two numbers in it.

We can’t have … 0 _ 2 _ … or … 0 _ _ 3 … as these have a difference of 2 and 3 respectively, so the only possible segment is … 0 1 _ _ ….

But any numbers that differ by 1 have to be followed by (or preceded by) 7 gaps:

So the best we could manage is 2 numbers out of every 9, which is worse than 1 out of every 4.

So presented with a sequence of 2001 numbers the best we can manage is ⌈2001 / 4⌉ = 501 numbers: (0, 4, 8, 12, 16, …, 1992, 1996, 2000).

Solution:The longest list contains all exact multiples of 4.Considered as years (ignoring the fact that there was no year 0), most of the numbers represent leap years, hence the title of the puzzle.

LikeLike