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.