A289677 a(n) = A289671(n)/2^f(n), where f(n) = 2*floor((n-1)/3) + ((n+2) mod 3) = A004523(n).

0, 1, 1, 2, 2, 3, 4, 4, 5, 11, 12, 13, 22, 19, 20, 43, 46, 44, 85, 88, 89, 171, 185, 192, 366, 380, 396, 774, 793, 814, 1586, 1589, 1610, 3136, 3106, 3130, 6123, 6078, 6103, 12088, 12147, 12229, 24283, 24534, 24736, 49040, 49482, 49879, 99031, 99792, 100747, 200444, 201892, 203765, 405931, 408478, 411403

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 eventually cycle 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, A289676.

Cf. also A290436-A290441.

Programs

Python

from _future_ import division
def A289677(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:
                ts |= traj
                break
            j %= 2*l
            if (l,j) in traj:
                c += 1
                cs |= traj
                break
            if (l,j) in cs:
                c += 1
                break
            if (l,j) in ts:
                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 A289671).