Le Monde puzzle [#754]

December 25, 2011
By

(This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers)

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…


Filed under: Mountains, R, Statistics, University life Tagged: mathematical puzzle

To leave a comment for the author, please follow the link and comment on his blog: Xi'an's Og » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , , , ,

Comments are closed.