找回密码
 欢迎注册
楼主: mathe

[擂台] csdn number

[复制链接]
发表于 2008-4-19 18:27:52 | 显示全部楼层
$10^n \pm 1$ 的因数分解: fac10pm1.zip (47.16 KB, 下载次数: 14) (源自:http://swox.com/~tege/repunit.html

相信正是各位需要的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-19 19:39:13 | 显示全部楼层
将 $10^b + 1$ 分解因数,假设素数 $p_1 <= p_2 <= ... <= p_r$ 均在其中,
如果将这 $r$ 个素数依次排列成的十进制数恰好为一个 b 位素数 $P = bar{p_1p_2...p_r}$ ,
那么 $n = p_1*p_2...p_r*P$ 即为解之一。

因为:$"Factor"(n) = bar{p_1p_2...p_rP} = bar{PP} = P*(10^b+1)$,
所以:${"Factor"(n)}/{n} = {P*(10^b+1)}/{p_1*p_2...p_r*P} = {10^b+1}/{p_1*p_2...p_r}$,
由本帖第一行的要求,即可得知上式一定可整除。

这是一个巧妙的构造法,估计与 mathe 在 7# 说的是一回事,但本人生性愚钝,早上始终无法读明白;
刚才才理出这个思路,描述出来与大家分享。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-19 20:41:43 | 显示全部楼层
> ifactors(10^105+1);

   [1, [[7, 2], [11, 1], [13, 1], [127, 1], [211, 1], [241, 1],

     [18276168846821336356291, 1], [265212793249617641, 1],

     [1661378260814161, 1], [29970369241, 1], [4147571, 1], [459691, 1],

     [9091, 1], [909091, 1], [2689, 1], [2161, 1]]]

评分

参与人数 1威望 +1 贡献 +1 经验 +1 鲜花 +1 收起 理由
mathe + 1 + 1 + 1 + 1 社区有你更精彩

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-19 21:06:02 | 显示全部楼层
根据shshsh的结果,所有因子长度之和为115,所以我们将它们排列好以后,任意去掉一些长度和为10的素因子,如果留下的是素数,那么就是一个解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-19 21:29:44 | 显示全部楼层

楼上统计有误。。。

  1. 7
  2. 7
  3. 11
  4. 13
  5. 127
  6. 211
  7. 241
  8. 2161
  9. 2689
  10. 9091
  11. 459691
  12. 909091
  13. 4147571
  14. 29970369241
  15. 1661378260814161
  16. 265212793249617641
  17. 18276168846821336356291
复制代码
将它粘贴进我的 PowCalc 中去,设定 R=0(求积),可验算正好为 $10^105+1$;
将它复制到我的 HugeCalc 中去,按“→”按钮,提示有 114 位(注:上面 mathe 统计错了)。
(这两款计算器都带智能过滤;其中 PowCalc 的过滤功能更强,有多种选项可设定)

故从中去掉某些数据行,并使减少的长度和= 9,剩下的若正好是个素数的话,那就走运了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-19 22:01:50 | 显示全部楼层
故从中去掉某些数据行,并使减少的长度和= 9,剩下的若正好是个素数的话,那就走运了
===================================================================
什么意思?

做这么多数字的素性测试很不容易的

感觉大家还是要学点haskell语言
那个东西做这种事情比C省N多麻烦
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-19 22:06:48 | 显示全部楼层
能不能把所有可能一行一个写成个文本文件?
提交到我这里
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-19 22:13:21 | 显示全部楼层
211
241
2161
2689
9091
459691
909091
4147571
29970369241
1661378260814161
265212793249617641
18276168846821336356291

211241216126899091459691909091414757129970369241166137826081416126521279324961764118276168846821336356291
测试1000次Rabin-Miller通过
=============================================================
重新测试100次通过
试除通过

评分

参与人数 1贡献 +1 经验 +1 鲜花 +1 收起 理由
mathe + 1 + 1 + 1 社区有你更精彩

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-19 22:33:48 | 显示全部楼层
得到个factor(n)/n = 7*7*11*13*127的结果

哈哈

评分

参与人数 1威望 +1 收起 理由
mathe + 1 我很赞同

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-20 06:48:49 | 显示全部楼层
非常好,说明通过因子分解$10^105+1$找到一个csdn数
$211*241*2161*2689*9091*459691*909091*4147571*29970369241*1661378260814161*265212793249617641*18276168846821336356291 $
  $ *211241216126899091459691909091414757129970369241166137826081416126521279324961764118276168846821336356291$
这个数字是多少?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 06:56 , Processed in 0.051400 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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