Puzzle - RPL and others

[Albert Chan]

(05-06-2021 09:09 PM)Albert Chan Wrote:  Combined, we have invariant: coprime(n,k) = coprime(n,d_k)

I was being stupid ... test for coprime is same as test for gcd = 1
And, for gcd ≠ 1, it is the buckets that we are after.

Since test for bucket n/2 is same as matching gcd = n/2, we can remove it.
Hopefully, this is my final version, by removing stuff from recurse5() / puzzle5().

Code:

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

function puzzle(n)
    if n%2 ~= 0 then return end -- n must be even
    local lst = {}
    for i=1,n do lst[i] = i end
    for i=1,n do lst[n+i] = gcd(n,i) end
    return recurse(lst, n, 1, {})
end

function recurse(lst, n, k, X)
    if k==n then return print('{'..table.concat(X,',')..'}') end
    local d, step, s = 0, k+k, k%4
    for i=1, k-6, 6 do          -- assume n <= 190
        d = ((((((d*n + X[i])*n + X[i+1])*n + X[i+2])*n
                    + X[i+3])*n + X[i+4])*n + X[i+5]) % k
    end
    for i = k-(k-1)%6, k-1 do d = d*n + X[i] end        
    d = k - d*n%k               -- first valid (mod k)

    if s == 0 then              -- k = step = 0 (mod 4)
        step = k
    elseif s ~= 2 then          -- k = d = 1 (mod 2)
        if d%2==0 then d=d+k end
    elseif (n+d)%4 == 0 then    -- n+d+k = 0 (mod 4)
        d = d+k
    end
    
    s = lst[n+k]                -- = gcd(n,k)
    while d < n do
        if lst[d] and lst[n+d] == s then
            X[k] = d
            lst[d] = false      -- mark taken
            recurse(lst, n, k+1, X)
            lst[d] = d          -- restore
        end
        d = d + step
    end
end
end

(05-07-2021 02:56 AM)Albert Chan Wrote:  I have confirmed n=60 has no solution ... in an hour.

Updated version finished in 4½ minutes.

Update1: add a simple test to quit if n is odd.
Update2: unroll loops to reduce expensive mod's, this finish n=60 case in 3 minutes.
The downside is n^7 ≤ 2^53 ⇒ n ≤ 190, which should be plenty enough.