Arithmetic Progression Puzzles: Keep Numbers Unevenly Spaced

To solve an evenly spaced number puzzle, keep choosing numbers but test every new one with the midpoint check: a new number is ruled out if it is the exact average of two numbers you already hold, or if one of your numbers is the exact average of it and another. From the numbers 1 to 9 the best you can do is keep five, and from 1 to 20 the best is nine ^[1].

This guide explains what evenly spaced means, gives a step-by-step method with the tricks that make it fast, works a full example and ends with practice puzzles and their answers.

What is an evenly spaced number puzzle?

Three numbers are evenly spaced when the gap from the first to the second equals the gap from the second to the third, as in 1, 5, 9 or 6, 10, 14. Mathematicians call such a trio a three-term arithmetic progression. The middle number is always the average of the outer two.

An evenly spaced puzzle comes in two flavours. In the first, you choose as many numbers as possible from 1 up to some limit so that no three of your chosen numbers are evenly spaced. In the second, you are given a list and asked to spot the one evenly spaced trio hiding inside it.

The three numbers do not have to sit next to each other in your list. If you hold 1, 2, 5 and 9, the trio 1, 5, 9 is evenly spaced even though 2 sits between 1 and 5. That is the detail most beginners miss.

How many numbers can you keep?

The answers for small ranges are known exactly, and the table below shows them with one best selection for each ^[1].

Every value in this table was rechecked for this guide by an exhaustive computer search, and each row agrees with the published values ^[1].

The number of best selections varies a lot. There are exactly four best selections from 1 to 9, but twenty-five from 1 to 8, and only two from 1 to 20 ^[1]. Fewer best selections means a puzzle with a forced answer is easier to set.

Why was the answer for 1 to 20 wrong for so long?

A paper from 1936 began the study of these selections and listed the best sizes for small ranges ^[2]. A paper published on 21 January 2012 showed that the 1936 value for the range 1 to 20 was wrong: the true best is nine, not eight ^[1], ^[2]. Some later values built on the faulty one rested on flawed reasoning as a result ^[1].

A second paper, published on 27 April 2012, used a computer search to settle the best size for every range up to 1 to 123 ^[2]. The whole calculation took about 30 hours on a personal computer, and one result is that 32 numbers can be kept from 1 to 122 ^[2]. That paper also showed that from 1 to any multiple of three, at least 48, you can never keep more than a third of the numbers ^[2].

The story is a useful warning for solvers. A hand count that feels complete can still miss a selection, which is why every count in this guide was checked by machine.

How do you check a set quickly?

Checking every trio in a set gets slow fast. The midpoint test is quicker. Two numbers can only have a whole-number midpoint when both are even or both are odd, so you only need to look at those pairs.

1. Split your numbers into evens and odds.
2. For each pair of evens and each pair of odds, work out the average of the pair.
3. If that average is in your set, you have spotted an evenly spaced trio.

Here is the test on the list 2, 4, 8, 16, 20, 21, 27, 28. The odds are 21 and 27, whose average 24 is not in the list. The six evens give fifteen pairs to test. Most averages miss, but 4 and 28 have average 16, which is in the list. So 4, 16, 28 is the evenly spaced trio, and it is the only one.

This cuts the work from twenty-eight pairs to sixteen, and it never misses a trio.

How do you build a large selection step by step?

1. Start from the bottom. Take 1, then work upwards, keeping each number that passes the midpoint test against everything you hold.
2. Note the result as a first draft. This greedy pass is fast and often good, but not always best.
3. Use both ends. Whenever the best size jumps up as the range grows by one, every best selection for the new range contains both the first and the last number ^[1]. Put them in first.
4. Try the mirror. If a selection works, replacing each number by its mirror image, counted from the other end of the range, gives another working selection ^[1].
5. Use doubling for big ranges. If a selection works for 1 to n, adding a copy of it shifted up by 2n - 1 gives a working selection for 1 to 3n - 1 ^[1].
6. Run the midpoint test on the final set. One missed pair spoils the whole answer.

What does the greedy pass give?

Run step 1 from 1 to 20. You keep 1 and 2, but 3 would complete 1, 2, 3. You keep 4 and 5. Then 6, 7, 8 and 9 all fail, because 6 completes 4, 5, 6, 7 completes 1, 4, 7, 8 completes 2, 5, 8 and 9 completes 1, 5, 9. You keep 10 and 11, skip 12, then keep 13 and 14, and nothing from 15 to 20 survives.

That leaves the pairs 1 and 2, 4 and 5, 10 and 11, and 13 and 14, which is eight numbers. Eight is the best possible up to 14, but up to 20 the best is nine ^[1]. Greedy choices made early can block better choices later, so treat the greedy result as a floor, not the answer.

What pattern hides in the greedy list?

Write each greedy number minus one in base three. You get 0, 1, 10, 11, 100, 101, 110 and 111, which are exactly the base-three numerals that use only the digits 0 and 1. A known observation says that numbers whose base-three form has no digit 2 never contain an evenly spaced trio ^[2].

The doubling rule from step 5 builds the same list. Start with 1, 2 in the range 1 to 2. Doubling gives 1, 2, 4, 5 in the range 1 to 5, and doubling again gives the greedy list in the range 1 to 14. One more doubling gives 16 numbers from 1 to 41, and 16 is the best possible there ^[1]. In fact that selection is the only best one for 1 to 41 ^[2].

How does the method solve a full example?

Here is an original puzzle. Choose five numbers from 1 to 9 so that no three are evenly spaced, and include the number 3. Five is the most you can keep from this range ^[1], so there is no slack.

Step 1: use both ends. The best size jumps from four to five when 9 joins the range, so every best selection contains 1 and 9 ^[1]. You now hold 1, 3 and 9.

Step 2: cross out what is now blocked. With 1 and 3 held, 5 would complete 1, 3, 5 and 2 would complete 1, 2, 3. With 3 and 9 held, 6 would complete 3, 6, 9. Five is already out, and it would also complete 1, 5, 9.

Step 3: list what is left. The candidates are 4, 7 and 8, and you need two of them.

Step 4: test each pair. The pair 4 and 7 fails, because 1, 4, 7 is evenly spaced. The pair 7 and 8 fails, because 7, 8, 9 is evenly spaced. The pair 4 and 8 passes.

Answer: 1, 3, 4, 8, 9. Run the midpoint test once more. The evens 4 and 8 have average 6, which is not held. The odds 1, 3 and 9 give averages 2, 5 and 6, none of them held. An exhaustive search of every five-number choice confirms this is the only answer.

It is also one of the four best selections from 1 to 9 listed in the published work ^[1]. Its mirror, 1, 2, 6, 7, 9, is another of those four, which is step 4 of the method in action.

How do the solving tricks compare?

Do evenly spaced patterns turn up in other puzzles?

They do, often in reverse. A paper published on 6 November 2002 colours the whole numbers so that, for every gap size, each long enough stretch contains an evenly spaced run whose members all have different colours ^[3]. Asking for that property along runs of a set length needs at least one more colour than the run has members ^[3].

The same paper links this to strings with no repeated block, where the rule must hold along every second, third or later symbol as well as along the string itself ^[3]. Spacing rules like these sit behind many puzzle patterns, from rows of tiles to repeating cycles.

What mistakes should you avoid?

• Testing only neighbours. The trio can be spread out, like 1, 5, 9 inside a longer list.
• Forgetting the new number can be the middle. When you add 7 to a set holding 5 and 9, the trio 5, 7, 9 appears with 7 in the middle.
• Trusting the greedy pass. It gives eight from 1 to 20, where nine is possible.
• Checking odd with even pairs. Their average is never a whole number, so they can be skipped.
• Stopping before the final test. Run the midpoint test on the finished set every time.

Can you solve these practice puzzles?

1. Choose six numbers from 1 to 11 so that no three are evenly spaced, and include both 5 and 7.
2. Spot the only evenly spaced trio in 1, 5, 12, 15, 19, 22, 24, 28.

Answers

1. 1, 2, 5, 7, 10, 11. Six is the best for this range ^[1], and every best selection from 1 to 11 uses both 1 and 11 ^[1]. Holding 1, 5, 7 and 11 rules out 3, 4, 6, 8 and 9: they would complete 3, 5, 7, then 1, 4, 7, then 1, 6, 11, then 5, 8, 11, then 5, 7, 9. Only 2 and 10 remain, and together they create no trio. A full search confirms that this is the only answer.
2. 5, 12, 19. The odds are 1, 5, 15 and 19, and the pair 5 and 19 has average 12, which is in the list. No other pair of odds or evens has its average in the list.

Each gem in this next puzzle returns to the top at evenly spaced steps, so each one traces its own arithmetic progression. Line up the progressions and see where they meet.