A122248 a(n) - a(n-1) = A113474(n).

0, 1, 3, 5, 9, 13, 18, 23, 31, 39, 48, 57, 68, 79, 91, 103, 119, 135, 152, 169, 188, 207, 227, 247, 270, 293, 317, 341, 367, 393, 420, 447, 479, 511, 544, 577, 612, 647, 683, 719, 758, 797, 837, 877, 919, 961, 1004, 1047, 1094, 1141, 1189

Offset: 0

Author

Paul Barry, Aug 27 2006

Keywords

• easy
• nonn

Comments

First differences are A113474.

The following sequences all appear to have the same parity: A003071, A029886, A061297, A092524, A093431, A102393, A104258, A122248, A128975. - Jeremy Gardiner, Dec 28 2008

Links

• Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, preprint, 2016.
• Hsien-Kuei Hwang, Svante Janson, Tsung-Hsi Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms 13:4 (2017), #47.
• Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.

Crossrefs

Cf. A113474, A122247.

Programs

PARI

a(n) = sum(k=1, n, sum(j=0, n, k\2^j)) - binomial(n, 2); \\ Michel Marcus, Mar 09 2023

Formula

G.f.: (1/(1-x))*Sum{k=0..infinity, x^(2^k)/((1-x)*(1-x^(2^k)))}-x^2/(1-x)^3.

a(n) = Sum_{k=1..n} Sum_{j=0..n} floor(k/2^j) - binomial(n,2).

a(n) = A122247(n)-binomial(n,2).