Project Euler/61

Problem Statement

This problem explores an extension of the concept of a triangular number, generated by the formula ${\dfrac {n(n+1)}{2}}$, to other shapes.

Exploring triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers - numbers that are generated according to particular formulae:

$P_{3,n}={\dfrac {n(n+1)}{2}}$

$P_{4,n}=n^{2}$

$P_{5,n}={\dfrac {n(3n-1)}{2}}$

$P_{6,n}=n(2n-1)$

$P_{7,n}={\dfrac {n(5n-3)}{2}}$

$P_{8,n}=n(3n-2)$

Link: https://projecteuler.net/problem=61

Solution Technique

CURRENTLY UNSOLVED

Our solution technique is to generate a graph (for this, we use the Guava library).

We wish to find the sum of the ordered set of six cyclic 4-digit numbers for which each polygonal type, triangle/square/pentagonal/hexaongal,/heptagonal,octagonal, is represented by a different permutation of the digits (maintaining original order).

To do this, we create a graph, with each possible connection between a prefix and a suffix marked with an edge.

This results in a 6-partite graph, and we seek a path, a cycle, that passes through all 6 partitions.

crux (several years later)

The approach described above was sound, the implementation was logical, but the program just contained one significant, fatal bug: when we assembled the graph connecting four-digit numbers with shared first-two-digits and last-two-digits, we incorrectly implemented it to connect last-two-digits to last-two-digits. Change a % to a / and it worked okay.

Code

https://git.charlesreid1.com/cs/euler/src/branch/master/scratch/Round2_050-070/061/GuavaFigurate.java

https://git.charlesreid1.com/cs/euler/src/branch/master/java/Problem061.java