问一下project euler 241

winxos

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

数学知识不够 ，看的很费力，不知道`10^6`,`13`是如何得到的呢？ 最终是不是说 只用`10^6`以内的素因子通过$p^a

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^an>=p^a*{1+p+...+p^a}/u>p^{2a}/u>=p^{2a}/13$,于是得出定理4.

mathe

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

sha1

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