For some reason Problem 61 of Project Euler is a problem that not so many people have solved compared to the problems in the sixties range. However, I think that it was a quite approachable problem which was fun to solve. The problem reads

Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:

TriangleP_{3,n}=n(n+1)/21, 3, 6, 10, 15, …SquareP_{4,n}=n^{2}1, 4, 9, 16, 25, …PentagonalP_{5,n}=n(3n-1)/21, 5, 12, 22, 35, …HexagonalP_{6,n}=n(2n-1)1, 6, 15, 28, 45, …HeptagonalP_{7,n}=n(5n-3)/21, 7, 18, 34, 55, …OctagonalP_{8,n}=n(3n-2)1, 8, 21, 40, 65, …

The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.

1. The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).

2.Each polygonal type: triangle (P_{3,127}=8128), square (P_{4,91}=8281), and pentagonal (P_{5,44}=2882), is represented by a different number in the set.

3. This is the only set of 4-digit numbers with this property.

Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.

I used a fairly efficient brute force method to find the solution. The algorithm goes

- Generate all four digit triangle, square, … , octagonal numbers
- Start with any number as the beginning of the chain
- Given the chain current find a number that
- is cyclic as described
- is not a type of number which is already used in the chain
- is different from other numbers in the chain

- If the chain is of length 6 check that it can be closed – if true then finish
- If such a number exists add it to the chain and go to 3
- If no such number exists remove the last number from the chain and go to 3.

## Generating figurate numbers

It is rather easy to generate all the four digit numbers. There are only 97 four digit triangular numbers and for the other cases the number is smaller. The smallest being octagonal numbers with only 41 4 digit numbers. There is a total of 357 numbers to keep track of.

I wont show you the code for generating the numbers as it is trivial. You can see it in the source code if you like.

## Finding the chain

In order to avoid a whole lot of nested for-loops as I can see some other solutions contains I made the search for the chain as a recursive function.

Which contains 3. to 6. on my small pseudo algorithm, so let me post the code and comment on it

public bool FindNext(int last, int length) { for (int i = 0; i < solution.Length; i++) { if (solution[i] != 0) continue; for (int j = 0; j < numbers[i].Length; j++) { bool unique = true; for(int k = 0; k < solution.Length; k++){ if (numbers[i][j] == solution[k]) { unique = false; break; } } if ( unique && numbers[i][j] / 100 == solution[last] % 100) { solution[i] = numbers[i][j]; if (length == 5) { if (solution[5] / 100 == solution[i] % 100) return true; } if (FindNext(i, length + 1)) return true; } } solution[i] = 0; } return false; }

Where *numbers* and *solution* are class variables.

The solution is being build in an array, where index 0 represents triangle numbers and so on.

The majority of the code is about point 3 finding the next number.

The for loops on line 2 and 4 goes through all the possible numbers in the search.

Line 3 ensures that the chain does not contain two numbers of the same type as stated in 3.02.

Line 6-12 ensures that the chain does not contain two numbers that are the same as stated in 3.03. The first solution I found contained 1045 as both triangle and hexagonal number. A solution which was not allowed. I could have written this a one line linq statement, but due to performance I chose not to.

Line 14 checks if the number is cyclic, and if so adds it to the chain.

Then we have a check that we can close the chain if the length is correct on line 17-20. If so we return true.

Line 21 is where the recursion actually happens. So if we reach the bottom and find a valid chain then we return true all the way up. If we return false we will instead remove the last number added to the chain continue the search until we either finds a valid number or run out of numbers to search through. If we run out of numbers we return false.

It always takes me a little while to see through recursive methods, but I hope it is clear for you once you read the code a few times. The only thing we need now is to call the recursive method.

## Main method

I have decided to start the chain with an octagonal number since there are the fewest of them. I doubt it will make any difference, since it means there is a larger search space for the rest of the chain. The main method looks like

int result = int.MaxValue; solution = new int[6]; numbers = new int[6][]; for (int i = 0; i < 6; i++) { numbers[i] = generateNumbers(i); } for (int i = 0; i < numbers[5].Length; i++) { solution[5] = numbers[5][i]; if (FindNext(5, 1)) break; } result = solution.Sum();

In theory we would have to have searched 33723162396 permutations to search for a solution. However, since we don’t generate all permutations but tries to build the chain one piece at a time we limit that search space significantly. In fact when we run the code we get the following result.

8256, 5625, 2882, 8128, 2512, 1281 The sum of the series is 28684 Solution took 1 ms

The chain is shown in the first line, not in the chain order, but with triangle numbers followed by square and so on. The chain looks like

1281, 8128, 2882, 8256, 5625, 2512

It runs in 1ms, so I am quite pleased with the resulting performance.

## Wrapping up

I provided one very fast solution to the problem at hand of finding the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.

The source code is as usually available for you if you like to take a peek at it and the things I left out.

Did you solve it in another way? Do you have comments? Do you have questions. Don’t be afraid of asking them in the comment section I would love to hear from you.

The blog image is attributed to Nayu Kim who kind shared it under the creative commons license. It shows a pentagonal aperture of a lens.

Table 1

Four sets (size: 3, 4, 5, 6) of different cyclic 4-digit numbers.

[Re: Project Euler – Problem 61: Cyclical figurate numbers]

http://img11.hostingpics.net/pics/776916pe61tab1cycl.jpg

In Table 1, under column “Cyclic 4-digit numbers (cyclic order)”, we can see that interconnection between two sets is possible:

EN1 & EN3:

8128; 2882; 8281 & 8128; 2850; 5017; 1782; 8281

___

Sources:

1) Project Euler – Problem 61

Kristian’s algorithm

http://www.mathblog.dk/files/euler/Problem61.cs

2) Formula

PE61, article:

http://www.mathblog.dk/project-euler-61-numbers-cyclic-property/

3) Microsoft Visual C# 2010 Express

4) Microsoft Office Excel (2007)

___

Thanks to Kristian for this inspiring article and algo.

🙂

> The blog image is attributed to Naya Kim who kind shared it under the creative commons license. It shows a pentagonal aperture of a lens.

Ahem, it’s Nayu Kim. =)

What really confused me here was the definition of what a cyclic number was. In the example given each number shares 2 digits but it’s never stated that that has to be the number of shared digits.

While generating the n-agonal numbers, you can skip any whose least significant two digits form a number < 10, since the most significant 2 digits of candidate 4 digit numbers can’t start with a 0.

My brute force solution in C++, along the same lines as yours, took 0.04 ms.