找回密码
 欢迎注册
查看: 29655|回复: 48

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

[复制链接]
发表于 2011-12-5 13:34:59 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
我想完成下面的测试,请问那位高手有高招。
若有一个奇数T,在T-1的范围内,找出最小能使2^n-1被T整除的n值。
例1:若T=127,
当n=7时,2^n-1=2^7-1能被127整除,并且n=7是适合条件的最小数。
2、若T=129
当n=14时,2^n-1=2^14-1能被129整除,并且n=14是适合条件的最小数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-12-5 14:33:51 | 显示全部楼层
如果考虑计算的话,
因为mT+1=2^n
所以S=mT 有特点:二进制全1
比如1*127=127=1111111B
最高的一个bit 1在第6位,如果加1后,最高的bit 1进了一位,必满足条件了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-12-5 15:04:05 | 显示全部楼层
请考虑φ(T)的素数分解.    其中φ(m)表示m的欧拉函数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-12-5 15:45:28 | 显示全部楼层
有幸得到二位高人的指点!
我虽然还没有实施,还不知是否会实施,
但G-Spider 所叙述的原理很明确,首先就抓住了数字特点,
高人的办法就是高。
medie2005所说考虑φ(T)的素数分解,是说G-Spider的方法要考虑素数分解?
那要是弄个大数的话,就我这水平好像还很费劲呢。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-12-5 16:02:01 | 显示全部楼层
大数的话,我的那方法不合适了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-12-5 16:10:32 | 显示全部楼层
噢,是这样,看来这也算是个难题了?
很期盼谁还能出个高招进行大数计算。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-12-5 18:14:39 | 显示全部楼层
6# 海里游

medie2005已经给出了一个充分的条件。
适合条件的最小数n一定是φ(T)的一个因子
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-12-5 18:27:02 | 显示全部楼层
6# 海里游
http://mathworld.wolfram.com/MultiplicativeOrder.html
  1. Table[MultiplicativeOrder[2, m], {m, 1, 200, 2}]
复制代码
{1, 1}
{3, 2}
{5, 4}
{7, 3}
{9, 6}
{11, 10}
{13, 12}
{15, 4}
{17, 8}
{19, 18}
{21, 6}
{23, 11}
{25, 20}
{27, 18}
{29, 28}
{31, 5}
{33, 10}
{35, 12}
{37, 36}
{39, 12}
{41, 20}
{43, 14}
{45, 12}
{47, 23}
{49, 21}
{51, 8}
{53, 52}
{55, 20}
{57, 18}
{59, 58}
{61, 60}
{63, 6}
{65, 12}
{67, 66}
{69, 22}
{71, 35}
{73, 9}
{75, 20}
{77, 30}
{79, 39}
{81, 54}
{83, 82}
{85, 8}
{87, 28}
{89, 11}
{91, 12}
{93, 10}
{95, 36}
{97, 48}
{99, 30}
{101, 100}
{103, 51}
{105, 12}
{107, 106}
{109, 36}
{111, 36}
{113, 28}
{115, 44}
{117, 12}
{119, 24}
{121, 110}
{123, 20}
{125, 100}
{127, 7}
{129, 14}
{131, 130}
{133, 18}
{135, 36}
{137, 68}
{139, 138}
{141, 46}
{143, 60}
{145, 28}
{147, 42}
{149, 148}
{151, 15}
{153, 24}
{155, 20}
{157, 52}
{159, 52}
{161, 33}
{163, 162}
{165, 20}
{167, 83}
{169, 156}
{171, 18}
{173, 172}
{175, 60}
{177, 58}
{179, 178}
{181, 180}
{183, 60}
{185, 36}
{187, 40}
{189, 18}
{191, 95}
{193, 96}
{195, 12}
{197, 196}
{199, 99}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-12-5 19:13:28 | 显示全部楼层
wayne 是有点厉害,一串输出这么多。
不知大点的数字,不说百位,二十、三十位数好不好算,
φ(T)中的因子不好找吧?
要是用大数分解就麻烦了,如果能避开大数分解才好。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-12-5 19:41:31 | 显示全部楼层
9# 海里游

这个题的瓶颈 本质上就是整数分解,基本上你能分解到多少位,MultiplicativeOrder 就能算到那个程度。
下面给出  T= 10^m + 1 对应的最小n,我就给到60位了,
{m,n}
{1, 10}
{2, 100}
{3, 60}
{4, 612}
{5, 9090}
{6, 9900}
{7, 909090}
{8, 980392}
{9, 525780}
{10, 1374700}
{11, 2721180}
{12, 849915000}
{13, 14551804410}
{14, 1518743100}
{15, 763560}
{16, 10757824}
{17, 9732271265340}
{18, 249999750000}
{19, 101010101010101010}
{20, 4780769070063240}
{21, 31839968160}
{22, 63208567927959300}
{23, 30238845147055380}
{24, 76593124234068750000}
{25, 5974852718019150}
{26, 9501909883886661218900}
{27, 3756429983879822340}
{28, 68288031546290594763480}
{29, 385208012326656394453004620}
{30, 37935662427065700}
{31, 303030303030303030303030303030}
{32, 454107199791322539392480}
{33, 228826728441270216180}
{34, 11895652808643746807698218900}
{35, 5153002783667850900678787170}
{36, 5173492921847933277870000}
{37, 46108552933314991444717835649220}
{38, 310181394079257549159556944325200}
{39, 30013459143267265148340}
{40, 797844886761372155865976850078640}
{41, 554323725055432372297807607214733880780}
{42, 199276555277369253440323343700}
{43, 20486093670634092262859405209421450}
{44, 8678224560039944141728452762503328272796}
{45, 54686290559837261467199400}
{46, 23191849322887649440766047764754240100}
{47, 5143427942724013651731444402859858728321690}
{48, 3621541536749878611426273024}
{49, 329619256378175885025051091403520301272270420}
{50, 34366923271760553003541825541788709200}
{51, 51397556652484487847690276271140201853860}
{52, 14710058149341217727827514819180043874432195200}
{53, 9090909090909090909090909090909090909090909090909090}
{54, 2809083802657811953476980842571256750000}
{55, 245029803115589300259923664313614006360}
{56, 16869468857853983987603151693312452592953173200}
{57, 15063654767078035614740718700194691642922899260}
{58, 10541328481485126884562054116466687082819888197600}
{59, 407843316386084059769879811253137130423484531182773720}
{60, 39062476690894322522918480910567357083385000}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-19 14:53 , Processed in 0.053208 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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