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,3

Comments

Scatter plot might be called "Cypress forest on a windy day". - Antti Karttunen, Nov 30 2021

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

Formula

a(2n+1) = a(n) for n >= 0.

a(2n) = a(n) + a(n - 2^A007814(n)) = a(2*A059894(n)) for n > 0 with a(0) = 1.

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.

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).

Conjecture: C(p, q; n) = Sum_{k=0..n-1} p^k*q^(n-k-1) Sum_{j=0..k} q^j*A009766(n-2, j) for n > 1 with C(p, q; 0) = C(p, q; 1) = 1.

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 *)

Prog

(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

Crossrefs

Cf. A000108, A006318, A007814, A059894, A108524, A115197, A116867.

Similar recurrences: A124758, A243499, A284005, A329369, A341392.

Sequence in context: A002487 A318509 A357980 * A336161 A336160 A335421

Adjacent sequences: A347202 A347203 A347204 * A347206 A347207 A347208

Keyword

nonn,look

Author

Mikhail Kurkov, Aug 23 2021 [verification needed]

Status

approved