Puzzle - RPL and others
05-07-2021, 10:35 AM (This post was last modified: 05-09-2021 02:08 PM by Albert Chan.)
Post: #31
 Albert Chan Senior Member Posts: 2,686 Joined: Jul 2018
RE: Puzzle - RPL and others
(05-06-2021 09:09 PM)Albert Chan Wrote:  Combined, we have invariant: coprime(n,k) = coprime(n,dk)

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.
 « 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)