A379151 The binary weights of the Catalan numbers (A000108).
1, 1, 1, 2, 3, 3, 2, 6, 6, 9, 6, 8, 8, 12, 9, 16, 13, 17, 12, 17, 13, 18, 15, 25, 20, 17, 20, 24, 28, 25, 26, 25, 25, 32, 27, 34, 29, 32, 33, 29, 35, 29, 31, 36, 35, 44, 44, 49, 40, 46, 48, 44, 38, 50, 43, 44, 46, 47, 55, 50, 52, 58, 59, 60, 65, 68, 56, 62, 68
Offset: 0
Examples
a(10) = 6 because Catalan(10) = 16796 = 100000110011100_2, which has 6 one bits. - _Vincenzo Librandi_, Feb 05 2025
Links
- Amiram Eldar, Table of n, a(n) for n = 0..10000
- Amiram Eldar, Plot of (1/n^2) * Sum_{k=1..n} a(k) for n = 2^(8..23).
- Florian Luca and Igor E. Shparlinski, On the g-ary expansions of middle binomial coefficients and Catalan numbers, The Rocky Mountain Journal of Mathematics, Vol. 41, No. 4 (2011), pp. 1291-1301.
Programs
-
Magma
[&+Intseq(Catalan(n), 2): n in [0..100]]; // Vincenzo Librandi, Feb 05 2025
-
Mathematica
a[n_] := DigitCount[CatalanNumber[n], 2, 1]; Array[a, 100, 0]
-
PARI
a(n) = hammingweight(binomial(2*n, n)/(n+1));
Formula
Two formulas from Luca and Shparlinski (2011):
a(n) >= 3 for all but finitely many positive integers n.
a(n) >> eps(n) * sqrt(log(n)), for all n <= X with at most o(X) exceptions as X -> oo, where eps(n) is a function tending to zero as n -> oo.
Conjecture: Sum_{k=1..n} a(k) ~ n^2 / 2 (see the plot in the Links section).