Le Monde puzzle [#814]

The #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 a1,…,a10 such that

a1+…+a10=100

and

a1+2a2+…+10a10=2a2x….x10a10,

which reduces the number of unknowns from 100 to 10 (or even 9). Furthermore, the fact that the (first) sum of the ai‘s is less than 100 implies that the (second) sum of the iai‘s is less than 1000, hence iai is less than 1000. This reduces the number of possible ten-uplets enough to allow for an enumeration,  hence the following R code:

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.

2 Responses to “Le Monde puzzle [#814]”

  1. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 551 other followers