OFFSET
0,3
FORMULA
a(2n + 1) = a(n).
a(4n) = a(2n) with a(0) = 1.
a(4n + 2) = 2*b(n), b(2n + 1) = 2*b(n), b(2n) = 3*c(n - 1, 1) with b(0) = 1.
c(2n + 1, k) = c(n, k), c(4n + 2, k) = (k + 2)*c(2n, k), c(4n, k) = (k + 3)*c(n - 1, k + 1) with c(0, k) = 1.
Another way to compute a(4n + 2):
a(2*(4^n - 1)/3) = (n + 1)!.
a(2^(2m)*(2k + 1) + 2*(4^m - 1)/3) = (m + 1)*a(2^(2m)*k + 2*(4^m - 1)/3).
a(2^(2m + 1)*(2k + 1) + 2*(4^(m + 1) - 1)/3) = a(2^(2m + 1)*k + 2*(4^(m + 1) - 1)/3).
Note that a(4n + 2) is completely defined by these 3 last formulas. However, it looks like that it is not so easy to identify m and k for a given n, which makes these formulas useless for computing this sequence.
EXAMPLE
a(6) = 4 because the binary expansion of 6 is 110 and we have [(10), 1(10)] -> [1, 1]. Increasing these values by 1 gives us 2*2 = 4.
a(18) = 6 because the binary expansion of 18 is 10010 and we have [(10), (10)0(10)] -> [1, 2]. Increasing these values by 1 gives us 2*3 = 6.
a(26) = 18 because the binary expansion of 26 is 11010 and we have [(10), (10)(10), 1(10)(10)] -> [1, 2, 2]. Increasing these values by 1 gives us 2*3*3 = 18.
For n=482, the bits of n and the resulting product for a(n) are
n = 482 = binary 1 1 1 1 0 0 0 1 0
a(n) = 162 = 3*3*3*3 *2
n=3863 = binary 111100010111 is the same a(n) = 162 since its final trailing "111" has no effect.
MATHEMATICA
A033264[n_] := SequenceCount[IntegerDigits[n, 2], {1, 0}];
A053645[n_] := n - 2^Floor@Log2@n;
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Nov 14 2023 *)
PROG
(PARI) a(n) = my(A = 1, B = 1); if(n, for(i=1, logint(n, 2), if(bittest(n, i), A *= (B += !bittest(n, i-1))))); A
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Mikhail Kurkov, Oct 14 2023
STATUS
approved