A078903 a(n) = n^2 - Sum_{u=1..n} Sum_{v=1..u} valuation(2*v, 2).

0, 0, 1, 1, 2, 3, 5, 5, 6, 7, 9, 10, 12, 14, 17, 17, 18, 19, 21, 22, 24, 26, 29, 30, 32, 34, 37, 39, 42, 45, 49, 49, 50, 51, 53, 54, 56, 58, 61, 62, 64, 66, 69, 71, 74, 77, 81, 82, 84, 86, 89, 91, 94, 97, 101, 103, 106, 109, 113, 116, 120, 124, 129, 129, 130, 131, 133, 134

Offset: 1

Author

Benoit Cloitre, Dec 12 2002

Keywords

• nonn

Comments

This is a fractal generator sequence. Let Fr(m,n) = m*n - a(n); then the graph of Fr(m,n) for 1 <= n <= 4^(m+1) - 3 presents fractal aspects.

Examples

			Fr(1, n) for 1 <= n <= 4^2-3 = 13 gives 1, 2, 2, 3, 3, 3, 2, 3, 3, 3, 2, 2, 1.
Fr(2, n) for 1 <= n <= 4^3-3 = 63 gives 2, 4, 5, 7, 8, 9, 9, 11, 12, 13, 13, 14, 14, 14, 13, 15, 16, 17, 17, 18, 18, 18, 17, 18, 18, 18, 17, 17, 16, 15, 13, 15, 16, 17, 17, 18, 18, 18, 17, 18, 18, 18, 17, 17, 16, 15, 13, 14, 14, 14, 13, 13, 12, 11, 9, 9, 8, 7, 5, 4, 2.
		

Links

• Ivan Neretin, Table of n, a(n) for n = 1..10000
• 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.
• Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple generating functions, 2004.
• Ralf Stephan, Table of generating functions (ps file).
• Ralf Stephan, Table of generating functions (pdf file).

Crossrefs

Cf. A078904, A073504.

Equals (1/2) * A076178(n).

Programs

Magma

[n^2-(&+[ &+[Valuation(2*v,2):v in [1..u]]:u in [1..n]]):n in [1..70]]; //  Marius A. Burtea, Oct 24 2019

Maple

a:= proc(n) option remember; `if`(n=0, 0,
      a(n-1)-1+add(i, i=Bits[Split](n)))
    end:
seq(a(n), n=1..68);  # Alois P. Heinz, Feb 03 2024

Mathematica

Accumulate@Table[DigitCount[n, 2, 1] - 1, {n, 68}] (* Ivan Neretin, Sep 07 2017 *)

PARI

a(n)=n^2-sum(u=1,n,sum(v=1,u,valuation(2*v,2)))

Python

def A078903(n): return (n+1)*n.bit_count()-n+(sum((m:=1<>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1))>>1)  # Chai Wah Wu, Nov 12 2024

Formula

a(n) = n^2 - Sum_{k=1..n} A005187(k);

a(n) = n^2 - Sum_{u=1..n} Sum_{v=1..u} A001511(v);

a(n+1) - a(n) = A048881(n).

G.f.: 1/(1-x)^2 * ((x(1+x)/(1-x) - Sum_{k>=0} x^2^k/(1-x^2^k))). - Ralf Stephan, Apr 12 2002

a(0) = 0, a(2*n) = a(n) + a(n-1) + n - 1, a(2*n+1) = 2*a(n) + n. Also, a(n) = A000788(n) - n. - Ralf Stephan, Oct 05 2003