login
Numbers n such that n divides 2^n + 1.
(Formerly M2806)
48

%I M2806 #88 Sep 08 2022 08:44:35

%S 1,3,9,27,81,171,243,513,729,1539,2187,3249,4617,6561,9747,13203,

%T 13851,19683,29241,39609,41553,59049,61731,87723,97641,118827,124659,

%U 177147,185193,250857,263169,292923,354537,356481,373977,531441,555579,752571

%N Numbers n such that n divides 2^n + 1.

%C Closed under multiplication: if x and y are terms then so is x*y.

%C 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

%C A000051(a(n)) mod a(n) = 0. - _Reinhard Zumkeller_, Jul 17 2014

%C 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

%C 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

%C Conjecture: if n divides 2^n+1, then (2^n+1)/n is squarefree. Cf. A272361. - _Thomas Ordowski_, Dec 13 2018

%C Conjecture: For k > 1, k^m == 1 - k (mod m) has an infinite number of positive solutions. - _Juri-Stepan Gerasimov_, Sep 29 2019

%D J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 243, p. 68, Ellipses, Paris 2008.

%D R. Honsberger, Mathematical Gems, M.A.A., 1973, p. 142.

%D W. Sierpiński, 250 Problems in Elementary Number Theory. New York: American Elsevier, 1970. Problem #16.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Robert G. Wilson v, <a href="/A006521/b006521.txt">Table of n, a(n) for n = 1..1064</a>

%H Toby Bailey and Chris Smyth, <a href="http://www.maths.ed.ac.uk/~chris/papers/n_divides_2to_nplus1.pdf">Primitive solutions of n|2^n+1</a>.

%H Alexander Kalmynin, <a href="https://arxiv.org/abs/1611.00417">On Novák numbers</a>, arXiv:1611.00417 [math.NT], 2016.

%H V. Meally, <a href="/A006516/a006516.pdf">Letter to N. J. A. Sloane, May 1975</a>

%H C. Smyth, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Smyth/smyth2.html">The terms in Lucas Sequences divisible by their indices</a>, JIS 13 (2010) #10.2.4.

%p for n from 1 to 1000 do if 2^n +1 mod n = 0 then lprint(n); fi; od;

%p 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

%t Do[If[PowerMod[2, n, n] + 1 == n, Print[n]], {n, 1, 10^6}]

%t 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 *)

%t Select[Range[10^5], Divisible[2^# + 1, #] &] (* _Robert Price_, Oct 11 2018 *)

%o (Haskell)

%o a006521 n = a006521_list !! (n-1)

%o a006521_list = filter (\x -> a000051 x `mod` x == 0) [1..]

%o -- _Reinhard Zumkeller_, Jul 17 2014

%o (PARI) for(n=1,10^6,if(Mod(2,n)^n==-1,print1(n,", "))); \\ _Joerg Arndt_, Nov 30 2014

%o (Python)

%o A006521_list = [n for n in range(1,10**6) if pow(2,n,n) == n-1] # _Chai Wah Wu_, Jul 25 2017

%o (Magma) [n: n in [1..6*10^5] | (2^n+1) mod n eq 0 ]; // _Vincenzo Librandi_, Dec 14 2018

%Y Subsequence of A014945.

%Y Cf. A057719 (prime factors), A136473 (primitive n such that n divides 2^n+1).

%Y Cf. A000051, A006517.

%Y Cf. A066807 (the corresponding quotients).

%Y Solutions to k^m == k-1 (mod m): 1 (k = 1), this sequence (k = 2), A015973 (k = 3), A327840 (k = 4), A123047 (k = 5), A327943 (k = 6), A328033 (k = 7).

%Y Column k=2 of A333429.

%K nonn

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _David W. Wilson_, Jul 06 2009