gxqcn 发表于 2008-4-19 18:27:52

10^n \pm 1 的因数分解:(源自:http://swox.com/~tege/repunit.html)

相信正是各位需要的。:)

gxqcn 发表于 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# 说的是一回事,但本人生性愚钝,早上始终无法读明白;
刚才才理出这个思路,描述出来与大家分享。

shshsh_0510 发表于 2008-4-19 20:41:43

> ifactors(10^105+1);

   , , , , , ,

   , ,

   , , , ,

   , , , ]]

mathe 发表于 2008-4-19 21:06:02

根据shshsh的结果,所有因子长度之和为115,所以我们将它们排列好以后,任意去掉一些长度和为10的素因子,如果留下的是素数,那么就是一个解

gxqcn 发表于 2008-4-19 21:29:44

楼上统计有误。。。

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

故从中去掉某些数据行,并使减少的长度和= 9,剩下的若正好是个素数的话,那就走运了:victory:

无心人 发表于 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次通过
试除通过

无心人 发表于 2008-4-19 22:33:48

得到个factor(n)/n = 7*7*11*13*127的结果

哈哈

mathe 发表于 2008-4-20 06:48:49

非常好,说明通过因子分解$10^105+1$找到一个csdn数
$211*241*2161*2689*9091*459691*909091*4147571*29970369241*1661378260814161*265212793249617641*18276168846821336356291 $
$ *211241216126899091459691909091414757129970369241166137826081416126521279324961764118276168846821336356291$
这个数字是多少?:)
页: 1 [2] 3 4 5 6 7 8 9 10 11
查看完整版本: csdn number