A289676 a(n) = A289670(n)/2^f(n), where f(n) = 2*floor((n-1)/3) + ((n+2) mod 3).

2, 1, 1, 2, 2, 1, 4, 4, 3, 5, 4, 3, 10, 13, 12, 21, 18, 20, 43, 40, 39, 85, 71, 64, 146, 132, 116, 250, 231, 210, 462, 459, 438, 960, 990, 966, 2069, 2114, 2089, 4296, 4237, 4155, 8485, 8234, 8032, 16496, 16054, 15657, 32041, 31280, 30325, 61700, 60252, 58379, 118357, 115810, 112885

Offset: 1

Author

N. J. A. Sloane, Aug 01 2017

Keywords

• nonn

Comments

This is the number of distinct binary words w of length n that terminate under the Post tag system (see A284116, A289670) reduced to take into account the observation made by Don Reble that (if the bits of w are labeled from the left starting at bit 0) bits 1,2,4,5,7,8,... (not a multiple of 3) are "junk DNA" and have no effect on the outcome.

Crossrefs

Cf. A284116, A284119, A284121, A289670, A289671, A289672, A289673, A289674, A289675, A289677.

Cf. also A290436-A290441.

Programs

Python

from _future_ import division
def A289676(n):
    c, k, r, n2, cs, ts = 0, 1+(n-1)//3, 2**((n-1) % 3), 2**(n-1), set(), set()
    for i in range(2**k):
        j, l = int(bin(i)[2:],8)*r, n2
        traj = set([(l,j)])
        while True:
            if j >= l:
                j = j*16+13
                l *= 2
            else:
                j *= 4
                l //= 2
            if l == 0:
                c += 1
                ts |= traj
                break
            j %= 2*l
            if (l,j) in traj:
                cs |= traj
                break
            if (l,j) in cs:
                break
            if (l,j) in ts:
                c += 1
                break
            traj.add((l,j))
    return c # Chai Wah Wu, Aug 03 2017

Extensions

Corrected by Don Reble, Aug 01 2017 (there were errors in A289670)