A392736 A 4-automatic binary sequence with irreducible nested recurrence.

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

Offset

0

Comments

Unlike the Thue-Morse sequence A010060, the nested index 2n+1-a(n) in the recurrence formula cannot be simplified to a linear function of n. This makes a(n) a "genuinely nested" automatic sequence. The sequence is balanced; i.e., a(2n) + a(2n+1) = 1 for all n >= 0. The sequence is 4-automatic with a 4-state DFAO reading base-4 digits most significant first. The auxiliary sequence b(n) = a(2n+1-a(n)) is A392743.

Links

Michael De Vlieger, Table of n, a(n) for n = 0..10000

John M. Campbell and Benoit Cloitre, Meta-automatic Sequences, arXiv:2602.23395 [math.NT], 2026. See p. 3.

Formula

a(0)=0, a(1)=1, and for n>=0: a(4n) = a(n), a(4n+1) = 1-a(n), a(4n+2) = a(2n+1-a(n)), a(4n+3) = 1-a(2n+1-a(n)).

Example

For n=2: a(4*2+2) = a(10) = a(2*2+1-a(2)) = a(5-1) = a(4) = 1.

Mathematica

a[0] = 0; a[1] = 1; a[n_] := a[n] = Which[Mod[n, 4] == 0, a[Quotient[n, 4]], Mod[n, 4] == 1, 1 - a[Quotient[n, 4]], Mod[n, 4] == 2, a[2*Quotient[n, 4] + 1 - a[Quotient[n, 4]]], True, 1 - a[2*Quotient[n, 4] + 1 - a[Quotient[n, 4]]]]; Table[a[n], {n, 0, 79}]

Prog

(PARI) a(n) = if(n<2, n, my(q=n\4, r=n%4); if(r==0, a(q), r==1, 1-a(q), r==2, a(2*q+1-a(q)), 1-a(2*q+1-a(q))));

Crossrefs

Cf. A010060 (Thue-Morse sequence), A298952, A392737 (positions of 1's), A392738 (positions of 0's), A392743.

Twin sequence is A392742.

Sequence in context: A353354 A284912 A192082 * A353498 A296066 A073070

Adjacent sequences: A392733 A392734 A392735 * A392737 A392738 A392739

Keyword

nonn,easy

Author

John M. Campbell and Benoit Cloitre, Jan 21 2026

Status

approved