快速计算10^12以内全部卡米切尔数

无心人

若整数n非素正整数 且对所有正整数a 满足$a^n-=a\quad(mod n)$ 则称n为卡米切尔数 现求一快速算法求出10^12内所有卡米切尔数 前三个数字是：561,1105,1729

无心人

没有人迎战么？ =============== 至少要有人出来分析下啊

mathe

假设 $n=p_1^{u_1}p_2^{u_2}...p_k^{u_k}$ 其中$p_1,p_2,...,p_k$为不同的素数 记 $m=LCM( (p_1-1)p_1^{u_1-1}, (p_2-1)p_2^{u_2-1},...,(p_k-1)p_k^{u_k-1})$ 那么就是说 $m|n$ 也就是要求 $p_1-1| n/{p_1^{u_1}}$ $p_2-1|n/{p_2^{u_2}}$ ... $p_k-1|n/{p_k^{u_k}}$

mathe

错了，上面应该是要求 $m|n-1$ 所以 $u_1=u_2=...=u_k=1$

mathe

也就是 $n=p_1 p_2 ... p_k$ 而且 $p_1 -1|n-1$ $p_2 -1|n-1$ ... $p_k-1|n-1$ 使用这个结果计算$10^12$以内所有解应该已经不是问题了。

mathe

还有至少3个素数，n必须是奇数

mathe

还有对于每个素因子p,$p(2p-1)<=n$,由此我们只要$10^6$以内的素数表。是不是这说明我们还可以加大搜索范围

无心人

还有，至少有三个因子 因此只需要10000以下素数 有1000000的可搜索$10^18$的

mathe

想到一种比较可行的算法。 假设计算N以内的数 我们首先找到所有奇素数p使得p(2p-1)<=N，把这个列表记住L 然后对于每个这样的素数p, M=[N/p]; for(x=(2*p-1);x<=M;x+=p-1){ 检查x的每个素因子q, 如果q^2|x,那么淘汰x 如果(x*p-1)%(q-1)!=0,淘汰x 如果对于所有的x的素因子q,x都没有被淘汰，那么x*p就是就是一个解。 }

mathe

原帖由 无心人 于 2008-3-26 14:17 发表 还有，至少有三个因子 因此只需要10000以下素数 有1000000的可搜索$10^18$的

你这是以最小的素因子为基准，我是以最大的素因子为基准