请高手出个招，找出最小能使2^n-1被T整除的n值

wayne

1000

wayne

1. For[T = 1, T < 100, T += 2; tmp = n /. List@ToRules@Reduce[28*5^n - 1 == T k && k > 0 && 0 < n < 600, {k, n}, Integers]; If[Length[tmp] > 0, Print[{T, First[tmp]}]]]

复制代码

wayne

惭愧，把问题想复杂了，其实这样更快：

1. Select[Table[{T, tmp = Position[Table[Mod[28*5^ii, T], {ii, T}], 1]; If[Length[tmp] > 0, Quiet[tmp[[1,1]]], 0]}, {T, 1, 2000, 2}], #[[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}

海里游

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

wayne

44# 海里游 既要全部打印出来，又要大数，你不觉得很矛盾吗？ 针对某一个特定的T，比较大的，需要把代码改一下， 比如T = 1000003 ，最小n是48685 T = 10000079， 最小n是1122997

1. T = 1000003; tmp = Position[Table[Mod[28*PowerMod[5, ii, T], T], {ii, T}], 1]; If[Length[tmp] > 0, Quiet[tmp[[1, 1]]], 0]

复制代码

现在这个话题应该消停了吧。

海里游

现在这个话题应该消停了吧

哈哈…… 我自己也觉得不好意思。

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

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

wayne

46# 海里游 折煞我了，我不是什么大师哈。 按你的意思我已经改好代码了， 你只需修改参数a,b,step即可。 如果还有问题，可以追问， 我不是不想帮你，你别多想了。

2. a = 10^4 + 1; (*开始*)
3. b = 10^5 + 1000; (*结束*)
4. step = 10; (*步长*)
5. For[T = a, T < b, T += step;tmp = Position[Table[Mod[28*PowerMod[5, ii, T], T], {ii, T}], 1]; If[Length[tmp] > 0, Print["T=", T, ", n=", tmp[[1, 1]]], 0]]

复制代码

海里游

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

海里游

最小能使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