我只会做第1题,就先写第1题吧.
把n质因数分n=p1^e1 * p2^e2 * ...* pk^ek
记:A(pi^ei) 为质因数分解中 pi^ei 的因数个数,S(pi^ei) 为质数分解中 pi^ei 的因数之和.
则:A(pi^ei) = ei+1,
S(pi^ei) = 1+pi+pi^2+...+pi^ei = [pi^(ei+1)-1]/(pi-1) = [pi^A(pi^ei)-1]/(pi-1)
并且,有这么一个性质:
an = A(p1^e1) * A(p2^e2) * ...* A(pk^ek)
Sn = S(p1^e1) * S(p2^e2) * ...* S(pk^ek)
我们先从简单的入手,假设n只有一个质因数,看看有多少个符合 3an^2>Sn 的,也就是:
[A(pi^ei)]^2 / S(pi^ei) > 3,结果如下:
p1=2,e1可取从0到6.
p2=3,e2可取从0到3.
p3=5,e3可取从0到1.
(再大就不行了)
再说n不止一个质因数的情形.
当 pi 和 ei 较小时,[A(pi^ei)]^2 / S(pi^ei) 会远远大于1,给其它可能的 pi 和 ei 留有富余,所以要多考虑这个富余的因素.
最大的富余量在 p1=2,e1=2 时,此时:[A(pi^ei)]^2 / S(pi^ei) = 9/7,所以要考虑全部
[A(pi^ei)]^2 / S(pi^ei) > 3*9/7 的 pi 和 ei.
所以就是需要一一测试下面的情形:
p1=2,e1可取从0到6.
p2=3,e2可取从0到3.
p3=5,e3可取从0到2.
p4=7,e4可取从0到1.
(再大就不行了)
为了保险起见,最好一一测试这些数.略.
第2问,an^3 > Sn 是同样的方法,就是考虑的数多了一些.
这样的n的个数当然也是有限的.
当 n 只有一个质因数时:
p1=2,e1可取从0到8.
p2=3,e2可取从0到4.
p3=5,e3可取从0到1.
p4=7,e4可取从0到1.
(再大就不行了)
当 pi 和 ei 比较小时,富余量最大在 p1=2,e1=3,p2=3,e2=2,p3=5,e3=1 时,此时:
A(2^3 * 3^2 * 5) ^3 / S(2^3 * 3^2 * 5) = (4*3*2)^3 / (15*13*6) = 11.8154
所以,最后要考虑的质因数有:
p1=2,e1可取从0到11.
p2=3,e2可取从0到6.
p3=5,e3可取从0到4.
p4=7,e4可取从0到3.
p5=11、13、17,e5可取从0到2.
p6=19到89的质数时,e6可取从0到1.
(再大就不行了)
建议写个程序,一个一个试,看看哪个最大.