## Teaser 3047: Some permutations

**From The Sunday Times, 14th February 2021** [link]

I gave Robbie three different, non-zero digits and asked him to add up all the different three-digit permutations he could make from them. As a check for him, I said that there should be three 3’s in his total. I then added two more [non-zero] digits to the [original three digits] to make [a set of] five digits, all being different, and asked Robbie’s mother to add up all the possible five-digit permutations of these digits. Again, as a check, I told her that the total should include five 6’s.

Given the above, the product of the five digits was as small as possible.

What, in ascending order, are the five digits?

I have changed the text of this puzzle slightly to make it clearer.

[teaser3047]

## Jim Randell 5:10 pm

on12 February 2021 Permalink |(See also:

Teaser 2863).This Python program runs in 64ms.

Run:[ @repl.it ]Solution:The five digits are: 1, 2, 5, 8, 9.There are two scenarios with a minimal product of 720:

The sum of all 3-digit permutations is 3330 (= 222 × 15).

The sum of all 5-digit permutations is 6666600 = (266664 × 25).

In total there are 16 candidate solutions, each with the same sums for the 3-digit and 5-digit permutations.

In general, if we have a set of

kdifferent digits, then they can be rearranged infactorial(k)different ways, to form different numbers.And when these numbers are summed, each digit will appear

factorial(k) / k = factorial(k – 1)times in each column.So we can calculate the total of all permutations without having to generate them all:

In particular, for 3-digit numbers this simplifies to [[

`222 * sum(ds)`

]] and for 5-digit numbers it simplifies to [[`266664 * sum(ds)`

]].The program above can be adapted using this analysis to give a solution with a run time of 51ms:

LikeLike

## Tony Brooke-Taylor 3:11 pm

on13 February 2021 Permalink |I think it is possible to simplify the problem to a point where the solution can be found manually. I admit I only spotted the simplifications once I had written an algorithm similar to yours Jim.

In the 3-digit problem we can work out manually what the total must be: there is only one multiple of 222 that has three 3’s in it. Eight sets of three digits sum to the correct cofactor, of which four are symmetrical around the value 5.

In the 5-digit problem we can also work out what the total must be: there is only one multiple of 266664 that has five 6’s in it, and I believe this is more obvious if we look at multiples of 11111. Thus we have a unique cofactor in this problem too, and the sum of the extra two digits must be the difference between the two cofactors. Only four pairs of digits make up this sum.

If we combine the four pairs with the eight trios and deduplicate, we get ten possible sets of 5, of which six are symmetrical around the value 5.

By trigonometry, the solution with the minimum product has the greatest distances between the central number and the others. My leap of faith is that we could also have applied this at the 3-digit stage to reduce the number of trios we needed to test.

LikeLike

## Jim Randell 12:07 pm

on17 February 2021 Permalink |@Tony: Once we’ve got the 8 pairs of triples that sum to 15, and we are extending them with a pair that sums to 10 (= (1,9) (2,8) (3, 7) (4,6)), then we only need to consider the first viable pair, as later ones will give a larger product.

So we can exhaustively check the solution space by calculating only 7 products.

Here’s some code that uses this analysis:

LikeLike

## Frits 10:31 am

on15 February 2021 Permalink |@Jim,

If you replace line 23 “t5 = psum(ds5) ” with

your code is approx. 4.5 times faster (with Python 3.9.0).

Maybe nconcat is not efficient if called multiple times?

Subsets only seems to have minor overhead.

LikeLike

## Jim Randell 12:40 pm

on15 February 2021 Permalink |@Frits: In a program that runs pretty much instantaneously I am less concerned about coding for execution speed as I am that the program itself should be concise, clear and easy to modify (and, above all, correct).

So using a general utility function like [[

`nconcat()`

]] makes it clear that I am turning a sequence of digits into a number, even if it is not the fastest way to achieve this.Although with a bit of analysis we find that we don’t have to construct numbers corresponding to all the permutations of the digits in order to arrive at the sum (and gives a general principle for attacking similar problems), which lets us write a program that runs even faster.

But that is not to say I’m not at all interested in execution speed. I’ll have a look at improving [[

`nconcat()`

]], and another advantage of using utility functions is that if an improvement is made, every program that uses them gets the benefit.LikeLike

## Frits 11:23 am

on13 February 2021 Permalink |Basic version, not really optimized for speed.

LikeLike

## Frits 2:07 pm

on18 February 2021 Permalink |Partly based on Tony’s comments.

LikeLike