login
A289677
a(n) = A289671(n)/2^f(n), where f(n) = 2*floor((n-1)/3) + ((n+2) mod 3) = A004523(n).
9
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,4
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.
PROG
(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
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Aug 01 2017
EXTENSIONS
Corrected by Don Reble, Aug 01 2017 (there were errors in A289671).
STATUS
approved