## Le Monde puzzle [#754]

**T**he pre-X’mas puzzle in Le Monde weekend edition is about “magical numbers” having as digits all digits between 0 and n (at least once) and being multiple of all digits between 1 and (n+1). Easy, isn’t it?! I thought so while driving down to the Alps on Saturday and (on Monday early morning) I tried a brute force solution

magi=function(n){ prdct=prod(1:(n+1)) for (t in 1:10^6){ num=sum(sample(0:n)*10^(0:n)) if (num==prdct*trunc(num/prdct)){ print(num) break()} } }

which worked for n=2,3, but failed for n=4. Maybe too brute-force? So I imposed the basic divisibility by 2×5=10 from the start, namely the last digit had to be 0:

magi=function(n){ prdct=prod(1:(n+1)) if (n>3){ for (t in 1:10^6){ num=sum(sample(0:n)*10^(0:n)) if (num==prdct*trunc(num/prdct)){ print(num) break()} } }else{ for (t in 1:10^6){ num=10*sum(sample(1:n)*10^(0:(n-1))) if (num==prdct*trunc(num/prdct)){ print(num) break()} } } }

**S**till did not work for n=4… Actually, there was a mistake in prdct in both of the above, in that the solution number only needs to be divided by the largest powers to the prime numbers between 2 and n+1, as implemented below.

**I** thought a wee more on the conditions and realised that any random permutation of the digits {1,…,4} could not be divided by 3, since their sum is 10. Therefore, the solution for n=4 must have at least 6 digits. This led me to a more general R function which works for the cases n=4,5,6 and has a second parameter, k, namely the number of digits in the proposed solution. It also includes imposing a correct second digit based on the divisibility by 4:

magi456=function(n,k){ proo=3*4*5*(1+6*(n==6)) #only required divisors digi=10^(0:(k+1)) sol=rep(9,k+2)*digi for (t in 1:10^6){ a0=0 #multiple of 2*5 a1=sample(2*(1:trunc(n/2)),1) #multiple of 4 b=sample((1:n)[-a1]) #all other integers b=sample(c(b,sample(0:n,(k-n+1),rep=TRUE))) a=sum(c(a0,a1,b)*digi) if (a%%proo==0){ sol=a print(a) break() } } return(sol) }

**A** similar solution can be proposed for the cases n=7,8,9, with a different constraint on the three first digits due to the divisibility by 8. There again is a special case when n=7, since the sum of all integers from 1 to 7 is 28, not divisible by 3. On the other hand, the sum of all integers from 1 to 8 is 36 and the sum of all integers from 1 to 9 is 45, both divisible by 9. Here is the corresponding R code:

magi789=function(n,k){ proo=(1+2*(n==7))*5*7*8*(1+8*(n>7)) #only required divisors digi=10^(0:(k+1)) sol=rep(9,k+2)*digi for (t in 1:10^6){ a0=0 #multiple of 2*5 #multiple of 8 (4, 2) a1=sample(2*(1:trunc(n/2)),1) a2=sample((1:n)[-a1],1) while ((a1+2*a2)%%4!=0){ a1=sample(2*(1:trunc(n/2)),1) a2=sample((1:n)[-a1],1) } b=sample((1:n)[-c(a1,a2)]) #all other integers b=sample(c(b,sample(0:n,(k-n+1),rep=TRUE))) a=sum(c(a0,a1,a2,b)*digi) if (a%%proo==0){ sol=a print(a) break() } } return(sol) }

**L**e Monde was furthermore asking for the smallest solution for each n. I ran the R code a few thousand times for every n and obtained

> magi456(4,4) 122340 > magi456(5,4) 123540 > magi456(6,5) 1235640 > magi789(7,7) 122437560 > magi789(8,7) 123487560 > magi789(9,8) 1234759680

**O**f course, these are upper bounds on the smallest solutions (and there are more clever ways of R coding the above as well as of solving the puzzle in a mathematical way). Being away till Tuesday, I will not check the solution till then…

January 28, 2012 at 12:18 am

[…] Monde puzzle of last weekend was about sudoku-like […]

December 31, 2011 at 12:11 am

[…] addition to the solution to the wrong problem, Le Monde of last weekend also dedicated a full page of its Science leaflet to the coverage of […]

December 27, 2011 at 8:45 am

Funny! Le Monde published the solution to the wrong problem last weekend! Here is the solution. The approach is exhaustive as well, using in addition the constraint that numbers divisible by 7 must have the alternate sum of their block-of-three-digits divisible by 7. (I thought there was an easier check…) The smallest solution for 7 is smaller than mine’s.