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

海里游 发表于 2011-12-5 13:34:59

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

我想完成下面的测试，请问那位高手有高招。
若有一个奇数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是适合条件的最小数。

G-Spider 发表于 2011-12-5 14:33:51

如果考虑计算的话，
因为mT+1=2^n
所以S=mT 有特点:二进制全1
比如1*127=127=1111111B
最高的一个bit 1在第6位，如果加1后，最高的bit 1进了一位，必满足条件了。

medie2005 发表于 2011-12-5 15:04:05

请考虑φ(T)的素数分解.    其中φ(m)表示m的欧拉函数

海里游 发表于 2011-12-5 15:45:28

有幸得到二位高人的指点！
我虽然还没有实施，还不知是否会实施，
但G-Spider 所叙述的原理很明确，首先就抓住了数字特点，
高人的办法就是高。
medie2005所说考虑φ(T)的素数分解，是说G-Spider的方法要考虑素数分解？
那要是弄个大数的话，就我这水平好像还很费劲呢。

G-Spider 发表于 2011-12-5 16:02:01

:)大数的话，我的那方法不合适了。

海里游 发表于 2011-12-5 16:10:32

噢，是这样，看来这也算是个难题了？
很期盼谁还能出个高招进行大数计算。

wayne 发表于 2011-12-5 18:14:39

6# 海里游

medie2005已经给出了一个充分的条件。
适合条件的最小数n一定是φ(T)的一个因子

wayne 发表于 2011-12-5 18:27:02

6# 海里游
http://mathworld.wolfram.com/MultiplicativeOrder.htmlTable, {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)中的因子不好找吧？
要是用大数分解就麻烦了，如果能避开大数分解才好。

wayne 发表于 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}

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