Puzzle - RPL and others

[Albert Chan]

Previous post Python code, translated to Lua.
Since Lua does not have infinite precision integer built-in, I just loop the digits for MOD.

As expected, speed improved quite a bit, about 5X. (LuaJIT 1.1.8)
I have confirmed n=60 has no solution ... in an hour.

Code:

do
local gcd, recurse5 = require 'factor'.gcd

function puzzle5(n)
    local lst = {}
    for i=1,n do lst[i] = i end
    for i=1,n do lst[n+i] = (gcd(n,i) == 1) end
    lst[floor(n/2)] = false     -- skip center
    return recurse5(lst, n, 1, {})
end

function recurse5(lst, n, k, X)   
    if k==n then return print(table.concat(X,',')) end
    if k+k==n then X[k]=k; k=k+1 end -- skip center
    local d, step = 0, k+k
    for i=1,k-1 do d = (d*n + X[i]) % k end
    d = k - d*n%k               -- first valid (mod k)
    if k%2~=0 then              -- k is odd -> d odd too
        if d%2==0 then d = d+k end
    elseif k==2 then            -- mod4 restricted
        d = (n%4~=0) and 4 or 2
    else
        local bad = ((n+k-d)%4 ~= 0)
        if k%4 ~= 0 then if bad then d=d+k end
        elseif bad  then return -- can't fix by +k
        else step = k           -- step = 0 (mod4)
        end       
    end
    while d < n do
        if lst[d] and lst[n+d] == lst[n+k] then
            X[k] = d            
            lst[d] = false      -- mark taken     
            recurse5(lst, n, k+1, X)
            lst[d] = d          -- restore
        end
        d = d + step
    end
end
end

lua> puzzle5(8)
3,2,5,4,1,6,7
5,2,3,4,7,6,1
5,6,7,4,3,2,1

lua> puzzle5(10)
3,8,1,6,5,4,7,2,9

lua> puzzle5(14)
9,12,3,10,5,4,7,6,11,8,1,2,13