Number of valid sequences that satisfies given constraints

Question

The question is to find number of valid sequences (A1,A2....AN) with given constraints:

1. Value of Ai lies between 1 and 6 (1<= Ai <= 6)
2. Two adjacent numbers should be coprime. For e.g. 2,4,.. sequence is not allowed
3. If the value repeats in the sequence, then difference in their index should be greater than 2. For e.g. If K=4, (1,2,3,1) is a valid sequence while (1,3,4,3) is not a valid sequence
   Note: N is given in the problem statement.

I could only think of a backtracking solution wherein each recursive call would try all numbers from 1 to 6 for the given Ai position.
This look like more of brute force way. Could you please help with an optimal solution.

Answer 1

We can use the fact that only 6 possible digits can be used to construct numbers.

1. Consider a lookup table dp[i][j][k], which is basically count of i-digit numbers with the i-th digit as j, (i-1)th digit as k.
2. Create a mapping of all valid co-primes for each digit. Something like {2: [1,3,5], 3: [1,2,4,5], 6: [1,5]}...
3. Base cases: dp[0] = 0 for all j,k, dp[1] = 0 for all j,k, dp[2][j][k] = 1 if gcd(j,k)==1 and j!=k
4. Filling up the table should be relatively straighforward now.

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

5. Final answer = sum(dp[N][1..6])

This has a time and space complexity of O(N*6*6) ~ O(N).

Edit: @KellyBundy was kind enough to add a Python implementation; corrected it (and a minor flaw in my answer) and added here:

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