在OEIS上搜索得到以下系列：
A005187：a（n）= a（[n/2]）+ n;1/sqrt（1-x）展开式的分母也是2^a（n）;也称2n -2n的二进制展开式中1的个数。
第二部分给出了2*n - bitcount(2*n)的公式，你可以用一些高效的比特计数实现来计算它，比如gcc的__builtin_popcount。

还要注意，比特计数（2n）=比特计数（n）
其推导如下：
设n =和（B[j] 2^j），其中j=0...N
假设B[N] = 1。定义
(a)F（n）= n + F（n/2）= n+n/2+n/4+...= 2 * n -（1/2 + 1/4 +... 1/2^N）的几何级数
现在，对于设置的每个比特b[j]，取整函数减去b[j]（sum（1/2^k，k=1...j+1））。这是因为它实际上去掉了1/2，但是随着它的传播，后续项被相加。
所以
(b)f（n）=下限（F（n）-总和（B[j]总和（1/2^k，k=1...j+1），其中j=0...N-1）
将（a）改为（b）
(c)f（n）=下限（2n -（1/2 + 1/4 +... 1/2^（N+1））- * 总和 *（B[j]（总和（1/2^（k），对于k=1..j+1），对于j=0...N-1））
ok，这部分相当酷！观察一下，当b[j]为1时，如果你从粗体表达式中偷偷地把1/2^（j+1）放进斜体的sum中，sum中的sum就变成了1，这意味着
B[j]（总和（1/2^（k），k=1..j+1），j=0...N-1）=总和（b[j]，j=0...N-1）
因此等式（c）简化为

f(n) = floor(2*n - sum(b[j], for j=0...N-1) - remainder)
f(n) = 2*n - bitcount(n-2^N) - 1    ; because remainder >0 and <1
f(n) = 2*n - bitcount(n)            ; b[N]=1, so bitcount(n)=bitcount(n-2^N)+1

其中余数是sum（1/2^j，j= 1，.. N +1 and B[j-1]==0），但这个和总是〉0且〈1（它至多为1-1/2^（N+2）且至少为1/2^（N+1），因此它可以作为-1移出楼层。
并且还注意，可以使比特计数运行时间等于设置的比特数（http://gurmeet.net/puzzles/fast-bit-counting-routines/）。一些处理器将其作为单独的指令。
不确定乳胶是否在这里工作，但是没有数学符号是很痛苦的。我一直不得不编辑它，因为有些东西总是看起来不对劲。

The function grows as follows - 

f(n) = n + f(n/2)
f(n/2) can be further simplified as - 

n/2 + f(n/4)

If we keep doing this, we will see n + n/2 + n/4 + n/8.....upto log n terms
= n (1 + 1/2 + 1/4 + 1/8...log n terms)
= n[ (1- (1/2)^log n)/(1/2)]
= 2n [1 - (1/2)^log n]

The term (1/2)^log n will become smaller and smaller as n increases, therefore the 2n term dominates. Hence f(n) belongs to big Theta (n)

如下所示，http://oeis.org/A005187可以产生一个闭合形式，因为：
a（n）= A011371（2n+1）
由于http://oeis.org/A011371：a（n）= A005187（n）- n，n ≥ 0
由于http://oeis.org/A005187：A184835（地板（n/2））
由于http://oeis.org/A184835：（PARI）{a（n）=局部的（t=真实的（极根（1+x+x^2+x^3+x^4-x^5）[1]））;n+下限（n/t）+下限（n/t^2）+下限（n/t^3）+下限（n/t^4）}