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

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