Enigmatics |
|
Posted on: Thursday 29/11, 2007; 3:27 PM Load the Combinatorica package for doing operations on graphs. Derive the formula for triangular numbers.
Generate a list of triangular numbers less than 1000.
Split each of the triangular numbers into its constituent digits.
Compute and display the adjacency matrix for the allowed transitions between numbers.
Define a function for iterating the adjacency matrix, and normalise its output to bound the size of the matrix elements. This will be used to discover zero rows/columns in the iterated adjacency matrix, which correspond to nodes that do not belong to a cycle. Compute and display the iterated adjacency matrix.
Delete the triangular numbers that correspond to zero rows in the iterated adjacency matrix, because they do not contribute to the sought after cycle.
Compute and display the new adjacency matrix, and its iterated form.
Repeate the above process for zero columns in the new adjacency matrix.
HamiltonianCycle is not designed to work on directed graphs, so the following step is not strictly valid. Exhaustively delete all possible 1 or 2 triangular numbers and look for a Hamiltonian cycle in the resulting adjacency matrix. Extract the cases in which a Hamiltonian cycle was found.
Only the 3rd case is a valid Hamiltonian cycle. Cases 1, 2 and 4 violate the adjacency matrix condition at the end of the cycle (e.g. {3, 7, 8}, {3} cannot be a part of a Hamiltonian cycle because 8≠3). However, HamiltonianCycle is not designed to work on directed graphs, so problems such as this are to be expected. The correct solution is case 3.
The number of digits in this cycle is
This is not actually the solution to the stated problem which asks for the maximum number of digits in the cycle, not the maximum number of triangular numbers in the cycle. |
Blogged from |
||||
