# Le Monde puzzle [#887]

**Xi'an's Og » R**, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)

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

**A** simple combinatorics Le Monde mathematical puzzle:

N is a golden number if the sequence {1,2,…,N} can be reordered so that the sum of any consecutive pair is a perfect square. What are the golden numbers between 1 and 25?

Indeed, from an R programming point of view, all I have to do is to go over all possible permutations of {1,2,..,N} until one works or until I have exhausted all possible permutations for a given N. However, 25!=10²⁵ is a wee bit too large… Instead, I resorted once again to brute force simulation, by first introducing possible neighbours of the integers

perfect=(1:trunc(sqrt(2*N)))^2 friends=NULL le=1:N for (perm in 1:N){ amis=perfect[perfect>perm]-perm amis=amis[amis<N] le[perm]=length(amis) friends=c(friends,list(amis)) #,recursive=TRUE) }

and then proceeding to construct the permutation one integer at time by picking from its remaining potential neighbours until there is none left or the sequence is complete

orderin=0*(1:N) t=1 orderin[1]=sample((1:N),1) for (perm in 1:N){ friends[[perm]]=friends[[perm]] [friends[[perm]]!=orderin[1]] le[perm]=length(friends[[perm]]) } while (t<N){ if (length(friends[[orderin[t]]])==0) break() if (length(friends[[orderin[t]]])>1){ orderin[t+1]=sample(friends[[orderin[t]]],1)}else{ orderin[t+1]=friends[[orderin[t]]] } for (perm in 1:N){ friends[[perm]]=friends[[perm]] [friends[[perm]]!=orderin[t+1]] le[perm]=length(friends[[perm]]) } t=t+1}

and then repeating this attempt until a full sequence is produced or a certain number of failed attempts has been reached. I gained in efficiency by proposing a second completion on the left of the first integer once a break occurs:

while (t<N){ if (length(friends[[orderin[1]]])==0) break() orderin[2:(t+1)]=orderin[1:t] if (length(friends[[orderin[2]]])>1){ orderin[1]=sample(friends[[orderin[2]]],1)}else{ orderin[1]=friends[[orderin[2]]] } for (perm in 1:N){ friends[[perm]]=friends[[perm]] [friends[[perm]]!=orderin[1]] le[perm]=length(friends[[perm]]) } t=t+1}

(An alternative would have been to complete left and right by squared taken at random…) The result of running this program showed there exist permutations with the above property for N=15,16,17,23,25,26,…,49. Here is the solution for N=49:

25 39 10 26 38 43 21 4 32 49 15 34 30 6 3 22 42 7 9 27 37 12 13 23 41 40 24 1 8 28 36 45 19 17 47 2 14 11 5 44 20 29 35 46 18 31 33 16 48

As an aside, the authors of Le Monde puzzle pretended (in Tuesday, Nov. 12, edition) that there was no solution for N=23, while this sequence

22 3 1 8 17 19 6 10 15 21 4 12 13 23 2 14 11 5 20 16 9 7 18/p>

sounds fine enough to me… I more generally wonder at the general principle behind the existence of such sequences. It sounds quite probable that they exist for N>24. (The solution does not bring any light on this issue.)

Filed under: Books, Kids, R, Statistics Tagged: Le Monde, mathematical puzzle, perfect square, R

**leave a comment**for the author, please follow the link and comment on their blog:

**Xi'an's Og » R**.

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.