问一下project euler 241

winxos

原帖由 mathe 于 2009-4-25 18:43 发表
是的.
对于n的任意一个素因子幂$p^a|n$,必然可以得出$p^a

数学知识不够 ，看的很费力，不知道`10^6`,`13`是如何得到的呢？
最终是不是说
只用`10^6`以内的素因子通过$p^a<sqrt(13)*10^9$来反推，求出所有的n？贡献分子$p2+1$中的+1是怎么得到的呢？
唉，只有佩服一下mathe了

mathe

定义$A(n)={\sigma(n)}/n$
那么我们可以有
定理1:
如果$n=\prod_{h=1}^tp_h^{a_h}$,那么$A(n)=\prod_{h=1}^tA(p_h^{a_h})=\prod_{h=1}^t{1+p_h+p_h^2+...+p_h^{a_h}}/{p_h^{a_h}}$
定理2:
如果$n=\prod_{h=1}^tp_h^{a_h}$,那么$\prod_{h=1}^t{1+p_h}/{p_h}<=A(n)<\prod_{h=1}^t{p_h}/{p_h-1}$

wayne

再加上一个条件，n必含因子2

wayne

当仅含2和3因子时，只有一种情况，就是2^3*3=24

winxos

原帖由 mathe 于 2009-4-26 16:03 发表
定义$A(n)={\sigma(n)}/n$
那么我们可以有
定理1:
如果$n=\prod_{h=1}^tp_h^{a_h}$,那么$A(n)=\prod_{h=1}^tA(p_h^{a_h})=\prod_{h=1}^t{1+p_h+p_h^2+...+p_h^{a_h}}/{p_h^{a_h}}$
定理2:
如果$n=\prod_{h=1}^t ...

谢谢mathe的耐心解答

mathe

记$q_h$为第$h$个素数,即$q_1=2,q_2=3,q_3=5,...$
引理1:如果n含有k个素因子,那么$A(n)<\prod_{h=1}^kq_h/{q_h-1}$
引理2:$\prod_{h=1}^16q_h>10^18$ (前16个素数乘积为32589158477190044730>10^18)
引理3:$\prod_{h=1}^15q_h/(q_h-1)~=7.209592601029953410588236494<7.5$
定理3:如果$n<10^18$,那么$A(n)<7.5$

mathe

引理4:如果$n<10^18$而且$A(n)=k+1/2$,那么$1<=k<=6$
或者说将$A(n)$写成即约形式${2k+1}/2$,那么分子为3到13之间的奇数.

mathe

定理4:如果$n<10^18,A(n)={2k+1}/2$,那么如果$p^a|n$,必然有$p^a<sqrt(13)*10^9$
证明,不妨设这里a已经是p的最大次数,于是我们知道$\sigma(p^a)=1+p+...+p^a$参与到分子的计算公式中,由于最终A(n)的即约形式中分子不超过13,那么除了最多一个不超过13的因子u,${1+p+...+p^a}/u$也必然是n的因子.
而且由于$p^a$同$1+p+...+p^a$互素,我们得出$p^a*{1+p+...+p^a}/u|n$,所以$p^a*{1+p+...+p^a}/u<=n$
得到$10^18>n>=p^a*{1+p+...+p^a}/u>p^{2a}/u>=p^{2a}/13$,于是得出定理4.

mathe

至此,最重要的结论都已经得出.
由此,还可以非常容易得出大于$10^6$的素因子只能是1次的,其次还可以证明大于$10^6$的素因子最多只有一个.

sha1

出去了几天，一直没机会上网。来看看大牛们的回复