Le Monde puzzle [#754]

The 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()}
 }
 }
 }

Still 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)
 }

Le 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

Of 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…