关于二进数及其平方中1的数量差迭代收敛

hujunhua

定义c(x)=x的二进数中1的数量。
对于任意一个二进数，比如101，我们给它的尾部逐步加缀1形成一个序列{`a_n`}：101,1011,10111,101111, ...
构造`b_n:=c(a_n)-c(a_n^2)`, 即`a_n`与`a_n^2`的二进数中1的数量差。
试验发现, 除了前面的有限项，`b_n`的后部收敛到一个常数数列。
试证明这个猜想，或者找到反例。

hujunhua

给 `a` 的二进数加缀1，等价于生成 `2a+1`, 迭代下去就生成了一个序列{`a_n`}: `a_1=a, a_{n+1}=2a_n+1`
所以对于自然数中的奇数序列，可以划分成无数个上述那样的序列，`a_1≡1\pmod4`:
{1, 3, 7, 15, 31, 63, 127, 255, 511, ...}, 对应的{`b_n`}={0, 0, 0, 0, 0, 0, 0, 0, ...}
{5, 11, 23, 47, 95, 191, 383, 767, 1535, ...}, 对应的{`b_n`}={-1, -2, 1, 1, 1, 1, ...}
{9, 19, 39, 79, 159, 319, 639, 1279, 2559, ...}, 对应的{`b_n`}={-1, -2, -3, 0, 0, 0, 0, ...}
{13, 27, 55, 111, 223, 447, 895, 1791, 3583, ...}, 对应的{`b_n`}={-1, -2, -2, 2, 2, 2, 2, ...}
{17, 35, 71, 143, 287, 575, 1151, 2303, 4607, ...}, 对应的{`b_n`}={-1, -2, -3, -4, 0, 0, 0, 0, ...}
{21, 43, 87, 175, 351, 703, 1407, 2815, 5631, ...}, 对应的{`b_n`}={-3, -3, -2, -3, 0, 0, 0, 0, ...}
{25, 51, 103, 207, 415, 831, 1663, 3327, 6655, ...}, 对应的{`b_n`}={-2, -1, -2, -2, 1, 1, 1, 1, ...}
{29, 59, 119, 239, 479, 959, 1919, 3839, 7679, ...}, 对应的{`b_n`}={-1, -2, -2, -2, 3, 3, 3, 3, ...}
{33, 67, 135, 271, 543, 1087, 2175, 4351, 8703, ...}, 对应的{`b_n`}={-1, -2, -3, -4, -5, 0, 0, 0, 0, ...}
{37, 75, 151, 303, 607, 1215, 2431, 4863, 9727, ...}, 对应的{`b_n`}={-3, -5, -1, -2, -3, 0, 0, 0, 0, ...}
{41, 83, 167, 335, 671, 1343, 2687, 5375, 10751, ...}, 对应的{`b_n`}={-2, -4, -4, -3, -4, -1, -1, -1, -1, ...}
{45, 91, 183, 367, 735, 1471, 2943, 5887, 11775, ...}, 对应的{`b_n`}={-4, 0, 0, 1, 0, 4, 4, 4, 4, 4, 4, 4, ...}
..........
结果大多数收敛到一个非负常数，也就是说`c(n)≥c(n^2)`,  这是不是有点违反常识？

hujunhua

收敛结果的前100项是
{0, 1, 0, 2, 0, 0, 1, 3, 0, 0, -1, 4, 0, 1, 2, 4, 0, 0, -1, 0, 0, 0, \
-1, 5, 0, 2, -1, 2, 1, 2, 3, 5, 0, 0, -1, 0, -1, -2, 0, 4, -1, -1, 0, \
2, -2, 4, 3, 6, 0, 1, -2, 2, 1, 1, 1, 7, 0, 1, 0, 3, 2, 3, 4, 6, 0, \
0, -1, 0, -1, -2, -1, 0, 0, 0, -2,3, -2, -1, 4, 5, -1, -2, -1, 0, -2, \
1, 0, 2, -1, 0, -4, 5, 2, 5, 4, 7, 0, 1, -2, 1}
其中正数44项，零31项，负数25项。
在OEIS网站没有上述序列。

mathe

在一个二进制数$t$后面添加`m`个1以后就变为$s$, 那么
$c(s)=c(t)+m$
$s=2^m t+(2^m-1)$
于是$s^2=2^{2m}(t+1)^2-2^{m+1}(t+1)+1$
`\begin{split}c(s^2)&=c\left(2^{2m}(t^2+2t)+2^{2m}-2^{m+1}(t+1)+1\right)\\&=c(t^2+2t)+c\left((2^{m-1}-1)-t\right)+1\end{split}`
其中$c\left((2^{m-1}-1)-t\right)=(m-1)-c(t)$，当`(m-1)`不小于 `t` 的位数时 ，
所以$c(s^2)=c(t^2+2t)+m-c(t)$。
于是对于充分大的`m`, $c(s)-c(s^2)=2c(t)-c(t^2+2t)$为常数。