论坛 › 算法交流 › 请高手出个招，找出最小能使2^n-1被T整除的n值

wayne 发表于 2011-12-18 00:38:23

1000<T<1100 范围内，解是

{1003, 277},
{1007, 76},
{1009, 464},
{1013, 141},
{1017, 144},
{1033, 238},
{1063, 18},
{1083, 76},
{1091, 68},
{1093, 190},
{1097, 327}

wayne 发表于 2011-12-18 00:44:40

For; If > 0, Print[{T, First}]]]

wayne 发表于 2011-12-18 01:03:10

惭愧，把问题想复杂了，其实这样更快：Select, {ii, T}], 1]; If > 0, Quiet]], 0]}, {T, 1, 2000, 2}], #[] > 0 &]{3, 2}
{9, 6}
{17, 5}
{19, 4}
{23, 21}
{27, 18}
{29, 7}
{37, 22}
{43, 25}
{47, 24}
{53, 24}
{57, 4}
{59, 16}
{73, 23}
{81, 18}
{83, 30}
{97, 93}
{103, 10}
{107, 87}
{111, 22}
{113, 32}
{131, 12}
{137, 30}
{139, 1}
{141, 24}
{149, 10}
{157, 39}
{159, 24}
{163, 49}
{167, 134}
{173, 121}
{177, 16}
{193, 20}
{197, 60}
{199, 29}
{223, 36}
{227, 68}
{233, 2}
{243, 18}
{249, 30}
{257, 141}
{263, 65}
{271, 18}
{277, 236}
{281, 45}
{283, 110}
{289, 101}
{293, 257}
{307, 4}
{309, 10}
{311, 56}
{317, 44}
{323, 85}
{339, 32}
{347, 275}
{353, 321}
{361, 76}
{373, 340}
{383, 298}
{391, 21}
{393, 12}
{397, 373}
{411, 30}
{417, 70}
{419, 195}
{421, 44}
{423, 24}
{433, 343}
{437, 175}
{439, 114}
{443, 397}
{447, 10}
{463, 305}
{467, 110}
{477, 24}
{479, 68}
{493, 21}
{501, 134}
{503, 12}
{523, 8}
{529, 483}
{531, 132}
{541, 55}
{547, 399}
{551, 49}
{557, 120}
{563, 468}
{577, 371}
{579, 20}
{587, 550}
{591, 60}
{593, 451}
{597, 62}
{607, 158}
{613, 270}
{617, 18}
{619, 35}
{647, 192}
{653, 322}
{667, 21}
{669, 36}
{673, 494}
{677, 575}
{681, 68}
{683, 665}
{699, 2}
{701, 177}
{703, 22}
{709, 57}
{719, 202}
{727, 386}
{729, 342}
{731, 277}
{743, 517}
{747, 30}
{757, 630}
{773, 111}
{787, 636}
{797, 417}
{809, 302}
{811, 339}
{813, 18}
{817, 67}
{821, 90}
{823, 239}
{831, 236}
{839, 341}
{841, 273}
{849, 110}
{857, 655}
{859, 240}
{863, 633}
{877, 534}
{887, 54}
{893, 346}
{907, 223}
{921, 4}
{933, 56}
{937, 149}
{947, 595}
{951, 44}
{953, 808}
{967, 151}
{971, 170}
{977, 574}
{983, 516}
{989, 109}
{1003, 277}
{1007, 76}
{1009, 464}
{1013, 141}
{1017, 144}
{1033, 238}
{1063, 18}
{1083, 76}
{1091, 68}
{1093, 190}
{1097, 327}
{1103, 803}
{1117, 44}
{1119, 340}
{1121, 103}
{1149, 298}
{1151, 213}
{1153, 865}
{1163, 845}
{1179, 12}
{1187, 1149}
{1193, 363}
{1201, 383}
{1213, 1002}
{1217, 421}
{1223, 674}
{1229, 114}
{1231, 568}
{1233, 30}
{1237, 285}
{1257, 404}
{1259, 394}
{1263, 44}
{1269, 162}
{1277, 645}
{1279, 537}
{1283, 275}
{1289, 286}
{1291, 143}
{1303, 13}
{1307, 980}
{1317, 114}
{1319, 27}
{1327, 363}
{1341, 84}
{1357, 219}
{1367, 379}
{1369, 166}
{1373, 1002}
{1381, 473}
{1399, 191}
{1401, 110}
{1409, 174}
{1423, 231}
{1427, 826}
{1431, 180}
{1433, 369}
{1437, 68}
{1459, 205}
{1481, 160}
{1483, 532}
{1487, 72}
{1493, 1312}
{1503, 300}
{1509, 12}
{1511, 558}
{1523, 627}
{1543, 808}
{1553, 135}
{1559, 29}
{1567, 926}
{1569, 8}
{1571, 51}
{1577, 112}
{1583, 267}
{1593, 306}
{1607, 1587}
{1613, 1219}
{1623, 190}
{1637, 731}
{1657, 291}
{1663, 1261}
{1667, 1655}
{1671, 120}
{1679, 527}
{1689, 468}
{1693, 479}
{1697, 1323}
{1709, 776}
{1711, 161}
{1723, 563}
{1733, 1726}
{1739, 346}
{1747, 129}
{1761, 550}
{1773, 60}
{1777, 69}
{1787, 861}
{1789, 484}
{1801, 470}
{1811, 150}
{1819, 405}
{1821, 158}
{1823, 474}
{1839, 270}
{1847, 1318}
{1849, 67}
{1851, 18}
{1857, 344}
{1867, 70}
{1877, 1552}
{1879, 841}
{1907, 568}
{1913, 1314}
{1931, 329}
{1933, 536}
{1941, 192}
{1951, 725}
{1957, 112}
{1959, 322}
{1979, 482}
{1987, 1540}
{1993, 753}
{1997, 1270}

海里游 发表于 2011-12-18 12:16:29

太谢谢了，能人就是不一样，一会儿一个招。
耽误老师的宝贵时间了，我没想到老师为我的代码还费了一番工夫，
并且这么快有了结果。
上面28*5^ii的代码，ii范围是从1至2000，不知最小值和最大值是
不是还能设大吗？像你前面说的60位。
如果设了大数Quiet]], 0]}, {T, 1, 2000, 2}], #[] > 0 &]
这里的参数除了1, 2000要改，其他还要改吗？

wayne 发表于 2011-12-18 14:09:25

44# 海里游
既要全部打印出来，又要大数，你不觉得很矛盾吗？

针对某一个特定的T，比较大的，需要把代码改一下，
比如T = 1000003 ，最小n是48685
T = 10000079， 最小n是1122997T = 1000003; tmp =Position, T], {ii, T}], 1]; If > 0, Quiet]], 0]现在这个话题应该消停了吧。

海里游 发表于 2011-12-18 17:34:21

现在这个话题应该消停了吧
哈哈……
我自己也觉得不好意思。:*-^
既要全部打印出来，又要大数，你不觉得很矛盾吗？
让大师为难了，也怪我当时没有把意思表述清楚，
当时是想说，起始值设大点，与最大值的距离小
一点，即能连续输出，又能输出大数。
我只强调T是自然数型，这样的大数就更难两全了，
除非公差大一点的等差级数还差不多。
现在觉得老师说的是，即要大数，又要全部连续
输出，真是即要满足东，又要满足西。
老师一直都来关注我的问题，真是不知如何感谢，
只能再一次口头谢谢！！

wayne 发表于 2011-12-18 18:06:00

46# 海里游
折煞我了，我不是什么大师哈。
按你的意思我已经改好代码了，
你只需修改参数a,b,step即可。
如果还有问题，可以追问，
我不是不想帮你，你别多想了。
a = 10^4 + 1; (*开始*)
b = 10^5 + 1000; (*结束*)
step = 10; (*步长*)
For, T], {ii, T}], 1]; If > 0, Print["T=", T, ",n=", tmp[]], 0]]

海里游 发表于 2011-12-18 20:10:48

那我就不客气的称你wayne ，感激的话我也不多说了，
你算是帮我的底了，可能是我最近比较有贵人缘吧，
运气还行，遇到了一个能帮助我的人。

海里游 发表于 2013-6-6 18:01:24

最小能使a^n-1被T整除的n值，有很多性质。下面称这样的n值为循环节，用p表示。
用循环节能判断素数、合数、寻找伪素数、寻找梅森数2^n-1(n为素数)、费马数2^n-1(n=2^k)及推广数a^n-1中的因子等。
进行上面的计算与判断，算法都比较简便，并且找梅森数、费马数因子参与运行的数字不需要运行a^n±1，只需要运行n(指数n的位数要小于程序求循环节所能运行的位数，循环节最大能运行五六十位，n最大也就只能取四十位左右)，只要循环节能运行到几位，因子就能找到几位。
方法：
1、若找梅森数2^n-1(n为素数)中的因子，只要在数2n*m+1(m是变量)中寻找循环节p=n的数，就是2^n-1中的因子，这些因子中有素因子，也有合数型因子，若是合数型因子，则这些因子都是以a为底的有相同循环节的伪素数(都是2^n-1中前面输出的素因子之积)。
2、若找费马数2^n+1(n=2^k)中的因子，只要在数4n*m+1(m是变量)中寻找循环节p=2n的数，就是2^n+1中的因子(也有合数型因子，是2^n+1中前面输出的素因子之积)。
找循环节，wayne在前面介绍的程序能秒杀五六十位数字，那么就能找梅森数、费马数中含有五六十位数的因子，虽说在数2n*m+1与4n*m+1中寻找有枚举之嫌，公差2n与4n有加大的可能，不过有些麻烦，最好适合并行计算。
目前本人求循环节的方法很笨拙，没能尝试使用Mathematica，所以很希望wayne能够帮忙测试一下找梅森数、费马数因子的大小与速度，也希望对此有兴趣的朋友也尝试一下或提出高见，使之完善，如有价值也许能为人所用。
例：找2^4096+1中的因子，就在4*4096*m+1(m是变量)中寻找循环节p=2*4096=8192的数，就是2^4096+1中的因子。
即：2^4096+1中有因子114689、 26017793、63766529 、 190274191361 、 12561 32134125569 、
568630647535356955169033410940867804839360742060818433等，这些因子都是循环节为8192的数，并且在小于这些数中只有这些数的循环节p=8192

查看完整版本: 请高手出个招，找出最小能使2^n-1被T整除的n值