OFFSET
0
COMMENTS
State transition table, initial State = A:
. State | A A B B C C D D State | A B C D
. Input | 0 1 0 1 0 1 0 1 -------+------------
. -------+-------------------------------- Output | 0 0 0 1
. State' | C B D A C C D D
.
State diagram:
. +-----------+ +------------+ +-----------+
. | 0, 1 | | 1 | | 0, 1 |
. | v 0 | v 0 v |
. | [ C ] <---- [ A ] [ B ] ----> [ D ] |
. | | ^ | | |
. | | | 1 | | |
. +-----------+ +------------+ +-----------+
From Kevin Ryde, Sep 12 2020: (Start)
a(n) is the output value at the state reached at the most significant 1-bit of n (or the initial state A if n=0). Low 1-bits of n alternate between A and B and then a 0-bit goes to C or D respectively. So a(n) = 0 or 1 according as the number of low 1-bits of n is even or odd, except n = 2^k-1 has no 0-bits at all so remains in A or B and a(n) = 0.
An increment n+1 changes low 1-bits to low 0-bits, and their parity is the period-doubling sequence A035263. This sequence differs from A035263 at n = 2^k-1 for k odd since the final state B is a(n) = 0 whereas A035263(n+1) = 1. (For k even, final state A is a(n) = 0 the same as A035263(n+1) = 0.)
(End)
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11.
J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11. [Local copy]
PROG
(Haskell)
a231600 n = a 3 n where
a s 0 = 0 ^ s
a s x = a (t s b) x' where (x', b) = divMod x 2
t 3 0 = 1; t 3 1 = 2; t 2 0 = 0; t 2 1 = 3; t 1 _ = 1; t 0 _ = 0
-- state encoding: A = 3, B = 2, C = 1, D = 0.
(PARI) a(n) = n++; my(v=valuation(n, 2)); v%2==1 && v!=logint(n, 2); \\ Kevin Ryde, Sep 12 2020
CROSSREFS
KEYWORD
nonn
AUTHOR
Reinhard Zumkeller, Nov 11 2013
STATUS
approved