找回密码
 欢迎注册
楼主: 海里游

[求助] 请高手出个招,找出最小能使2^n-1被T整除的n值

[复制链接]
发表于 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}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-12-18 00:44:40 | 显示全部楼层
  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]}]]]
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-12-18 01:03:10 | 显示全部楼层
惭愧,把问题想复杂了,其实这样更快:
  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}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-12-18 12:16:29 | 显示全部楼层
太谢谢了,能人就是不一样,一会儿一个招。
耽误老师的宝贵时间了,我没想到老师为我的代码还费了一番工夫,
并且这么快有了结果。
上面28*5^ii的代码,ii范围是从1至2000,不知最小值和最大值是
不是还能设大吗?像你前面说的60位。
如果设了大数Quiet[tmp[[1,1]]], 0]}, {T, 1, 2000, 2}], #[[2]] > 0 &]
这里的参数除了1, 2000要改,其他还要改吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-12-18 14:09:25 | 显示全部楼层
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]
复制代码
现在这个话题应该消停了吧。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-12-18 17:34:21 | 显示全部楼层
现在这个话题应该消停了吧

哈哈……
我自己也觉得不好意思。
既要全部打印出来,又要大数,你不觉得很矛盾吗?

让大师为难了,也怪我当时没有把意思表述清楚,
当时是想说,起始值设大点,与最大值的距离小
一点,即能连续输出,又能输出大数。
我只强调T是自然数型,这样的大数就更难两全了,
除非公差大一点的等差级数还差不多。
现在觉得老师说的是,即要大数,又要全部连续
输出,真是即要满足东,又要满足西。
老师一直都来关注我的问题,真是不知如何感谢,
只能再一次口头谢谢!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-12-18 18:06:00 | 显示全部楼层
46# 海里游
折煞我了,我不是什么大师哈。
按你的意思我已经改好代码了,
你只需修改参数a,b,step即可。
如果还有问题,可以追问,
我不是不想帮你,你别多想了。

  1. a = 10^4 + 1; (*开始*)
  2. b = 10^5 + 1000; (*结束*)
  3. step = 10; (*步长*)
  4. 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]]
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-19 15:46 , Processed in 0.044060 second(s), 14 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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