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

Cielo

想了一下也没什么头绪，瞎猜个吧：
n = 1 或 5 时，有 4 个 n，其余的都只有 2 个……

superacid

原帖由 Cielo 于 2009-6-26 01:42 发表
想了一下也没什么头绪，瞎猜个吧：
n = 1 或 5 时，有 4 个 n，其余的都只有 2 个……

再多些两行猜呢......n=7就不对，还有n>2

superacid

经过我的多次鼓励，铯_猪哥恐鸣已经猜出来了。

Cielo

原帖由 superacid 于 2009-6-26 08:21 发表


再多些两行猜呢......n=7就不对，还有n>2

呵呵我是写到第7行了，结果只注意了新加的数，没看见原来保留下来的数

Osullivan

如果每秒此题杀死我100个脑细胞，我上午思考了三个小时，白搭，脑细胞死了多少，LZ你帮我算算~~~~~~~~~

superacid

看来这道题有一点难，明天给出第一个提示

r_517

去掉每行最后一个1，变成Stern Brocot Tree（囧。。。这名字我搜了半天才搜出来怎么拼的。。。）。。继续思考思路去了。。

金眼睛

数论对我来说太陌生了，我虽然不能给出证明过程，可以给出一个猜想的结果，呵呵！

再详细说一下我的思路吧，希望大家集思广益，把这道题证明出来。

1：先把第一行的两个1设成a和b，可以发现第N层是由两个数列累加而成，一个是a的系数，一个是b的系数。
2：比如第四层的一半 1 4 3 5 2，是由第三层1 3 2 3 1与0 1 1 2 1相加而成。
3：这个0 1 1 2 1是前两层的结合 0 （1 1）2 1 第一层出现了，0 1 （1 2 1）第二层出现了，也就是公用的1出现1次。
第N层可以由前N-1层由此递推关系构造出来！！

也许有朋友会问，这有什么用啊？呵呵，对于计算机编程来说，这个发现好处是显而易见的，后面附上解此题的Matlab程序，5秒可以算到25，然后由于数列太长，1.6*10^16这么长，out of memory了，不过前面这些结果足够发现一些规律了。

结论：
1：对于质数m来说，第m层含有m的个数为：N=m-1。
下面列出到25的结果，前面是层数m，后面是含有m的个数。
2-1，3-2，4-2，5-4，6-2，7-6，8-4，9-6，10-4，11-10，12-4，13-12，14-6，15-8，16-8，17-16，18-6，19-18，20-8，21-12，22-10，23-22，24-8，25-20……
2：既然对于质数规律这么明显，一定想到对各个合数进行质因数分解，通过观察找到如下规律：
对于某个合数的一个分解，例：m=  2^a  *  3^b  *  5^c  ……
则m层含有m的个数为：N=(2-1)*2^(a-1)*(3-1)*3^(b-1)*(5-1)*5^(c-1) ……

对于2009，由于2009=7^2*41  故 N=(7-1)*7^(2-1)*(41-1)*41^(1-1)=1680。

以上结论仅为猜想，希望能对大家有所启发，下面给出计算程序，会Matlab的人可以借鉴。
_________________________________________________________________________________

clear;
a=[0,1,1];b=[1,2];
for i=1:24
c=b;c(end)=[];c=[c,fliplr(b)];b=a+c;c(1)=[];a=[a,c];
2*length(find(b==(i+1)))
end
_________________________________________________________________________________

[ 本帖最后由 金眼睛 于 2009-6-28 00:20 编辑 ]

Cielo

哇！金眼睛的结果是欧拉函数，估计就是对的了 ！

edmond-xym

这个题目没问题么？
开始是两个1，那从第三行起为什么中间都有2？
另外，开始只有两个1，下面都是上面的两个数字之和，这不就是杨辉三角么？求第n层，用二项式就好了，但别忘了你的要求比二项式少一层，就是+1和-1的问题了。