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

As mentioned in the previous post, an alternative consists in filling 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 increase in computing time, as shown below. I thus redefined the construction of the solution by initialising the permutation at random (it could be 1 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 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 used it…) The gain in computing time is amazing:

> system.time(for (i in 1:50) pick(15))
5.397       0.000       5.395
> system.time(for (i in 1:50) puck(15))
0.285       0.000       0.287


An unrelated point is that an 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?

Filed under: Kids, R, Statistics, University life Tagged: Le Monde, mathematical puzzle, sample