|
|
A006521
|
|
Numbers n such that n divides 2^n + 1.
(Formerly M2806)
|
|
47
|
|
|
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, 118827, 124659, 177147, 185193, 250857, 263169, 292923, 354537, 356481, 373977, 531441, 555579, 752571
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Closed under multiplication: if x and y are terms then so is x*y.
More is true: 1. If n is in the sequence then so is any multiple of n having the same prime factors as n. 2. If n and m are in the sequence then so is lcm(n,m). For a proof see the Bailey-Smyth reference. Elements of the sequence that cannot be generated from smaller elements of the sequence using either of these rules are called *primitive*. The sequence of primitive solutions of n|2^n+1 is A136473. 3. The sequence satisfies various congruences, which enable it to be generated quickly. For instance, every element of this sequence not a power of 3 is divisible either by 171 or 243 or 13203 or 2354697 or 10970073 or 22032887841. See the Bailey-Smyth reference. - Toby Bailey and Christopher J. Smyth, Jan 13 2008
The number of terms < 10^n: 3, 5, 9, 15, 25, 40, 68, 114, 188, 309, 518, 851, .... - Robert G. Wilson v, May 03 2015
Also known as Novák numbers after Břetislav Novák who was apparently the first to study this sequence. - Charles R Greathouse IV, Nov 03 2016
Conjecture: For k > 1, k^m == 1 - k (mod m) has an infinite number of positive solutions. - Juri-Stepan Gerasimov, Sep 29 2019
|
|
REFERENCES
|
J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 243, p. 68, Ellipses, Paris 2008.
R. Honsberger, Mathematical Gems, M.A.A., 1973, p. 142.
W. Sierpiński, 250 Problems in Elementary Number Theory. New York: American Elsevier, 1970. Problem #16.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
MAPLE
|
for n from 1 to 1000 do if 2^n +1 mod n = 0 then lprint(n); fi; od;
S:=1, 3, 9, 27, 81:C:={171, 243, 13203, 2354697, 10970073, 22032887841}: for c in C do for j from c to 10^8 by 2*c do if 2&^j+1 mod j = 0 then S:=S, j; fi; od; od; S:=op(sort([op({S})])); # Toby Bailey and Christopher J. Smyth, Jan 13 2008
|
|
MATHEMATICA
|
Do[If[PowerMod[2, n, n] + 1 == n, Print[n]], {n, 1, 10^6}]
k = 9; lst = {1, 3}; While[k < 1000000, a = PowerMod[2, k, k]; If[a + 1 == k, AppendTo[lst, k]]; k += 18]; lst (* Robert G. Wilson v, Jul 06 2009 *)
Select[Range[10^5], Divisible[2^# + 1, #] &] (* Robert Price, Oct 11 2018 *)
|
|
PROG
|
(Haskell)
a006521 n = a006521_list !! (n-1)
a006521_list = filter (\x -> a000051 x `mod` x == 0) [1..]
(PARI) for(n=1, 10^6, if(Mod(2, n)^n==-1, print1(n, ", "))); \\ Joerg Arndt, Nov 30 2014
(Python)
A006521_list = [n for n in range(1, 10**6) if pow(2, n, n) == n-1] # Chai Wah Wu, Jul 25 2017
(Magma) [n: n in [1..6*10^5] | (2^n+1) mod n eq 0 ]; // Vincenzo Librandi, Dec 14 2018
|
|
CROSSREFS
|
Cf. A057719 (prime factors), A136473 (primitive n such that n divides 2^n+1).
Cf. A066807 (the corresponding quotients).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|