Archive for Diophantine equations

Le Monde puzzle [#814]

Posted in Books, Kids, R with tags , , , on April 2, 2013 by xi'an

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.

Follow

Get every new post delivered to your Inbox.

Join 705 other followers