Puzzle - RPL and others
05-04-2021, 03:29 AM
Post: #25
 Albert Chan Senior Member Posts: 2,686 Joined: Jul 2018
RE: Puzzle - RPL and others
(05-03-2021 03:43 PM)3298 Wrote:  ... a staggering 1304_s (over 21 minutes!) for base 22, which does not benefit from it at all beyond
the simple odd/even and ==base/2 checks. Good ol' base 10 takes just under 2.5 seconds.

There is also a mod-4 bucket, for even base n:

n = 4k: ﻿ ﻿ ﻿ ﻿ d4 ≡ d8 ≡ ... ≡ d4k ≡ 0 (mod 4) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ → d2 ≡ d6 ≡ ... ≡ d4k-2 ≡ 2 (mod 4)
n = 4k+2: d4 ≡ d8 ≡ ... ≡ d4k ≡ 2 (mod 4) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ → d2 ≡ d6 ≡ ... ≡ d4k+2 ≡ 0 (mod 4)

Combined, we have the invariant: (n + 2i + d2i) ≡ 0 (mod 4)

Code:
def recurse3(lst, n, k=1, x=0):     if k==n: print x; return     x, d0, step = n*x, lst[k], k+k     d1 = k-x%k  # first valid (mod k)     if k&1:     # odd k         if not (d1&1): d1 += k  # d1 also odd     elif k==2:         d1 = 4 if (n&3) else 2     else:       # even k >= 4         bad = (n+k-d1) & 3         if k&3: d1 += bad and k # d1 (mod4) = n+k         elif bad: return        # can't fix by +k         else: step = k          # step (mod4) = 0     for d in xrange(d1, n, step):         try: i = lst.index(d,k)         except ValueError: continue         lst[i] = d0         recurse3(lst, n, k+1, x+d)         lst[i] = d      # restore

>>> recurse3(range(10), 10)
381654729

With this, I confirmed there is no solution for 16 ≤ n ≤ 40
 « 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)