A347205 a(2n+1) = a(n) for n >= 0, a(2n) = a(n) + a(n - 2^A007814(n)) for n > 0 with a(0) = 1.
1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 6, 3, 4, 1, 5, 4, 7, 3, 9, 5, 7, 2, 10, 6, 9, 3, 10, 4, 5, 1, 6, 5, 9, 4, 12, 7, 10, 3, 14, 9, 14, 5, 16, 7, 9, 2, 15, 10, 16, 6, 19, 9, 12, 3, 20, 10, 14, 4, 15, 5, 6, 1, 7, 6, 11, 5, 15, 9, 13, 4, 18, 12, 19, 7, 22, 10, 13
Offset: 0
Links
- Antti Karttunen, Table of n, a(n) for n = 0..16384
- J. Abate and W. Whitt, Brownian Motion and the Generalized Catalan Numbers, J. Int. Seq. 14 (2011) # 11.2.6.
- Index entries for sequences with interesting graphs or plots
Crossrefs
Programs
-
Mathematica
a[0] = 1; a[n_] := a[n] = If[OddQ[n], a[(n - 1)/2], a[n/2] + a[n/2 - 2^IntegerExponent[n/2, 2]]]; Array[a, 100, 0] (* Amiram Eldar, Sep 06 2021 *)
-
PARI
a(n) = if (n==0, 1, if (n%2, a(n\2), a(n/2) + a(n/2 - 2^valuation(n/2, 2)))); \\ Michel Marcus, Sep 09 2021
Formula
a(2n+1) = a(n) for n >= 0.
Sum_{k=0..2^n - 1} a(k) = A000108(n+1) for n >= 0.
a((4^n - 1)/3) = A000108(n) for n >= 0.
a(2^m*(2^n - 1)) = binomial(n + m, n) for n >= 0, m >= 0.
Generalization:
b(2n+1, p, q) = b(n, p, q) for n >= 0.
b(2n, p, q) = p*b(n, p, q) + q*b(n - 2^A007814(n), p, q) = for n > 0 with b(0, p, q) = 1.
Conjectured formulas: (Start)
Sum_{k=0..2^n - 1} b(k, 2, 1) = A006318(n) for n >= 0.
Sum_{k=0..2^n - 1} b(k, 2, 2) = A115197(n) for n >= 0.
Sum_{k=0..2^n - 1} b(k, 3, 1) = A108524(n+1) for n >= 0.
Sum_{k=0..2^n - 1} b(k, 3, 3) = A116867(n) for n >= 0.
b((4^n - 1)/3, p, q) is generalized Catalan number C(p, q; n). (End)
Conjecture: a(n) = T(n, wt(n)+1), a(2n) = Sum_{k=1..wt(n)+1} T(n, k) where T(2n+1, k) = T(n, k) for 1 <= k <= wt(n)+1, T(2n+1, wt(n)+2) = T(n, wt(n)+1), T(2n, k) = Sum_{i=1..k} T(n, i) for 1 <= k <= wt(n)+1 with T(0, 1) = 1. - Mikhail Kurkov, Dec 13 2024
Comments