Puzzle - RPL and others

[Albert Chan]

(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:     d₄ ≡ d₈ ≡ ... ≡ d_4k ≡ 0 (mod 4)       → d₂ ≡ d₆ ≡ ... ≡ d_4k-2 ≡ 2 (mod 4)
n = 4k+2: d₄ ≡ d₈ ≡ ... ≡ d_4k ≡ 2 (mod 4)       → d₂ ≡ d₆ ≡ ... ≡ d_4k+2 ≡ 0 (mod 4)

Combined, we have the invariant: (n + 2i + d_2i) ≡ 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