A270803 Formal inverse of Thue-Morse sequence A010060.

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

Offset

0

Comments

Conjecture: a(n) = A151666(floor((n+1)/2)) for n > 0. - Georg Fischer, Nov 29 2022

Conjecture confirmed. See the attached file. The idea is to guess the automaton for this sequence (in base 2) and then verify that it satisfies the identities in the Gawron-Ulas paper. Next we make a (base 2) automaton for A151666. This is easy because it is just the numbers consisting only of 0 and 1 in base 4. Then finally we assert Fischer's identity and Walnut returns TRUE. - Jeffrey Shallit, Nov 30 2022

Links

R. J. Mathar, Table of n, a(n) for n = 0..17000

Maciej Gawron and Maciej Ulas, On formal inverse of the Prouhet-Thue-Morse sequence, Discrete Mathematics 339.5 (2016): 1459-1470. Also arXiv:1601.04840 [math.CO], 2016.

Jeffrey Shallit, Verification of Fischer's conjecture

Formula

a(0)=0, a(1)=a(2)=1, a(3)=0; thereafter

if n mod 4 = 0 then a(n) = a(n-1),

if n mod 4 = 1 then a(n) = a(n-2),

if n mod 4 = 2 then a(n) = a(n-3),

otherwise a(n) = (a(n-4) + a((n-3)/4)) mod 2.

a(n) = A001002(n) mod 2 for n > 0. - John M. Campbell, Jul 17 2016

Maple

A270803 := proc(n)
    option remember;
    if n <=3 then
        op(n+1, [0, 1, 1, 0]) ;
    else
        if n mod 4 = 0 then
            procname(n-1)
        elif n mod 4 = 1 then
            procname(n-2)
        elif n mod 4 = 2 then
            procname(n-3)
        else
            (procname(n-4)+procname((n-3)/4)) mod 2;
        end if;
    end if;
end proc:
seq(A270803(n), n=0..120) ;

Mathematica

a[n_] := a[n] = Which[n <= 3, {0, 1, 1, 0}[[n + 1]], Mod[n, 4] == 0, a[n - 1], Mod[n, 4] == 1, a[n - 2], Mod[n, 4] == 2, a[n - 3], True, Mod[a[n - 4] + a[(n - 3)/4], 2]];
Table[a[n], {n, 0, 120}] (* Jean-François Alcover, Nov 27 2017, from Maple *)

Crossrefs

Cf. A010060, A151666.

See A270804 for positions of 1's

Sequence in context: A095130 A284789 A288736 * A030301 A316341 A284901

Adjacent sequences: A270800 A270801 A270802 * A270804 A270805 A270806

Keyword

nonn

Author

N. J. A. Sloane, Apr 02 2016

Status

approved