数列通项公式之二
northwolves的数列通项公式的题，暂时没有通项公式，但mathe给出了一个出色的递推公式。本题跟northwolves的题有关，也是求通项公式。
一个数列：递推公式
F(0)=1
F(2n+1)=F(n)
F(2n)=F(n)+F(n-1)
---------------------------------------
为了便于计算
设 g(n)=F(n-1)
原数列转化为
g(1)=1
g(2n)=n
g(2n+1)=g(n)+g(n+1)
--------------------------------------------
那么$g(2^(k-1))=1$，$g(2^k)=1$
求：满足以下条件的n的个数，记作u(k)。
$2^(k-1)<n<2^k$，且$g(n)=k$
即求 数列第 $2^(k-1)$与 $2^k$项之间的数列值刚好等于k的项的数目u(k)。 比如: 求数列g(n)的第$2^2009$项到第$2^2010$项之间数列值等于2010的项的个数u(2010) u(2010)应该已经相当大了,应该是上100位的数 可先列出前几项，观察规律：
u(2)=1
u(3)=2
u(4)=2
u(5)=4
u(6)=2
u(7)=6
u(8)=4 全是素数？从2开始，
+1: 3
+2: 5
+2: 7
+4: 11
+2: 13
+6: 19
+4: 23
（可能太武断了，才看了这么几项，应该只是个巧合） 回复3楼：
u(k)<k
所以u(2010)<2010，不可能是上100位的数，最多4位数。 实际上$g(n)$在$2^{k-1}<=n<2^k$的时候的最大值为$F_{k+1}$,即菲波那且数列的第k+1项.
也就是这$2^{k-1}$个数只取大概${{\omega}^{k+1}}/{sqrt(5)}$个值,平均每个值要取${sqrt(5)}/{{\omega}^2}*(2/{\omega})^{k-1}$次,其中$\omega$是${sqrt(5)+1}/2$,根据这个估计式,大概在第15项左右开始u(k)<k不成里.
而对于这个问题,我们可以直接计算$2^{k-1}$和$2^k$之间一个较小数字m出现的次数,计算时间复杂度大概为
$O(k^2*m^2)$,空间复杂度$O(k*m^2)$ 如果用u(k,i)表示满足以下条件的n的个数（其中i<=k）：
2^(k-1)<n<2^k,且 g(n)=i
--------------------------------------------
那么u(k,i)=φ(i). φ()为欧拉函数。
即 u(k)=u(k,k)=φ(k)
所以u(2010)=φ(2010)=528
大家可以用较小的k值验证一下上述式子是否正确。 本帖最后由 KeyTo9_Fans 于 2010-1-13 12:36 编辑
赞楼上！:b:
5#太失败了。
明明就用φ(n)来描述就足够了。
怎么就想歪了……
##################################
楼上是第100贴，帮你做个记号，留作纪念。
希望你的结论是对的，不要给100贴的纪念抹黑了。
################################## 8#应该不对