问一下project euler 241

sha1

记sigma(n)是n的所有除数之和，sigma(6) = 1+2+3+6=12。
找到n<=10^18的范围内的正整数，满足sigma(n)/n = k+1/2，k是整数.

数据范围太大了，蛮力不行。尝试用2x3,2x5,2x2x2x3, 2x2x2x5这样比较小的素数的乘积去做深搜，还是很慢。

暂时想不到什么别的思路了，问一下各位有什么好的办法？

winxos

原帖由 sha1 于 2009-4-20 18:22 发表
记sigma(n)是n的所有除数之和，sigma(6) = 1+2+3+6=12。
找到n

我也不会，我感觉应该是满足条件的数应该是因子上有点什么共性。

sha1

原帖由 winxos 于 2009-4-21 18:32 发表

我也不会，我感觉应该是满足条件的数应该是因子上有点什么共性。

恩，找不到其中的规律，估计要得利用点特殊的性质才行。

BTW，这是我找到的一些数，但是不全

2
24
4320
4680
26208
8910720
17428320
20427264
91963648
197064960
8583644160
10200236032
21857648640
57575890944
57629644800
206166804480
1416963251404800
15338300494970880

winxos

原帖由 sha1 于 2009-4-21 19:34 发表


恩，找不到其中的规律，估计要得利用点特殊的性质才行。

BTW，这是我找到的一些数，但是不全

2
24
4320
4680
26208
8910720
17428320
20427264
91963648
197064960
8583644160
10200236032
...

你是如何找到下面这么大的数的呢？
我觉得这个问题应该是从因子反过来求。

sha1

原帖由 winxos 于 2009-4-22 08:31 发表

你是如何找到下面这么大的数的呢？
我觉得这个问题应该是从因子反过来求。

我看前面那些数的因子都不大，然后找了前面一些较小的素数，然后用深搜乘出来的，一一验证，但是这样算得比较慢，我就弄了一些剪枝，最后就得到了这样的一些数，但是我这样剪枝之后搜出来的数不全。

不知道还有什么好一点的剪枝

winxos

原帖由 sha1 于 2009-4-22 12:07 发表


我看前面那些数的因子都不大，然后找了前面一些较小的素数，然后用深搜乘出来的，一一验证，但是这样算得比较慢，我就弄了一些剪枝，最后就得到了这样的一些数，但是我这样剪枝之后搜出来的数不全。

不知道还 ...

我上午想到了一点思路，
如果r(n)=k ,r表示因子和,
n=p1*p2*...pn
则r(n*Pn+1)=r(n)*(Pn+1 +1)
比如已经知道r(24)=60
则r(24*11)=60*12=720
这里要Pn+1不是n的因子，如果Pn+1是n的因子，则需要减去相应的部分，
比如r(2)=2
r(2*2)=7=2*(2+1)-2
r(3)=4
r(3*3)=13=4*(3+1)-3
.....
至于什么样的因子还可以达到k+1/2，我还没想呢，sha1你看看这条路能走不？

mathe

除了2这个特殊的数.
其它的数可以因子分解,其中最大的素数可以大于$10^6$,但是次大的素因子不会超过$10^6$,
而且最大因子必然是其它因子p对应的$1+p+p^2+...+p^k$一个素因子,而且这个表达式最多只有一个因子大于$10^6$
由此我们需要先姜所有小于$10^6$的素因子求出.

mathe

另外简单估计一下,可以得到$k<=6$,
也就是结果分子的素因子不大于13,当然分母素因子为2.
所以计算过程每个分量如果在分子出现大于13的素因子,分母必然出现.
利用这个条件可以捆绑很多素因子组合,可以极大减少搜索范围.

无心人

属于半多重完全数吧

mathe

是的.
对于n的任意一个素因子幂$p^a|n$,必然可以得出$p^a<sqrt(13)*10^9$
接下去我们可以穷举n的不超过$10^6$的最大素因子,假设这个素因子为P
我们可以从P的各种可能出发,来穷举.
比如P=127时,由于$P^a<sqrt(13)*10^9$,我们知道必然有$1<=a<=4$
比如a=4,那么对于比值贡献分母$127^4$,分子$1+127+127^2+127^3+127^4=262209281$,后者为大于$10^6$的素因子.
这个说明这个素因子$P_2=262209281$也必然为n的因子,同样它只能是1次,贡献分子$P_2+1=3^2*3137*13931$
这时我们得出3137和13931也是n的因子,这时已经得出$n>10^18$所以淘汰
也就是P=127,a=4无解

而如果P=127,a=3,那么我们得到分子中含$1+127+127^2+127^3=2^8*5*1613$,所以1613必然是n的素因子,同127是n小于$10^6$最大素音子矛盾,同样淘汰