Puzzle - RPL and others

[Albert Chan]

(05-05-2021 06:29 PM)Albert Chan Wrote:  With this, I confirmed there is no solution for 16 ≤ n ≤ 44
Interestingly, it take less time to run n=42, than n=40

I found out the reason n=42 take less time than n=40. Think non-buckets.

Example, first digit does not belong to any buckets.

>>> n = 10 # = 2 * 5
>>> sorted(set(range(1,n)) - set(range(2,n,2)) - set(range(5,n,5)))
[1, 3, 7, 9]

>>> n = 40 # = 2**3 * 5
>>> sorted(set(range(1,n)) - set(range(2,n,2)) - set(range(5,n,5)))
[1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39]

>>> n = 42 # = 2 * 3 * 7
>>> sorted(set(range(1,n)) - set(range(2,n,2)) - set(range(3,n,3)) - set(range(7,n,7)))
[1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41]

This is the set of digits for d₁, and n=42 has less elements than n=40.
(looping anything else is just a waste of time)

And, this set applied not just d₁, but any d_k that is coprime to n.
Conversely, if k is not coprime to n, d_k must not be above sets of values.

Combined, we have invariant: coprime(n,k) = coprime(n,d_k)

Code:

from euclid import gcd

def puzzle5(n):
    lst = range(n)  # assume even n
    lst[n//2] = 0   # skip center
    return recurse5(lst + [gcd(n,d)==1 for d in lst], n)

def recurse5(lst, n, k=1, x=0):
    if k==n: print x; return
    if k+k==n: x=n*x+k; k+=1    # skip center
    x, step = n*x, 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):
        if not lst[d]: continue
        if lst[n+d] != lst[n+k]: continue
        lst[d] = 0              # mark taken
        recurse5(lst, n, k+1, x+d)
        lst[d] = d              # restore

I doubled up lst for 2 purpose. (lst combined to reduce stress of arguments passing)
First half is to check duplicates, like before.
Second half holds coprime(n,d) table: lst[n+d] ≡ coprime(n,d)

Coprime test benefited if base n has many different factors.

Code:

       time (sec), on my Toshiba A665 laptop
n      puzzle4(n)  puzzle5(n)
32     2           2
34     8           9
36     11          3
38     55          60
40     114         46
42     110         31
44     843         590