**A**s mentioned in the previous post, an alternative consists in finding the permutation of {1,…,N} by “adding” squares left and right until the permutation is complete or no solution is available. While this sounds like the dual of the initial solution, it brings a considerable improvement in computing time, as shown below. I thus redefined the construction of the solution by initialising the permutation at random (it could start at 1 just as well)

perfect=(1:trunc(sqrt(2*N)))^2 perm=friends=(1:N) t=1 perm[t]=sample(friends,1) friends=friends[friends!=perm[t]]

and then completing only with possible neighbours, left

out=outer(perfect-perm[t],friends,"==") if (max(out)==1){ t=t+1 perm[t]=sample(rep(perfect[apply(out,1, max)==1],2),1)-perm[t-1] friends=friends[friends!=perm[t]]}

or right

out=outer(perfect-perm[1],friends,"==") if (max(out)==1){ t=t+1 perf=sample(rep(perfect[apply(out,1, max)==1],2),1)-perm[1] perm[1:t]=c(perf,perm[1:(t-1)]) friends=friends[friends!=perf]}

(If you wonder about why the *rep* in the *sample* step, it is a trick I just found to avoid the insufferable feature that sample(n,1) is equivalent to sample(1:n,1)! It costs basically nothing but bypasses reprogramming sample() each time I use it… I am very glad I found this trick!) The gain in computing time is amazing:

> system.time(for (i in 1:50) pick(15)) utilisateur système écoulé 5.397 0.000 5.395 > system.time(for (i in 1:50) puck(15)) utilisateur système écoulé 0.285 0.000 0.287

An unrelated point is that a more interesting (?) alternative problem consists in adding a toroidal constraint, namely to have the first and the last entries in the permutation to also sum up to a perfect square. Is it at all possible?