Listen With Others

Background

I decided to base a puzzle on multigrades (nothing to do with oil — it’s the Prouhet-Tarry-Escott problem which is to find two sets of numbers in which the sums of the powers of the numbers in each set are the same). More details can be found by Googling ‘Prouhet Tarry’ or ‘Multigrade Equations’. I wanted to create a puzzle that had a wow factor.

It has been proved that if there are n numbers in each set, it is possible to find cases that work for all powers up to n-1 (these best cases are called ‘ideal’).

A simple example is the sets [1, 5, 6] and [2, 3, 7].

 
This can be written as [1, 5, 6] =₂ [2, 3, 7].

A feature of these sets is that any number — positive or negative — can be added to all the numbers and the relationship still holds, but the most elegant ones are those where the smallest number is 1.

A much better example is

[1, 5, 10, 24, 28, 42, 47, 51] =₇ [2, 3, 12, 21, 31, 40, 49, 50]

Chen Shuwen (http://euler.free.fr/eslp/) has found an amazing case:

[1, 12, 25, 66, 91, 130, 174, 213, 238, 279, 292, 303] =₁₁ [4, 6, 31, 58, 105, 117, 187, 199, 246, 273, 298, 300]

Given an example that works for all powers up to n it is easy to generate another example from it that works all the way up to power n+1 (it looks impressive, but the mathematical proof is trivial).

Take the above example, [1, 5, 6] =2 [2, 3, 7]. Write down the numbers on the left, and extend the sequence by writing down the numbers on the right plus any constant (in this example, 5):

[1, 5, 6, 7, 8, 12]

Now write down the numbers on the right and extend that sequence by writing down the numbers on the left plus the same constant:

[2, 3, 7, 6, 10, 11]

We now have [1, 5, 6, 7, 8, 12] =₃ [2, 3, 7, 6, 10, 11] which reduces to [1, 5, 8, 12] =₃ [2, 3, 10, 11].

The constant 5 was chosen so that a couple of terms cancelled each other out.

Applying a constant of 7 to these sets, we get [1, 5, 9, 17, 18] =₄ [2, 3, 11, 15, 19].

This method doesn’t find all cases, though, and the number of terms in each set gets large very quickly and the cases soon cease to be ideal.

Puzzle Thoughts

At first I thought of using Chen’s sets plus a constant as the grid entries for a puzzle, but I felt that I should produce my own rather than copy someone else’s. Then I had a brainwave — would it be possible to have more than two sets with the relationship? I instinctively felt that it would be impossible, but I did some Googling anyway. All I found was one example of four sets but no indication of how it was derived.

I decided to write a small program to get a feel of how many cases there were with more than two sets. There were many of them, two of which are below:

Multiple Sets

The ball was now rolling. What about larger sets and higher powers? How about six numbers in each set and therefore powers up to five? The program for the above examples was trivial; for each combination of four numbers a line was written to a text file that consisted of the sum of the numbers, the sum of their squares, the sum of their cubes, and then the four numbers. The file was sorted and then scanned for adjacent lines that had the same first three numbers (i.e. the sums of the powers).

It wouldn’t be straightforward for six numbers, though — it would have six nested loops and if it handled numbers in the range 1 to 999 there would be 1,359,964,259,197,551 iterations if duplicate numbers were excluded. This would result in rather a lot of processing, a rather large file and a healthy contribution to Octopus Energy.

A method was required that required significantly less processing and disk storage (“If your program uses too many resources, the first step is to improve your algorithm”).

A Different Method

I noticed that in each of the sets found so far, the sum of the first and last number was a constant. I tried finding sets of six numbers with values up to 99 and found in all my cases that the sum of the second and penultimate numbers added to the same constant as well, as did the third and third-to-last (in the examples in the table above, the constants are 49 and 59, and in Chen Shuwen’s earlier example, the constant is 304). I managed to find some two-set examples online where the values do not add up to a constant, for example…

[0, 19, 25, 57, 62, 86] =₅ [2, 11, 40, 42, 69, 85]

…but I was looking for material for a puzzle, not attempting to produce a complete set of cases, and so I decided to apply a constant as a criterion to keep it all manageable. My six nested loops could now become three, resulting in far fewer iterations, but this was still too many to be writing the results to a file.

Looking at the nature of the results, I could see that there were bounds that I could place on the inner numbers thus avoiding lot of unnecessary processing, and so I developed an improved version. Another pattern then came to light, and my next version quickly found all six-number sets with numbers up to 999 where the sums of the numbers added up to a constant. Since the constant was always even, I made that a constraint too and so I was able to halve the running time of the program. Moreover, by processing the constants one at a time, there was no sorting to do at the end. I knew I was not finding all the cases (I believe I was finding over half of them) but it was good enough for the purpose of creating a puzzle.

The final program ran in under 12 seconds and the size of the output file was under 3MB.

The Results

I wrote a wee program to scan the output file to find the cluster size of the sets and the results looked like this:

Yes — there were nine sets of six numbers that had matching sums of powers! This was obviously going to form the basis of the puzzle. Here are the nine sets:

I can’t help thinking that there must be a neat way of finding these sets, but I haven’t got enough number theory knowledge to know how to do it — and if there is a neat way, why can’t I find anything on the web?

The Puzzle

I then had to decide how these sets could be made into a puzzle. Some fitting trials were undertaken using just six sets (36 numbers). It quickly became clear that the chance of fitting these sets of numbers into a symmetrical grid was remote and so it would be well-nigh impossible for nine sets.

I thought of fitting all the numbers into a symmetrical grid and having a hint like SUM OF NTH POWERS EQUAL, using my usual algebraic clues. This has 19 letters but there would have been at least a couple of dozen clues — that’s too many for so few letter values.

I considered various other ideas, and in the end I decided that I would need more letters in the hint. After referring to my thesaurus I ended up with SUM OF NTH POWERS IDENTICAL. There were no more than two of any letter which meant that I could use lower- and upper-case letters in the hint.

Since it wasn’t feasible to fit all the numbers from the sets into a symmetrical grid, how about having some in the grid and some to be deduced? This, though, would have meant mentioning sums of powers in the preamble, and I wanted this aspect of the puzzle to be a surprise.

So how about half of them? That would mean 27 numbers. This is an odd number and so the grid would have to have an odd number of rows and/or columns, meaning a grid like 6×7, 7×7 or 7×8. But what then? What about the other half of the numbers? It was then that I thought of having 918 as a grid entry so that the solver could easily determine the other numbers but without me having given the game away. There would be many ways of selecting three numbers from each set, thus increasing the chance of populating a grid.

The Grid

If I had 918 as a grid entry then I could have one of each of the numbers that added up to 918 in the grid (27 of them, making 28 in total). I couldn’t have single-digit grid entries, and so of the numbers [1, 917], [2, 916] and [4, 914] I had to have 917, 916 and 914 in the grid, as well as the 918. Of the remaining 48 numbers, one each of the remaining number pairs had to be in the grid. I decided to fit the numbers into an 8×6 grid because for some reason that felt right.

Fitting the Numbers into the Grid

Once again I resorted to my antique grid-generating and number-fitting program. I tweaked it so that each grid would include the required numbers (914, 916, 917 and 918), set it running and went to bed.

It generated and attempted to fill all possible grids which fitted my criteria and came up with just a handful of solutions. Amazingly, one of them (found at 3am) had top/bottom and left/right symmetry and it could be filled in only one way (I’m not happy if this is not the case, even though it wouldn’t matter) and the 918 was fully checked (which was good, because I didn’t intend to have a clue for it). Satisfyingly, there was quite a high proportion of checked digits.

The Clues

What about the clues? The theme was powers, and so the clues, ideally, would need to be based on them. Although I was aware that letter values that were powers could create a puzzle that was too easy, I decided to go along this route anyway. At first, I thought about having letters in the clues representing numbers that could be expressed as n, n + n² or n + n² + n³ where n > 1, but didn’t really fancy that.

I decided to have not more than four letter values in any clue (so that they did not appear cumbersome), or any numbers. I wrote a program to generate all possible clues and manually pored through them, selecting expressions that would produce a logical solving path — I wanted minimal trial and error in the solving process.

Having solved the clues, solvers needed to supply the missing numbers in each set. Having a table under the grid was the only way I could think of handling it, but the first vetter came up with an improvement which didn’t take up so much space (he also suggested the extra phrase in the preamble that said that if the relationship was true for any two of the sets, then it was true for all of them, because he was unhappy about the amount of computation in the final step).

The next problem was how to make solvers aware of the property of the sets, and I thought of writing the values of N below the grid. The vetter had the better idea of entering a range. Presumably, some solvers would forget to include zero!

The Calculations

There were various ways to calculate the powers of numbers up to 999 (for example, in the Windows calculator, 914y5 calculates 914⁵), one of which was to use my 1961 Brunsviga 20 pinwheel calculating machine weighing 25lb (11½kg), a perfect example of over-engineering — it was made to last 200 years but was superseded by electronic calculators which came onto the market in the early 1970s. The photo below shows the result of calculating 917⁵, which took just under a minute and made some very satisfying clicking sounds. The calculator has a back-transfer mechanism, which means that when a product has been calculated the result can be transferred to the setting levers (where the operand is entered) ready for a further calculation — perfect for calculating powers!

To add fifth powers, the user has to employ a digital system, i.e. grab hold of a pencil and paper, write down the individual powers and then sum them.