Puzzle - RPL and others
05-10-2021, 03:57 AM
Post: #35
 Albert Chan Senior Member Posts: 2,686 Joined: Jul 2018
RE: Puzzle - RPL and others
(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.

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
...
 « Next Oldest | Next Newest »

 Messages In This Thread Puzzle - RPL and others - Gene - 04-22-2021, 06:55 PM RE: Puzzle - RPL and others - Valentin Albillo - 04-22-2021, 11:52 PM RE: Puzzle - RPL and others - rprosperi - 04-23-2021, 04:21 PM RE: Puzzle - RPL and others - EdS2 - 04-23-2021, 07:30 AM RE: Puzzle - RPL and others - Dave Britten - 04-23-2021, 12:06 PM RE: Puzzle - RPL and others - 3298 - 04-23-2021, 09:17 AM RE: Puzzle - RPL and others - ijabbott - 04-23-2021, 03:57 PM RE: Puzzle - RPL and others - Albert Chan - 04-23-2021, 04:08 PM RE: Puzzle - RPL and others - Albert Chan - 04-27-2021, 12:14 PM RE: Puzzle - RPL and others - Didier Lachieze - 04-23-2021, 04:23 PM RE: Puzzle - RPL and others - 3298 - 04-23-2021, 09:05 PM RE: Puzzle - RPL and others - C.Ret - 04-24-2021, 04:40 PM RE: Puzzle - RPL and others - C.Ret - 04-25-2021, 09:25 AM RE: Puzzle - RPL and others - Claudio L. - 04-26-2021, 04:56 PM RE: Puzzle - RPL and others - 3298 - 04-27-2021, 08:16 PM RE: Puzzle - RPL and others - Albert Chan - 04-28-2021, 02:33 AM RE: Puzzle - RPL and others - Albert Chan - 04-28-2021, 03:30 AM RE: Puzzle - RPL and others - 3298 - 04-28-2021, 10:14 PM RE: Puzzle - RPL and others - Albert Chan - 04-29-2021, 03:25 AM RE: Puzzle - RPL and others - Allen - 04-28-2021, 08:45 PM RE: Puzzle - RPL and others - Albert Chan - 04-29-2021, 05:16 PM RE: Puzzle - RPL and others - Allen - 04-29-2021, 07:03 PM RE: Puzzle - RPL and others - C.Ret - 05-02-2021, 06:40 AM RE: Puzzle - RPL and others - 3298 - 05-03-2021, 03:43 PM RE: Puzzle - RPL and others - Albert Chan - 05-04-2021, 03:29 AM RE: Puzzle - RPL and others - 3298 - 05-04-2021, 06:48 AM RE: Puzzle - RPL and others - Albert Chan - 05-05-2021, 06:29 PM RE: Puzzle - RPL and others - 3298 - 05-06-2021, 04:24 PM RE: Puzzle - RPL and others - Albert Chan - 05-06-2021, 09:09 PM RE: Puzzle - RPL and others - Albert Chan - 05-07-2021, 10:35 AM RE: Puzzle - RPL and others - 3298 - 05-07-2021, 04:17 PM RE: Puzzle - RPL and others - Albert Chan - 05-09-2021, 01:21 AM RE: Puzzle - RPL and others - 3298 - 05-09-2021, 01:39 PM RE: Puzzle - RPL and others - Albert Chan - 05-10-2021 03:57 AM RE: Puzzle - RPL and others - Albert Chan - 05-07-2021, 02:56 AM RE: Puzzle - RPL and others - Albert Chan - 05-10-2021, 05:13 PM RE: Puzzle - RPL and others - 3298 - 05-10-2021, 08:23 PM RE: Puzzle - RPL and others - Albert Chan - 05-11-2021, 11:58 AM RE: Puzzle - RPL and others - 3298 - 05-11-2021, 02:14 PM RE: Puzzle - RPL and others - John Keith - 05-11-2021, 03:55 PM RE: Puzzle - RPL and others - ijabbott - 05-11-2021, 10:37 PM RE: Puzzle - RPL and others - Albert Chan - 05-13-2021, 11:38 PM

User(s) browsing this thread: 1 Guest(s)