A302202 a(n) = number of distinct words arising in Post's tag system {00, 1101} applied to the word (100)^n , or a(n) = -1 if this word has an unbounded trajectory.

6, 21, 16, 31, 412, 57, 2156, 859, 382, 2811, 372, 2609, 704, 37913, 618, 155, 1008, 2407, 1210, 629, 5286, 1779, 1468, 4346275, 4130, 3247, 7024, 3891, 14638, 7025, 4570, 4329, 147694, 1863, 11126, 81147, 20210, 3853, 116020, 7641, 6494

Offset: 1

Author

Lars Blomberg and N. J. A. Sloane, Apr 19 2018

Keywords

• nonn

Comments

a(n) = A284119(n) + A284121(n) (or -1 if the trajectory is unbounded).

a(n) is a lower bound on A284116(3n) (assuming that there is no starting string with an unbounded trajectory).

On October 30 2020, a student in my CS 360 class, Zhiping Cai, found that for n = 70051, 96938660265781 (96.9 trillion) steps are needed. See https://github.com/zcai1/posts-problem . I am not sure this has been independently verified. - Jeffrey Shallit, Sep 13 2021

Links

• Lars Blomberg, Table of n, a(n) for n = 1..6075

Crossrefs

Cf. A284119, A284121; A284116.