Puzzle - RPL and others

[Albert Chan]

(05-07-2021 04:17 PM)3298 Wrote:  

(05-07-2021 10:35 AM)Albert Chan Wrote:  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().

Nah, there's more to remove.
Odd/even is covered by whether the GCD is a multiple of 2 or not. So the odd/even test can go.
As hinted at in my answer to your private message, as well as in my previous code, the mod4 test on non-mod4 bases can be worked into the GCD partitioning as well. And as I found out after writing the code, it can also be generalized to higher powers of 2, more specifically to the smallest power of 2 that doesn't divide the base anymore.

Per your advise, I did just that, implemented gcd(2n,d) buckets.
Odd/even stuff all gone ...

For n=60, this smarter version finished in 53 seconds (previously at 3 minutes).

Code:

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

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

function recurse(lst, n, k, X)
    -- print(table.concat({unpack(X,1,k-1)},','))
    if k==n then return print('{'..table.concat(X,',')..'}') end
    local d = 0
    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)
    local s = lst[n+n+k]        -- = gcd(n+n,k)

    while d < n do
        if s == lst[n+d] and lst[d] then
            X[k] = d
            lst[d] = false      -- mark taken
            recurse(lst, n, k+1, X)
            lst[d] = d          -- restore
        end
        d = d + k
    end
end
end

(05-09-2021 01:39 PM)3298 Wrote:  GCD(2n,d) buckets are (new buckets from doubling n are indented further; sorting is the same):
- 1: {1 7 11 13 17 19 23 29}
- 2: {2 14 22 26}
- - 4: {4 8 16 28}
- 3: {3 9 21 27}
- 6: {6 18}
- - 12: {12 24}
- 5: {5 25}
- 10: {10}
- - 20: {20}
- 15: {15}
- 30: {} (empty because it's the base)
- - 60: {} (also empty because it's larger than the base)

Just to be sure, I peek at the iterations for n = 30, and it matched "swapped" buckets perfectly.

1
1,4
1,4,3
1,4,3,2
1,4,3,2,5
1,4,3,2,5,12
1,4,3,2,5,12,29
1,4,3,2,5,12,29,26
1,4,3,2,5,12,29,26,21
1,4,3,2,5,12,29,26,21,20
1,4,3,2,5,24
1,4,3,2,5,24,19
1,4,3,2,5,24,19,14
1,4,3,2,5,24,19,14,21
1,4,3,2,5,24,19,14,21,20
1,4,3,2,5,24,19,14,21,20,13
1,4,3,2,5,24,19,14,21,20,13,6
1,4,3,2,5,24,19,14,21,20,13,6,17
1,4,3,2,5,24,19,14,21,20,13,6,17,8
1,4,3,2,5,24,19,14,21,20,13,6,17,8,15
1,4,3,2,5,24,19,14,21,20,13,6,17,8,15,22
...