## Le Monde puzzle [#814]

**T**he #814 Le Monde math puzzle was to find 100 digits (between 1 and 10) such that their sum is equal to their product. Given the ten possible values of those digits, this is equivalent to finding integers a_{1},…,a_{10} such that

a_{1}+…+a_{10}=100

and

a_{1}+2a_{2}+…+10a_{10}=2^{a2}x….x10^{a10},

which reduces the number of unknowns from 100 to 10 (or even 9). Furthermore, the fact that the (first) sum of the a_{i}‘s is less than 100 implies that the (second) sum of the *ia _{i}*‘s is less than 1000, hence

*i*is less than 1000. This reduces the number of possible ten-uplets enough to allow for an enumeration, hence the following R code:

^{ai}bounds=c(100,trunc(log(1000)/log(2:10))) for (i2 in 0:bounds[2]) for (i3 in 0:bounds[3]) for (i4 in 0:bounds[4]) for (i5 in 0:bounds[5]) for (i6 in 0:bounds[6]) for (i7 in 0:bounds[7]) for (i8 in 0:bounds[8]) for (i9 in 0:bounds[9]) for (i10 in 0:bounds[10]){ A=c(i2,i3,i4,i5,i6,i7,i8,i9,i10) if (sum(A)<101){ A=c(100-sum(A),A) if (sum((1:10)*A)==prod((1:10)^A)) print(A) }}

that produces two answers

[1] 97 0 0 2 0 0 1 0 0 0 [1] 95 2 3 0 0 0 0 0 0 0

i.e. either 97 1’s, 2 4’s and 1 7, or 95 1’s, 2 2’s and 3 3’s. I would actually love to see a coding solution that does not involve this pedestrian pile of “for”. And a mathematical solution based on Diophantine equations. Rather than the equally pedestrian solution given by Le Monde this weekend.

April 2, 2013 at 7:06 pm

You can use recursion to get rid of the big pile of for loops – each call to the recursive function steps through one level of the loop. It is much slower, however.

April 2, 2013 at 8:25 pm

Thanks, Martyn. I was wondering whether a list could help, instead…