A094912 Output from a certain finite automaton when fed binary representation of n read from right to left.

0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset

0,1

Comments

There are 3 states. Start in state A.

If in A and 0 arrives go to A

If in A and 1 arrives go to B

If in B and 0 arrives go to C

If in B and 1 arrives go to A

If in C and 0 arrives go to A

If in C and 1 arrives go to C

If end in A, B, C then output 0, 0, 1 respectively.

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]

Example

a(10) = 1: 10 = 1010, read from right: A->A->B->C, so output a 1.

Maple

T:= <<1, 3, 1>|<2, 1, 3>>:
a:= proc(n)
  local L, state, i;
  L:= convert(n, base, 2);
  state:= 1;
  for i from 1 to nops(L) do
    state:= T[state, L[i]+1];
  od:
  [0, 0, 1][state];
end proc:
seq(a(n), n=0..100); # Robert Israel, Aug 18 2014

Prog

(PARI) {m=104; for(n=0, m, tape=binary(n); d=length(tape); state="A"; for(j=0, d-1, in=tape[d-j];
state=if(state=="A", if(in==0, "A", "B"), if(state=="B", if(in==0, "C", "A"), if(in==0, "A", "C"))));
print1(if(state=="A"||state=="B", 0, 1), ", "))} \\ Klaus Brockhaus, Jun 23 2004
(Haskell)
a094912 n = a 2 n where
   a s 0 = 0 ^ s
   a s x = a (t s b) x' where (x', b) = divMod x 2
   t 2 0 = 2; t 2 1 = 1; t 1 0 = 0; t 1 1 = 2; t 0 0 = 2; t 0 1 = 0
   -- state encoding: A = 2, B = 1, C = 0.
-- Reinhard Zumkeller, Nov 11 2013
(Python)
def delta(q, a):
    if q == "A": return {"0": "A", "1": "B"}[a]
    if q == "B": return {"0": "C", "1": "A"}[a]
    return {"0": "A", "1": "C"}[a]
def a(n):
    q = "A"
    for a in bin(n)[2:][::-1]: q = delta(q, a)
    return int(q == "C")
print([a(n) for n in range(105)]) # Michael S. Branicky, Jul 31 2022

Crossrefs

Cf. A231600.

Sequence in context: A294936 A296210 A368990 * A103673 A028862 A011673

Adjacent sequences: A094909 A094910 A094911 * A094913 A094914 A094915

Keyword

nonn,easy,base

Author

N. J. A. Sloane, Jun 21 2004

Extensions

A very interesting paper. I only looked though it as far as page 12. Perhaps some reader would read to the end and add appropriate references to it from other entries in the OEIS, as well as adding any new sequences that are found. A similar remark could be made about many papers on Jean-Paul Allouche's web site. - N. J. A. Sloane.

More terms from Klaus Brockhaus, Jun 23 2004

Status

approved