# Le Monde puzzle [#754]

December 25, 2011
By

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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…

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Tags: , , , ,