问满足给定约束的有效序列数

EN

for i in range 2 to n:
for j in range 1 to 6:
for k in range 1 to 6
if j and k are not coprime, dp[i][j][k] = 0 
else, dp[i][j][k] = summation(dp[i-1][k][l]) where l is in range [1,6] AND l!=j and j!=k
# this ensures a min gap of 3 and maintains co-primality of adjacent numbers

def count_seq(N):
  A = range(1, 7)
  dp = [[[None] * 7 for _ in range(7)] for _ in range(N+1)]
  for j in A:
    for k in A:
      dp[0][j][k] = 0
      dp[1][j][k] = 0
      dp[2][j][k] = int(gcd(j,k)==1 and j!=k)
  for i in range(3, N+1):
    for j in A:
      for k in A:
        if gcd(j, k) != 1:
          dp[i][j][k] = 0 
        else:
          dp[i][j][k] = sum(dp[i-1][k][l] for l in A if (l!=j and j!=k))
  return sum(dp[N][j][k] for j in A for k in A)

N = 100
print(count_seq(N))

number_set = [1, 2, 3, 4, 5, 6]

forbidden_tuples = {(2,4), (2,6), (4,6), (3,6), (4,2), (6,2), (6,4), (6,3)}

import itertools

def count_seq(N, start_state=None, memoization=None):
    """
    :param N:
    :param start_state
    :param memoization
    :return: Rules:
    1. a_i in {1,2,3,4,5,6}
    2. Two adjacent numbers should be coprime. For e.g. 2,4,.. sequence is not allowed ( for the set {1,2,3,4,5,6} this means that (2,6),(2,4),(3,6),(4,6) are forbidden
    3. repetitions with a distance >= 2

    State are ordered as a 2 item tuple to remember the history: (a_{n-1} , a_n)
    """
    if N == 1:
        return 6
    if memoization is None:
        memoization = {}
    count = 0
    state_set = set()  # Pending states which have not been explored yet
    number_set = [1, 2, 3, 4, 5, 6]
    forbidden_tuples = {(2,4), (2,6), (4,6), (3,6), (4,2), (6,2), (6,4), (6,3)}
    if start_state is None: # Getting initial states
        for subset in itertools.permutations(number_set, 2):
            if subset in forbidden_tuples:
                pass
            else:
                state_set.add((subset, N))
    else:  # checking all possible next states and appending to queue with 1 less length
        for ii in number_set:
            if ii in start_state or (ii, start_state[-1]) in forbidden_tuples:
                pass
            else:
                state_set.add(((start_state[1:] + tuple([ii])), N-1))
    # for each possible next state
    for state in state_set:
        if state[1] <= 2:
            count += 1
        elif state in memoization:  # checking if we computed this already
            count += memoization[state]
        else:  #we did not compute this, doing the computation
            memoization[state] = count_seq(state[1], state[0], memoization)
            count +=  memoization[state]

    return count

%timeit count_seq_slow(200)
199 ms ± 9.63 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit count_seq(200)
13.6 ms ± 833 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit count_seq_slow(2000)
3.54 s ± 374 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit count_seq(2000)
147 ms ± 7.02 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

K[n, d1, d2] = 0 if d1=d2 or d1 is not coprime to d2.
K[0, d1, d2] = 1
K[n, d1, d2] = sum(K[n-1, d2, d] for d=1..6 - {d1, d2})

S[n] = sum(K[n-2, d1, d2] for d1=1..6, d2=1..6)

from math import gcd

def S(n):
    if n == 0: return 1
    if n == 1: return 6
    K = [d1!=d2 and gcd(d1+1, d2+1)==1 for d1 in range(6) for d2 in range(6)]
    for _ in range(n-2):
        K = [0 if d1==d2 or gcd(d1+1, d2+1)!=1 else sum(K[d2*6+d] for d in range(6) if d!= d1 and d!=d2) for d1 in range(6) for d2 in range(6)]
    return sum(K)