OFFSET
1,2
COMMENTS
n^2/2 + n/2 <= a(n) <= (31/50)*n^2 + n/2. The lower and upper bounds are attained at n=2^k and n=5*2^k for k >= 0.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..16384
FORMULA
a(n) = A268836(n)/2 + n. - Kevin Ryde, Mar 12 2021
a(1) = 1; a(n) = [n == 0 (mod 2)]*(4*a(n/2) - n/2) + [n == 1 (mod 2)]*(2*a((n - 1)/2)+2*a((n + 1)/2)-(n-1)/2 - A010060(n)) where [] is an Iverson bracket
MAPLE
b:= proc(n) option remember; `if`(n<2, n,
Bits[Xor](n, b(iquo(n, 2))))
end:
a:= proc(n) a(n):= 1+`if`(n<2, 0, a(n-1)+b(n-1)) end:
seq(a(n), n=1..60); # Alois P. Heinz, Mar 14 2021
MATHEMATICA
a[1]=1;
a[n_/; EvenQ[n]]:= a[n] = 4a[n/2] - n/2;
a[n_/; OddQ[n]]:= a[n] = 2a[(n - 1)/2]+2a[(n + 1)/2]-(n-1)/2 - ThueMorse[n];
(* Second program: *)
b[n_] := If[n==0, 0, BitXor@@Table[Floor[n/2^m], {m, 0, Floor[Log[2, n]]}]];
A066194 = Table[b[n]+1, {n, 0, 60}];
A066194 // Accumulate (* Jean-François Alcover, Sep 10 2022 *)
CROSSREFS
KEYWORD
nonn,look
AUTHOR
John Erickson, Mar 12 2021
STATUS
approved