Le Monde puzzle [#840]

November 22, 2013
By

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

Another number theory Le Monde mathematical puzzles:

Find 2≤n≤50 such that the sequence {1,…,n} can be permuted into a sequence such that the sum of two consecutive terms is a prime number. 

Now this is a problem with an R code solution:

library(pracma)
foundsol=TRUE
N=2
while (foundsol){

  N=N+1
  noseq=TRUE
  uplim=10^6
  t=0
  while ((t<uplim)&&(noseq)){

    randseq=sample(1:N)
    sumseq=randseq[-1]+randseq[-N]
    noseq=min(isprime(sumseq))==0
    t=t+1
    }

  foundsol=!noseq
  if (!noseq){
   lastsol=randseq}else{ N=N-1}
  }

which returns the solution as

> N
[1] 12
> lastsol
 [1]  6  7 12 11  8  5  2  1  4  3 10  9

and so it seems there is no solution beyond N=12…

However, reading the solution in the next edition of Le Monde, the authors claim there are solutions up to 50. I wonder why the crude search above fails so suddenly, between 12 and 13! So instead I tried a recursive program that exploits the fact that subchains are also verifying  the same property:

findord=function(ens){

  if (length(ens)==2){
    sol=ens
    foundsol=isprime(sum(ens))}
  else{
    but=sample(ens,1)
    nut=findord(ens[ens!=but])
    foundsol=FALSE
    sol=ens
    if (nut$find){
      tut=nut$ord
      foundsol=max(isprime(but+tut[1]),
         isprime(but+tut[length(tut)]))
      sol=c(tut,but)
      if (isprime(but+tut[1]))
         sol=c(but,tut)
      }
  }
  list(find=foundsol,ord=sol)
}

And I ran the R code for N=13,14,…

> stop=TRUE
> while (stop){
+   a=findord(1:N)
+   stop=!(a$find)}

until I reached N=20 for which the R code would not return a solution. Maybe the next step would be to store solutions in N before moving to N+1. This is just getting  me too far from a mere Saturday afternoon break.


Filed under: Books, Kids, R Tagged: Le Monde, mathematical puzzle, pracma, prime numbers, R

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...

Comments are closed.