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

wayne 发表于 2011-12-7 12:00:10

30# 海里游
G-Spider 老师也是个不服输的人，有专研精神。

看你这话说的。:L

===============
我还想问一下，再变换一下形式还能实现吗？

我来张扬一下，这三种形式对Mathematica软件来说都是小儿科，直接秒杀的

wayne 发表于 2011-12-7 12:05:27

29# G-Spider
wayne可不得了，写过Mathematica 方面的书，你可以看看，呵呵。
我何时写过书，
G-Spider 也来捧杀俺，俺伤不起啊

海里游 发表于 2011-12-7 13:04:03

小儿科，直接秒杀的
不管咋样，能把Mathematica用的这么娴熟，也不是等闲之辈。
在这里能得到两位老师的指点是我的荣幸！

wayne 发表于 2011-12-8 20:20:50

30# 海里游
1、变化底数，例：3^n-1
2、变化差，例：3^n+1
3、变化高次项系数：例：28*5^n-1、28*5^n+1
我没打算 保留我的代码，
我的代码很简单，根本没有保留的价值，我还是贴出来吧：Reduce不到0.1秒，算出来的结果有：
{17, 1253788}
{51, 20909650126947162779716}
{85, 348714034443553974425322525050011080748}
{119, 5815567313638935956029708186115226665797655752549679956}
{153, 96987272776198332708416709963066110611988094276917672747669698477157308}
{187, 1617474370643784466466278005096953723768728550165420342091178876545837469604012176202596}
。。。。Reduce还是不到0.1秒，算出来的结果有：
{10, 2654733}
{112, 523553771289734018306479440702698688534629574272144363754546468697705315154733}
{214, 103252775487873539778349818853489242842014385763634353031391782424548439012836781535117409743533817787419329601424684690896665238892858468213127654733}
{316, 20363019484486454859862335314647447605067285978444603162320831488635453475242250902621480812597966560995030079639574454352917972467202807569575695308211387954724795592206363714879655665064413510972195422475777783440154733}
。。。

海里游 发表于 2011-12-8 21:33:45

wayne 老师太慷慨了！我只是想：我需要，老师费了力，
我想给老师点报酬也是应该的。没想到毫无保留的帖出
来了，只是让我不知怎么感谢！只能记在心里。
值得我尊敬！

海里游 发表于 2011-12-17 13:50:46

Wayne老师，又来麻烦你，
我测试了最开始的找出最小能使2^n-1被T整除的n值, T为自然数字型和T为10^m+1得出来的数都是对的。
但在
1、变化底数，例：3^n-1
2、变化差，例：3^n+1
3、变化高次项系数：例：28*5^n-1、28*5^n+1
得的结果中，好像有些问题，是我理解有问题？还是我没有把题意表达清楚，按我的测试好像对不上号。
这三个问题我的意思是：
找出最小能使3^n-1被T整除的n值,
找出最小能使3^n+1被T整除的n值,
找出最小能使28*5^n-1被T整除的n值,
由代码
1.        Reduce

得到的{17, 1253788}
1253788是3^17+1中的一个因子，n=1253788好像不符合3^n+1被T整除的最小值n

还想问一句前面自然数型的能进行大数计算吗？

海里游 发表于 2011-12-17 14:01:07

还有用下面的代码算自然数字型的怎么得出了与你不一样的结果？不知哪儿又出了问题。
Table, {m, 1, 200, 2}]

我的结果是：
{1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, \
12, 20, 14, 12, 23, 21, 8, 52, 20, 18, 58, 60, 6, 12, 66, 22, 35, 9, \
20, 30, 39, 54, 82, 8, 28, 11, 12, 10, 36, 48, 30, 100, 51, 12, 106, \
36, 36, 28, 44, 12, 24, 110, 20, 100, 7, 14, 130, 18, 36, 68, 138, \
46, 60, 28, 42, 148, 15, 24, 20, 52, 52, 33, 162, 20, 83, 156, 18, \
172, 60, 58, 178, 180, 60, 36, 40, 18, 95, 96, 12, 196, 99}
请老师帮我看一下这又是什么原因。

wayne 发表于 2011-12-17 16:55:45

1253788是3^17+1中的一个因子，n=1253788好像不符合3^n+1被T整除的最小值n
这句话没太明白。
您可以看到代码里面有一个103，意思是说，3^n+1被103整除的最小值n 是 17

海里游 发表于 2011-12-17 17:37:14

噢，原来是这样，28*5^n - 1 == 103 k && k
是表示
T=103
k是另一个因子。
下面所有数都符合T=103这样的条件。
只不过第一组17是n的最小值。
这与前面的
{1, 1}
{3, 2}
{5, 4}
{7, 3}
{9, 6}
{11, 10}
{13, 12}
{15, 4}
第一组
T=1，2^n-1=2^1-1能被T整除，并且n=1是最小的一个
第二组
T=3，2^n-1=2^2-1能被T整除，并且n=2是最小的一个
第三组
T=5，2^n-1=2^4-1能被T整除，并且n=4是最小的一个
和
m,n}
{1, 10}
{2, 100}
{3, 60}
{4, 612}
{5, 9090}
第一组
T=10^1+1，2^n-1=2^10-1能被T整除，并且n=10是最小的一个
第二组
T=10^2+1，2^n-1=2^100-1能被T整除，并且n=100是最小的一个
第三组
T=10^3+1，2^n-1=2^60-1能被T整除，并且n=60是最小的一个

的输出方式不一样，是这样吧？
那我要想像第一组一样把T设为变量，
像{1, 1}
{3, 2}
{5, 4}
{7, 3}
{9, 6}
{11, 10}
{13, 12}
{15, 4}
一样输出，并且计算大数，那要什么样的代码呢，我用前面给出的代码不能正常输出，
不知道什么原因，我虽然不好意思再麻烦你了，但是，还是要请大师帮忙帮到底了。

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

T<500以内，有解的如下：

{T,n}
{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}

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