### Random Post

### Recent Posts

### Recent Comments

Jim Randell on Enigma 457: Divided by ex… | |

geoffrounce on Puzzle 44: Men-only Mews | |

Jim Randell on Puzzle 44: Men-only Mews | |

Brian Gladman on Enigma 1053: Home truths | |

Jim Randell on Enigma 1053: Home truths |

### Archives

### Categories

- article (11)
- enigma (1,192)
- misc (3)
- project euler (2)
- puzzle (48)
- site news (47)
- tantalizer (51)
- teaser (3)

### Site Stats

- 186,589 hits

Advertisements

This is a directed search that starts from the observation that the numbers in the centre 4 squares are used in 4 products each and so are likely to be larger numbers, likewise the numbers in the 4 corner squares are only used in two products, so are likely to be smaller. (The remaining 8 edge squares are used in 3 products). It considers possible arrangements of the centre squares and calculates an upper bound for product sum that can be made using the remaining squares, if this is less than the best measure we’ve already found this arrangement is skipped.

It takes 28.2s to run to completion. Without the upper bound pruning I think it would take around 14 days to run to completion (although it does find the maximum solution in under 1s).

Solution:The maximum possible product sum is 2345.Here’s a diagram of the arrangement:

Labelling the squares a0,…a15, across then down, and colouring them as in a chessboard, if all the black squares, a0,a2,a5,a7,a8,a10,a13,a15 are populated, we can deduce the maximum product-sum possible by populating the white squares with the remaining numbers by using the rearrangement inequality.

This program considers permutations of numbers populating the black squares, eliminating reflections, and eliminating permutations where the black squares total more than the white squares. It still runs slower than Jim’s version, about 3 minutes under PyPy.

Some optimisation gets the run time down to 46 sec