数列通项公式之二

056254628

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)。

056254628

比如:    求数列g(n)的第$2^2009$项到第$2^2010$项之间数列值等于2010的项的个数u(2010)

mathe

u(2010)应该已经相当大了,应该是上100位的数

056254628

可先列出前几项，观察规律：
u(2)=1
u(3)=2
u(4)=2
u(5)=4
u(6)=2
u(7)=6
u(8)=4

KeyTo9_Fans

全是素数？从2开始，

+1: 3
+2: 5
+2: 7
+4: 11
+2: 13
+6: 19
+4: 23

（可能太武断了，才看了这么几项，应该只是个巧合）

056254628

回复3楼：
    u(k)<k
所以  u(2010)<2010，不可能是上100位的数，最多4位数。

mathe

实际上$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)$

056254628

如果用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

赞楼上！

5#太失败了。

明明就用φ(n)来描述就足够了。

怎么就想歪了……

##################################
楼上是第100贴，帮你做个记号，留作纪念。

希望你的结论是对的，不要给100贴的纪念抹黑了。
##################################

mathe

8#应该不对