问一下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^a10^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$最大素音子矛盾,同样淘汰