n|2^n+1
求出所有满足条件n|2^n+1的位数不超过50的整数n 本帖最后由 wayne 于 2011-1-12 20:47 编辑:dizzy:，只考虑素数解，我只能给到十位数：
1,3,171,13203,97641,354537,2354697,10970073,29884473,33894369,38265939,74214171,116226009,344380329,751611177,892145817,2595432537,
4014314433
除了3，你给出的都不是素数解:)实际上除了前两个，你给出的都是9的倍数 除了1和3，其余解应该都是3的倍数 好像蛮有规律的：
(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 3# mathe
:loveliness: , 漏出马脚了,应该叫 本原解: Primitive solutions
http://oeis.org/A136473
这个问题有人研究过,请看: 上面链接不错,基本可以解决这个问题了.
同样我先证明对于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 第一步
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,
添加.... 8# mathe
把所有的50位内的本原解都找出来,能办到吗
页:
[1]