Le Monde puzzle [#754]
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…
Filed under: Mountains, R, Statistics, University life Tagged: mathematical puzzle
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.