用v(p,n)表示正整数n的因子中素因子p的个数.
用d(n)表示n的约数个数,则d(n)=∏(v(p,n)+1).
考虑10^12内,满足d(n)>max{d(k):k<n}的正整数n的性质.
首先对素数p<q,应有v(p,n)≥v(q,n).
否则对m=n·(p/q)^(v(q,n)-v(p,n))<n,有d(m)=d(n).
于是,若v(37,n)≥1,则v(2,n)≥v(3,n)≥...≥v(37,n)≥1,
可得n≥2×3×...×31×37>10^12,不在讨论范围内.
因此对p≥37,都有v(p,n)=0.
若v(31,n)=1,由10^12/5<2×3×...×31<10^12/4,
n只可能为2×3×...×31及其2,3,4倍.
d(n)最大为(3+1)×(1+1)×...×(1+1)=4096.
以下只需考虑v(31,n)=0的情况.
由2^5>31,如果v(2,n)≥9,而v(31,n)=0.
可知整数m=31n/2^5<n,且d(m)≥d(n).
因此v(2,n)≤8.
同理,由3^4>31,同理可得v(3,n)≤6.
类似有v(5,n)≤4,v(7,n)≤2,v(11,n)≤2,...
如果v(19,n)≥2,则v(2,n)≥v(3,n)≥...≥v(19,n)≥2,
可得n≥(2×3×...×19)^2>10^12,不在讨论范围内.
因此对p≥19,都有v(p,n)≤1.
至此就将指数范围限制为9×7×5×3^4×2^3=204120种情况.
已经在计算能力范围内,所以图省事没考虑什么算法.
直接用Mathematica:
6720>4096,所以就是10^12以内d(n)的最大值.
上面的估计也适用小于10^12的上界.
不过要完全列举范围内具有给定约数个数的整数比较麻烦.
经过琐碎的步骤:
对n<10^5,d(n)最大为128,对应n=83160,98280;
对n<10^6,d(n)最大为240,对应n=720720,831600,942480,982800,997920;
对n<10^7,d(n)最大为448,对应n=8648640;
对n<10^12,d(n)最大为6720,对应n=963761198400.
