数学研发论坛

 找回密码
 欢迎注册
查看: 35053|回复: 61

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

[复制链接]
发表于 2008-3-25 17:17:13 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
精华
若整数n非素正整数
且对所有正整数a 满足$a^n-=a\quad(mod n)$
则称n为卡米切尔数

现求一快速算法求出10^12内所有卡米切尔数
前三个数字是:561,1105,1729
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-26 11:40:39 | 显示全部楼层
没有人迎战么?
===============
至少要有人出来分析下啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-26 13:21:59 | 显示全部楼层
假设
$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}}$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-26 13:24:09 | 显示全部楼层
错了,上面应该是要求
$m|n-1$
所以
$u_1=u_2=...=u_k=1$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-26 13:26:28 | 显示全部楼层
也就是
$n=p_1 p_2 ... p_k$
而且
$p_1 -1|n-1$
$p_2 -1|n-1$
...
$p_k-1|n-1$
使用这个结果计算$10^12$以内所有解应该已经不是问题了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-26 13:51:19 | 显示全部楼层
还有至少3个素数,n必须是奇数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-26 13:57:38 | 显示全部楼层
还有对于每个素因子p,$p(2p-1)<=n$,由此我们只要$10^6$以内的素数表。是不是这说明我们还可以加大搜索范围
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-26 14:17:46 | 显示全部楼层
还有,至少有三个因子
因此只需要10000以下素数

有1000000的可搜索$10^18$的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-26 14:20:43 | 显示全部楼层
想到一种比较可行的算法。
假设计算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就是就是一个解。
  }
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-26 14:22:56 | 显示全部楼层
原帖由 无心人 于 2008-3-26 14:17 发表
还有,至少有三个因子
因此只需要10000以下素数

有1000000的可搜索$10^18$的

你这是以最小的素因子为基准,我是以最大的素因子为基准
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2022-5-20 09:25 , Processed in 0.080900 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表