### Random Post

### Recent Posts

### Recent Comments

Jim Randell on Enigma 544a: Merry Christ… | |

Jim Randell on Puzzle #52: Bus change | |

J. Pijnenburg on Puzzle #52: Bus change | |

Jim Randell on Puzzle #53: Painting by n… | |

GeoffR on Puzzle #52: Bus change |

### Archives

### Categories

- article (11)
- enigma (1,367)
- misc (4)
- project euler (2)
- puzzle (90)
- puzzle# (48)
- site news (58)
- tantalizer (93)
- teaser (7)

### Site Stats

- 233,054 hits

This struck me as being somewhat similar to

Enigma 1536, so I attacked it in a similar way. It runs in 285ms.Solution:The sum of the set of squares is 2439.The chunking is a bit over the top – it’s much easier to compute the next square then it is the next prime, so it would be cleaner to just go up one square at a time.

Here’s some code that lets you specify the digit count pattern you are looking for, and it keeps a record of the smallest sum it’s found for each digit count as it goes along. So, to solve the original puzzle you would specify the digit count as 2222222222 (which is the default).

You can use it to determine that the minimum sum using each of the digits 0-9 three times is 6714 and using each of the digits four times the minimum sum is 12528. And (if you have the patience and the RAM) that using each of the digits five times the minimum sum is 17685.

Brian further improved this algorithm by encoding the digit count in hexadecimal, rather than decimal, and then using a neat bit of coding to check for overallocation of digits allows the elimination of superfluous intermediate results. So once the sum and largest square is found it becomes viable to re-run the algorithm with a modified digit count to find the next largest square, and so on until the required sequence of squares is determined.

Here is the result of our combined efforts:

Note that this algorithm will fail when the count of an individual digit exceeds 7, but as the algorithm is quite memory hungry it is more likely that it will run out of memory before this becomes a problem. Particularly when the program is being used to find solutions with homogeneous digit counts (such as required by the original puzzle).

After quite a bit of messing around here is what will probably be the final version of this algorithm.

This version packs the digit count into an integer using as few bits as possible, and also includes some tweaks to discard squares where the digit count exceeds the maximum digit count we are looking for. As the main routine is only interested in finding the smallest square for a specific digit count it no longer drags all the squares around, but just records the one for the digit count we’re looking for. And it provides the updates to the dictionary for each pass as a separate dictionary and merges them in at the end of the pass to ensure it doesn’t use a square twice.

It’s still however something of a memory hungry algorithm.

It takes command line arguments so you can specify the number of each digit you want to look for (e.g. as “9876543210” if you want each digit to appear its own number of times) and you can optionally specify the maximum square it should look for as a second argument.

Any of these general algorithms can also be used to provide solutions for Enigma 1518.

This one runs a bit slower, but gets the same answer as Jim

A faster version:

Here is my version:

If you’re short on time or RAM, and you have PyMathProg installed you can program up a solver to use GLPK to solve this Enigma. The following Python code (similar to my GLPK solution to

Enigma 1536) can find solutions for squares using each digit from 1 to 10 times in under 500ms.Here is a version of 1712 using the technique of my recursive solution to 1536.

This one constructs the optimal search sequence of digits in code (the sequence being the increasing frequency of the digit in the list of squares).

The performance is improved significantly by the converting the “containingsingle” and “containingdouble” entries to lists, so that smaller numbers are used first.

The program runs in about 90 ms