login
A289676
a(n) = A289670(n)/2^f(n), where f(n) = 2*floor((n-1)/3) + ((n+2) mod 3).
6
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,1
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.
PROG
(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
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Aug 01 2017; corrected by Don Reble, Aug 01 2017 (there were errors in A289670).
STATUS
approved