**From New Scientist #2206, 2nd October 1999** [link]

I was trying to construct a chain of 2-digit and 3-digit perfect squares such that each square in the chain had at least two digits in common with each of its neighbours (or with its sole neighbour, if it was at either end of the chain). If a square had a repeated digit that digit only counted more than once in calculating the number of digits that the square had in common with another square if it also appeared more than once in the other square; so 121 had only one digit in common with 100, but 100 had two [digits] in common with 400.

I found that I could construct three totally different chains each consisting of at least five squares; and I made each of these chains as long as possible, consistent with the stipulation that no square should be used more than once. But I could not link these chains into a single long chain until I used one particular 4-digit square as the means of linking one end of my first chain to one end of my second chain and also the other end of my second chain to one end of my third chain. In each place where it was used, this 4-digit square had at least two digits in common with each of its chain neighbours.

(1) Identify this 4-digit square.

(2) Which were the squares at opposite ends of the single long chain?

[enigma1050]

### Like this:

Like Loading...

I took the phrasing “I made each of these chains as long as possible …”, to mean that individually the three shorter chains cannot be extended with any of the 2,3-digit squares that do not already occur in the chain. This let me build a list of “unextendable” chains, and I could then choose three of them that do not share any numbers and do not fit together to form a composite chain, but can be formed into a composite chain with the same 4-digit square link interposed between them.

This Python 3 program runs in 5.9s.

Run:[ @repl.it ]Solution:(1) The 4-digit square is 1849; (2) The squares at the end of the long chain are 36 and 676.The composite chain uses 21 of the available 24 possible 2,3-digit squares (the remaining 4 squares – 49, 64, 121, 324 – cannot be linked to any other squares, so can’t appear in a chain).

The resulting chain is not unique, but each of the shorter chains keeps the same content. Here is an example solution:

Obviously the whole chain can simply be reversed, as can just the central short chain. But also numbers with the same digit content can be interchanged. So in the left chain we have (169, 196, 961) any of the three can appear in any of the corresponding positions. In the middle chain we have (144, 441), and in the right chain we have (256, 625).

In the left chain (16-169-196-961) all link together with 1 and 6, so the numbers can appear in any order (but 16 cannot occur at the end as a 9 is needed to link to 1849).

Similarly the right chain has (25-225-256-625) which all have 2 and 5 in common.

Also the middle chain can be split into (144-441-484-784)-(841-81), and the first part of this chain can be reversed, as 784 also links with 1849.

Altogether I think that makes 3456 possible composite solution chains.

Fortunately the numbers at the non-attached ends of the composite chain are unique by digit content, so whatever chains we use there will always be 36 at one end of the composite chain and 676 at the other end. (In the program I order the chains so the number on the left unattached end is smaller than the number on the right unattached end (when the numbers are considered as strings)).

We can make composite chains that use 20 of the available squares and are linked with 1089, 1764, 1849, 4761, 8649, 9801. But 1849 is the only linking square that gives a composite chain that uses 21 squares.

It wasn’t until I drew out a diagram of the graph showing the links between the 2-,3- digit squares that I realised that they form distinct clusters that cannot link outside themselves.

Each of (49), (64), (121) and (324) forms their own singleton cluster (my program above removes these from consideration, as they can’t link to any other squares) and (100, 400, 900) form a cluster of size 3, so that too can be discarded, as we can’t form a chain with at least 5 elements from it.

The remaining clusters are:

Now the part of the puzzle text that talks about making the three chains as long as possible makes sense. For each of these three clusters we can make chains that include all elements of the cluster.

In fact for each cluster there are only a few possible maximal length chains that can be constructed. And in each cluster there is an element that only links to one other element (36, 81, 676), so they must appear at one end of each maximal chain.

By examining how these end numbers can link to the 4-digit squares it becomes apparent that there is only one cluster that can form the middle of the composite chain, and then we can find suitable ends from the maximal paths of the remaining clusters to complete a composite chain.

The following Python program forms the clusters the 2-,3-digit squares and the proceeds to find composite chains. It runs in 95ms.

@Jim. That is a neat trick around lines 38 to 44 to cut down the number of chains that need to be considered. The running time of my first version, without this, was measured in minutes. After adopting your trick, but using only the length of the sequence rather than its content to eliminate ‘duplicates’, my run time is now less than half a second on my machine.