数列通项公式之二

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) 即求 数列第 $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)

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)

056254628

如果用u(k,i)表示满足以下条件的n的个数（其中i<=k）： 2^(k-1)

KeyTo9_Fans

赞楼上！ 5#太失败了。 明明就用φ(n)来描述就足够了。 怎么就想歪了…… ################################## 楼上是第100贴，帮你做个记号，留作纪念。 希望你的结论是对的，不要给100贴的纪念抹黑了。 ##################################

mathe

8#应该不对