第n层有多少个n？(Solved)

lulijie

我也抛砖引玉，说说我的思路。
用f(n,m)表示第n行第m个数。
那么得到以下递推公式
        f(1,1)=1，f(1,2)=1
        f(n+1,2k-1) =f(n,k)
        f(n+1,2k) =f(n,k)+f(n,k+1)

lulijie

f(n,1)=f(n-1,1)=......=f(1,1)=1
f(n,2)=f(n-1,1)+f(n-1,2)=1+f(n-1,2)=......=n-1+f(1,2)=n
f(n,3)=f(n-1,2)=n-1
f(n,4)=f(n-1,2)+f(n-1,3)=n-1+n-2=2n-3
f(n,5)=f(n-1,3)=n-2
f(n,6)=f(n-1,3)+f(n-1,4)=n-2+2n-5=3n-7
f(n,7)=f(n-1,4)=2n-5
f(n,8)=f(n-1,4)+f(n-1,5)=3n-8
f(n,9)=f(n-1,5)=n-3
。
。
。

lulijie

2009行共有2^2008+1个数，是个天文数字。
--------------------------------------------------------------------------------------
引入一个定义：
    a，b
一次填充变为  a，a+b，b
两次填充：上述一次填充后的数列，每相邻的数之间填入1个数，值等于相邻两数的和。
        即变为：a，2a+b,a+b，a+2b，b
三次填充：  上述两次填充后的数列，每相邻的数之间填入1个数，值等于相邻两数的和。
。。。。。。
n+1次填充：上述n次填充后的数列，每相邻的数之间填入1个数，值等于相邻两数的和。
-----------------------------------------------------------------------------------------------
这2^2008+1个数，可以这样填充。
第一步填充：
1，2009，2008，2007，2006，......，4，3，2，1
第二步填充：
    2009，2008之间不填充
    2008，2007之间填充1次，即填入4015
    2007，2006之间填充2次，即填入（2007），6020，4013，6019，（2006）三个数
    ......
     i   ,     i -1          之间填充 2009-i 次
    ......
   3，2之间填充2006次
   2，1之间填充2007次。  （ 其实上述填充后的数列是以2为左右对称。可以不用填充，参照2左边的数列就可）
---------------------------------------------------------------------------------------------
第2009行数列中，第一个2009为第二个数
     第二个2009，为1005和1004之间填充入的数（1005，1004之间共需填充1004次，第1次填入的就是2009）
     第三个2009，为670和669之间填入的数
（670，669之间共需填充1339次，（670），2009，1339，2008，（669），第2次填入的数中有2009）
    ......
这是我的一个思路，还是比较复杂。

lulijie

假设第一行为a，b
那么第N行，首尾之间的所有数都可表示为i*a+j*b，   i、j为正整数
    且  当i<=N，j<=N时，所有满足i和j互质的 i*a+j*b 值都存在，所有i和j不互质的 i*a+j*b 值都不存在。
----------------------------------------
当a=b=1，N=2009时，就是楼主的例子：
也就是求满足    i+j=2009，i、j为小于2009的正整数 且 i和j互质 的所有组合数。
    i=1，j=2008
    i=2，j=2007
    i=3，j=2006
    ......
    i=2007，j=2
    i=2008，j=1
因为2009=7*7*41
当i为7的倍数时，j也为7的倍数，i与j不互质，所以i不能等于7的倍数，
当i为41的倍数时，j也为41的倍数，i与j不互质，所以i不能等于41的倍数，
所以所求的总可能数为2008-（2009/7-1）-(2009/41-1)+(2009/(7*41)-1)=2008-286-48+6=1680

lulijie

对于N，假设N的第i个因数为ai，指数为ki
那么，总的个数=N-1- ∑(N/ai-1) + ∑(N/(ai*aj)-1) - ∑(N/(ai*aj*av)-1)+......
若N为素数，那么总的个数=N-1+（1-1）=N-1
N=3，那么总的个数=2-（1-1）=2
N=4，那么总的个数=3-（4/2-1）=2
N=5，那么总的个数=4-（1-1）=4
N=6，那么总的个数=5-（6/2-1)-(6/3-1)+(6/6-1)=5-2-1+0=2
N=8，那么总的个数=7-（8/2-1)=7-3=4
N=30,那么总的个数=29-（30/2-1)-（30/3-1)-（30/5-1)+(30/6-1)+(30/10-1)+(30/15-1)-(1-1)=29-14-9-5+4+2+1=8   
化简  N-1- ∑(N/ai-1) + ∑(N/(ai*aj)-1) - ∑(N/(ai*aj*av)-1)+......
       应该得到金眼睛的计算公式。

[ 本帖最后由 lulijie 于 2009-6-28 13:10 编辑 ]

lulijie

没学过高等数学，不知道欧拉函数是什么，确实孤陋寡闻。
百度了一下，明白了本题的答案就是求N的欧拉函数。
      i+j=2009
   i与j互质，就是i与2009互质，也就是求<=2009的与2009互质的所有正整数的个数，即求2009的欧拉函数。答案就是金眼睛的结果。
学习了。

lulijie

第N行的第m个数，表示成  p*a+q*b  的形式。
百度了一下法雷序列。发现：
所有的q/p或p/q都是N级法雷序列中的数。
难道仅仅是巧合么？

[ 本帖最后由 lulijie 于 2009-6-30 23:30 编辑 ]