[转载]整数分解为2的幂的和

wayne

22# gxqcn


折煞我也，

gxqcn

检索信息是要点本事的，
这点你确实比我强。

mathe

19#的方法中主要问题在于解决下面的问题
也就是给定$a_0,a_1,...,a_h$求$b_0,b_1,...,b_h$使得
$\sum_{t=0}^ha_tv_t(2x)=\sum_{t=0}^hb_tv_t(x)$
19#中给出了一个$O(h^2)$的算法，如果我们能够降低这个变换的复杂度，那么这个算法复杂度也可以降下来（可以事先使用一些辅助计算）。而我觉得这个变换非常有可能可以有更加低的计算复杂度。

mathe

对于函数$f(x)$,我们记$\Delta f(x)=f(x+1)-f(x)$为$f(x)$的一阶差分。
更加普遍的，我们可以记$\Delta^0f(x)=f(x),\Delta^1f(x)=\Delta f(x),...,\Delta^nf(x)=\Delta\Delta^{n-1}f(x)$
于是我们有对于$t>=k,\Delta^kv_t(x)=v_{t-k}(x)$
于是对于n次多项式f(x),假设$f(x)=a_0v_0(x)+a_1v_1(x)+...+a_nv_n(x)$
由于
$v_t(0)=\delta(t,0)={(1,t=0),(0,t>0):}$
我们对f(x)做k阶差分，将x=0代入，得到
$\Delta^kf(0)=a_k$,
于是对于n次多项式$f(x)$我们有公式
$f(x)=\sum_{t=0}^n\Delta^tf(0)v_t(x)$
现在我们来计算$v_t(2x)$的各阶差分
它的一阶差分为$v_t(2x+2)-v_t(2x)=v_{t-1}(2x+1)+v_{t-1}(2x)$
更加一般的，其k阶差分为$\Delta^k(v_t(2x))=\sum_{s=0}^kC_k^sv_{t-k}(2x+s)$
将$x=0$代入上面表达式得到$\sum_{s=t-k}^kC_k^sC_s^{t-k}$
于是我们得到通用公式
$v_t(2x)=\sum_{k="floor"(t/2)}^t \sum_{s=t-k}^kC_k^sC_s^{t-k}v_k(x)$
呵呵，不知道对计算有没有用

mathe

化简了一下，好像是
$b_k=\sum_{t=0}^kC_k^t2^{k-t}a_{t+k}$
这个公式很简单呀。不过时间复杂度没有变换，倒是那个二维矩阵可以省略，可以改成O(log(n))的空间复杂度

qianyb

谁来转篇介绍怎么高效检索信息的文章，使我们也能高效一下

litaoye

mathe可以看看这部分，我没有试过。

log(p(2*n)) = 1/(2*L2)*(log(n/log(n)))^2 + (1/2 + 1/L2 + LL2/L2)*log(n) - (1 + LL2/L2)*log(log(n)) + Phi(log(n/log(n))/L2),
where L2=log(2), LL2=log(log(2)) and Phi(x) is a certain periodic function with period 1 and a tiny amplitude.
Numerically, Phi(x) appears to have a mean value around 0.66. An expansion up to O(1) term had been obtained earlier by Kurt Mahler. (End)

KeyTo9_Fans

这个贴子的标题太广泛了，没有把要讨论的具体问题说清楚。

所以不能怪别人提出相同的问题。

建议把此贴的标题改为《求把n分解成2的幂之和的方案总数》或者《把n分解成2的幂之和，有多少种分解方法？》。

这样就一目了然地把问题说清楚了。

yyy_fcz

如果要求输出n的2的幂之和具体的和的形式，有没有快一点的算法？

gxqcn

输出具体和的形式，再快也快不到哪里去，它好比是在清点一群羊，
而若只报总数，则可不必一头头的数，可以用加法、乘法等快速实现。