珍珠湾ART

标题: 平均因子数 [打印本页]

作者: constant 时间: 2005-12-28 22:51
标题: 平均因子数

难度：++　到　+++www.ddhw.com

对任意正整数n，令t(n)为 n 的因子个数，T(n) = (1/n)*Sum (1 to n) (t(k)) 为前n个t(k)的平均值。

n: 1, 2, 3, 4, 5, 6, 7, 8, ...
t(n): 1, 2, 2, 3, 2, 4, 2, 4, ...
T(n): 1, 3/2, 5/3, 2, 2, 7/3, 16/7, 5/2, ...

证明 |T(n) - ln n| < 1。

作者: QL 时间: 2005-12-29 21:57
标题: 回复：平均因子数

An other way to count nT(n) is the following:

For any k<=n, k will be counted [n/k] times. So

nT(n) = sum_k ([n/k])

Hence T(n) = sum_k ([n/k])/n, which is bounded above by 1+1/2+...1/n and bounded below by

1/2+...1/n -- so is ln(n). Hence the conlculsion.

作者: constant 时间: 2005-12-30 18:17
标题: Right. It's double counting again [:)]

Right. It's double counting again

欢迎光临珍珠湾ART (http://zzwav.com/)