csdn number

gxqcn

$10^n \pm 1$ 的因数分解： fac10pm1.zip (47.16 KB, 下载次数: 14)

2008-4-19 18:27 上传

点击文件名下载附件
10^n±1 的因数分解

（源自：http://swox.com/~tege/repunit.html） 相信正是各位需要的。

gxqcn

将 $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

> 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]]]

mathe

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

gxqcn

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，剩下的若正好是个素数的话，那就走运了

无心人

故从中去掉某些数据行，并使减少的长度和= 9，剩下的若正好是个素数的话，那就走运了 =================================================================== 什么意思？ 做这么多数字的素性测试很不容易的 感觉大家还是要学点haskell语言 那个东西做这种事情比C省N多麻烦

无心人

能不能把所有可能一行一个写成个文本文件？ 提交到我这里

无心人

211 241 2161 2689 9091 459691 909091 4147571 29970369241 1661378260814161 265212793249617641 18276168846821336356291 211241216126899091459691909091414757129970369241166137826081416126521279324961764118276168846821336356291 测试1000次Rabin-Miller通过 ============================================================= 重新测试100次通过 试除通过

无心人

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

mathe

非常好，说明通过因子分解$10^105+1$找到一个csdn数 $211*241*2161*2689*9091*459691*909091*4147571*29970369241*1661378260814161*265212793249617641*18276168846821336356291 $ $ *211241216126899091459691909091414757129970369241166137826081416126521279324961764118276168846821336356291$ 这个数字是多少？