n|2^n+1

mathe · 发表于 2011-1-12 20:30:00

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

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

×

求出所有满足条件n|2^n+1的位数不超过50的整数n

wayne · 发表于 2011-1-12 20:42:38

本帖最后由 wayne 于 2011-1-12 20:47 编辑

，只考虑素数解，我只能给到十位数：

1,3,171,13203,97641,354537,2354697,10970073,29884473,33894369,38265939,74214171,116226009,344380329,751611177,892145817,2595432537, 4014314433

mathe · 发表于 2011-1-12 21:48:43

除了3，你给出的都不是素数解

实际上除了前两个，你给出的都是9的倍数

northwolves · 发表于 2011-1-12 23:40:08

除了1和3，其余解应该都是3的倍数

northwolves · 发表于 2011-1-12 23:46:08

好像蛮有规律的： (00:44) gp > for(n=1,100000,if((2^n+1)%n==0,print(n))) 1 3 9 27 81 171 243 513 729 1539 2187 3249 4617 6561 9747 13203 13851 19683 29241 39609 41553 59049 61731 87723 97641

wayne · 发表于 2011-1-13 12:23:02

3# mathe

, 漏出马脚了,应该叫本原解: Primitive solutions http://oeis.org/A136473 这个问题有人研究过,请看:

n_divides_2to_nplus1.pdf (46.14 KB, 下载次数: 6)

mathe · 发表于 2011-1-13 14:11:27

上面链接不错,基本可以解决这个问题了. 同样我先证明对于n>1,3|n,对于n>3, 9|n 对于一个满足n|2^n+1的整数n,我们可以定义从n的因子集合到它的因子集合的函数 $f(d)=min{x|d|2^x+1}$. 由于f严格减,我们知道对于任何满足条件的n,将n用f作用若干次最后得到1,而这一系列数都是n的约数. 而且比较有意思的是,这一系列数都满足$n|2^n+1$ 也就是说,如果$n|2^n+1$,那么$f(n)|2^{f(n)}+1$,而且$f(n)$是n的因子,n是$2^{f(n)}+1$的因子也就是说,从n出发,我们可以构造一系列数 $n,f(n),f^{(2)}(n),...,1$ 对于其中任意相邻两项a,b,都有$b|a,a|2^b+1$ 由此,我们可以从1开始构造,算法如下: S={1} For any x in S find all factors of $2^x+1$ which is also times of x and add them into S if they're not inside it End For

mathe · 发表于 2011-1-13 14:19:46

第一步 S={1} 第二步 x=1, 找出所有y使得1|y,y|2^1+1=3,添加3,得出S={1,3} 第三步 x=3,找出所有y使得3|y,y|2^3+1=9,添加9,得出S={1,3,9} 第四步 x=9,找出所有y使得9|y,y|2^9+1=513,添加27,171,513, S={1,3,9,27,171,513} 第五步 x=27,2^27+1=3^4*19*87211,添加81,1539,2354697,7064091,34797189,134217729 第六步 x=81,2^81+1=3^5*19*163*87211*135433*272010961, 添加....

wayne · 发表于 2011-1-13 17:14:32

8# mathe 把所有的50位内的本原解都找出来,能办到吗

账号		自动登录	找回密码
密码			欢迎注册

[讨论] n|2^n+1

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