快速计算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$的

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