Project Euler 61: Find the sum of the only set of six 4-digit figurate numbers with a cyclic property

Project Euler 61: Find the sum of the only set of six 4-digit figurate numbers with a cyclic property

Written by on 17 September 2011

Topics: Project Euler

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:

TriangleP3,n=n(n+1)/21, 3, 6, 10, 15, …
SquareP4,n=n21, 4, 9, 16, 25, …
PentagonalP5,n=n(3n-1)/21, 5, 12, 22, 35, …
HexagonalP6,n=n(2n-1)1, 6, 15, 28, 45, …
HeptagonalP7,n=n(5n-3)/21, 7, 18, 34, 55, …
OctagonalP8,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 (P3,127=8128), square (P4,91=8281), and pentagonal (P5,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

  1. Generate all four digit  triangle, square, … , octagonal numbers
  2. Start with any number as the beginning of the chain
  3. 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
  4. If the chain is of length 6 check that it can be closed – if true then finish
  5. If such a number exists add it to the chain and go to 3
  6. 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; } [/csharp]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(); [/code]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.[code] 8256, 5625, 2882, 8128, 2512, 1281 The sum of the series is 28684 Solution took 1 ms [/code]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[code] 1281, 8128, 2882, 8256, 5625, 2512 [/code]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.

3 Comments For This Post I'd Love to Hear Yours!

  1. Jean-Marie Hachey says:

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

  2. Nayukim says:

    > 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. =)

  3. Sim says:

    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.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.