A333429 -id:A333429 - cp's OEIS frontend

A006521 Numbers n such that n divides 2^n + 1.

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

Offset: 1

N. J. A. Sloane

nonn

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
A000051(a(n)) mod a(n) = 0. - Reinhard Zumkeller, Jul 17 2014
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: if n divides 2^n+1, then (2^n+1)/n is squarefree. Cf. A272361. - Thomas Ordowski, Dec 13 2018
Conjecture: For k > 1, k^m == 1 - k (mod m) has an infinite number of positive solutions. - Juri-Stepan Gerasimov, Sep 29 2019

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).

Robert G. Wilson v, Table of n, a(n) for n = 1..1064
Toby Bailey and Chris Smyth, Primitive solutions of n|2^n+1.
Alexander Kalmynin, On Novák numbers, arXiv:1611.00417 [math.NT], 2016.
V. Meally, Letter to N. J. A. Sloane, May 1975
C. Smyth, The terms in Lucas Sequences divisible by their indices, JIS 13 (2010) #10.2.4.

Subsequence of A014945.
Cf. A057719 (prime factors), A136473 (primitive n such that n divides 2^n+1).
Cf. A000051, A006517.
Cf. A066807 (the corresponding quotients).
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).
Column k=2 of A333429.

a006521 n = a006521_list !! (n-1)
a006521_list = filter (\x -> a000051 x `mod` x == 0) [1..]
-- Reinhard Zumkeller, Jul 17 2014

[n: n in [1..6*10^5] | (2^n+1) mod n eq 0 ]; // Vincenzo Librandi, Dec 14 2018

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

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

for(n=1,10^6,if(Mod(2,n)^n==-1,print1(n,", "))); \\ Joerg Arndt, Nov 30 2014

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

More terms from David W. Wilson, Jul 06 2009

A015951 Numbers k such that k | 5^k + 1.

Original entry on oeis.org

1, 2, 3, 9, 21, 26, 27, 63, 81, 147, 189, 243, 338, 441, 567, 609, 729, 903, 1029, 1323, 1378, 1701, 1827, 2187, 2667, 2709, 3087, 3969, 4263, 4394, 4401, 5103, 5481, 6321, 6561, 7203, 8001, 8127, 9261, 9429, 11907, 12789, 13149, 13203

Offset: 1

Robert G. Wilson v

nonn

Jinyuan Wang, Table of n, a(n) for n = 1..5000 (first 500 terms from Seiichi Manyama)

5^k+m is divisible by k: A123062 (m=2), A123052 (m=3), A123047 (m=4).

Column k=5 of A333429.

[n: n in [1..10^5] | Modexp(5, n, n)+1 eq n]; // Jinyuan Wang, Dec 29 2018

Select[Range@ 14000, Divisible[5^# + 1, #] &] (* Michael De Vlieger, Oct 10 2016 *)
Select[Range[15000],PowerMod[5,#,#]==#-1&] (* Harvey P. Dale, Aug 11 2024 *)

isok(n) = Mod(5, n)^n == -1; \\ Michel Marcus, Oct 11 2016

for n in range(1,10**5):
    if pow(5,n,n)+1 == n: print(n, end=', ') # Stefano Spezia, Dec 30 2018

A015949 Numbers k such that k | 3^k + 1.

Original entry on oeis.org

1, 2, 10, 50, 250, 1250, 5050, 6250, 11810, 25250, 31250, 59050, 126250, 156250, 295250, 510050, 631250, 750250, 781250, 1476250, 2125250, 2550250, 3156250, 3751250, 3906250, 5964050, 7381250, 10626250, 12751250, 13947610, 15781250

Offset: 1

Robert G. Wilson v

nonn

a(n) mod 20 = 10 for n >= 3. - G. C. Greubel, Nov 05 2018
This sequence is infinite, because for n > 1, 3^a(n) + 1 is in this sequence. - Jinyuan Wang, Nov 06 2018
For the provided data, if k is a term then p*k is a term where p is an odd divisor of k. - David A. Corneth, Nov 06 2018

Giovanni Resta, Table of n, a(n) for n = 1..180 (first 100 terms from G. C. Greubel)

Cf. A034472 (3^n+1).
Cf. A006521 (k | 2^k + 1), A015950 (k | 4^k + 1), A015951 (k | 5^k + 1).
Column k=3 of A333429.

[n: n in [1..2*10^7]| Modexp(3, n, n)+1 eq n]; // Vincenzo Librandi, Nov 01 2018

Do[If[PowerMod[3, n, n] + 1 == n, Print[n]], {n, 1, 10^7}] (* Jinyuan Wang, Nov 01 2018 *)
Select[Range[16*10^6],PowerMod[3,#,#]==#-1&] (* Harvey P. Dale, Dec 15 2024 *)

for(n=1, 10^7, if(Mod(3, n)^n==-1, print1(n, ", "))) \\ Jinyuan Wang, Nov 01 2018

Corrected by David W. Wilson

A015963 Numbers k such that k | 13^k + 1.

Original entry on oeis.org

1, 2, 7, 10, 34, 49, 50, 170, 203, 250, 343, 578, 850, 1250, 1421, 2401, 2890, 4210, 4250, 5887, 6010, 6250, 6410, 9826, 9947, 11977, 14450, 16807, 21050, 21250, 30050, 31250, 32050, 34714, 41209, 49130, 69629, 71570, 72250, 83839, 102170

Offset: 1

Robert G. Wilson v

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..300

Solutions to 13^n == k (mod n): this sequence (k=-1), A116621 (k=1), A116622 (k=2), A116629 (k=3), A116630 (k=4), A116611 (k=5), A116631 (k=6), A116632 (k=7), A295532 (k=8), A116636 (k=9), A116620 (k=10), A116638 (k=11), A116639 (k=15).

Column k=13 of A333429.

Select[Range[102170], Divisible[13^# + 1, #] &] (* Robert Price, Apr 10 2020 *)

A015950 Numbers k such that k | 4^k + 1.

Original entry on oeis.org

1, 5, 25, 125, 205, 625, 1025, 2525, 3125, 5125, 8405, 12625, 15625, 25625, 42025, 63125, 78125, 103525, 128125, 168305, 202525, 210125, 255025, 315625, 344605, 390625, 517625, 640625, 841525, 875125, 1012625, 1050625, 1275125

Offset: 1

Robert G. Wilson v

nonn

From Robert Israel, Sep 14 2017: (Start)
All terms except 1 are congruent to 5 mod 20.
If k is a term and prime p | k, then k*p is a term.
All prime factors of terms == 1 (mod 4).
If p is a prime == 1 (mod 4) and the order of 4 (mod p) is 2*m where m is in the sequence, then m*p is in the sequence. (End)

			4^5 + 1 = 1025 and 1025 is divisible by 5, so 5 is a term.

Max Alekseyev, Table of n, a(n) for n = 1..3514 (first 325 terms from Robert Israel)

Cf. A015945, A211349.

Column k=4 of A333429.

[n: n in [1..10^6] | Modexp(4, n, n)+1 eq n]; // Jinyuan Wang, Dec 29 2018

select(n -> 4 &^ n + 1 mod n = 0, [1, seq(i,i=5..10^7,20)]); # Robert Israel, Sep 14 2017

Select[Prepend[20 Range[0, 10^5] + 5, 1], Mod[4^# + 1, #] == 0 &] (* Michael De Vlieger, Dec 31 2018 *)

is_A015950(n) = Mod(4,n)^n == -1; \\ Michel Marcus, Sep 15 2017

A015950_list = [n for n in range(1,10**6) if pow(4,n,n) == n-1] # Chai Wah Wu, Mar 25 2021

A015954 Numbers k such that k | 7^k + 1.

Original entry on oeis.org

1, 2, 10, 50, 250, 1250, 2810, 5050, 6250, 14050, 25250, 31250, 40210, 70250, 126250, 156250, 201050, 351250, 510050, 631250, 650050, 781250, 789610, 1005250, 1265050, 1419050, 1756250, 2550250, 3156250, 3250250, 3906250, 3948050, 5026250, 6325250, 7095250, 8781250, 9478130

Offset: 1

Robert G. Wilson v

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..100

Solutions to b^k == -1 (mod k): A006521 (b=2), A015949 (b=3), A015950 (b=4), A015951 (b=5), A015953 (b=6), this sequence (b=7), A015955 (b=8), A015957 (b=9), A015958 (b=10), A015960 (b=11), A015961 (b=12), A015963 (b=13), A015965 (b=14), A015968 (b=15), A015969 (b=16).
Cf. A277370, A277401.
Column k=7 of A333429.

A015960 Numbers k such that k | 11^k + 1.

Original entry on oeis.org

1, 2, 3, 9, 27, 81, 111, 122, 243, 333, 729, 999, 2187, 2997, 4107, 6561, 7442, 8991, 10233, 12321, 13203, 19683, 24753, 26973, 30699, 36963, 39609, 59049, 74259, 80919, 89426, 92097, 110889, 118341, 118827, 151959, 177147, 222777

Offset: 1

Robert G. Wilson v

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..200

Solutions to b^k == -1 (mod k): A006521 (b=2), A015949 (b=3), A015950 (b=4), A015951 (b=5), A015953 (b=6), A015954 (b=7), A015955 (b=8), A015957 (b=9), A015958 (b=10), this sequence (b=11), A015961 (b=12), A015963 (b=13), A015965 (b=14), A015968 (b=15), A015969 (b=16).
Cf. A333134.
Column k=11 of A333429.

Select[Range[250000],PowerMod[11,#,#]==#-1&] (* Harvey P. Dale, Nov 09 2022 *)

A015965 Numbers k such that k | 14^k + 1.

Original entry on oeis.org

1, 3, 5, 9, 15, 25, 27, 45, 75, 81, 125, 135, 171, 183, 225, 243, 355, 375, 405, 505, 513, 549, 625, 675, 729, 855, 915, 1065, 1125, 1215, 1515, 1539, 1647, 1775, 1875, 2025, 2187, 2525, 2565, 2745, 3125, 3195, 3249, 3375, 3645, 4275, 4545

Offset: 1

Robert G. Wilson v

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..3000

Column k=14 of A333429.

A015953 Numbers k such that k | 6^k + 1.

Original entry on oeis.org

1, 7, 49, 203, 343, 1379, 1421, 2401, 5887, 9653, 9947, 11977, 16807, 39991, 41209, 67571, 69629, 83839, 117649, 170723, 271663, 279937, 288463, 347333, 472997, 487403, 586873, 706643, 823543, 1159739, 1195061, 1901641, 1959559, 2019241, 2359469, 2431331

Offset: 1

Robert G. Wilson v

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..100

Solutions to b^k == -1 (mod k): A006521 (b=2), A015949 (b=3), A015950 (b=4), A015951 (b=5), this sequence (b=6), A015954 (b=7), A015955 (b=8), A015957 (b=9), A015958 (b=10), A015960 (b=11), A015961 (b=12), A015963 (b=13), A015965 (b=14), A015968 (b=15), A015969 (b=16).

Column k=6 of A333429.

Select[Range[2000000],PowerMod[6,#,#]==#-1&] (* Harvey P. Dale, Aug 28 2012 *)

A015955 Numbers k such that k | 8^k + 1.

Original entry on oeis.org

1, 3, 9, 27, 57, 81, 171, 243, 513, 729, 1083, 1539, 2187, 3249, 4401, 4617, 6561, 9747, 13203, 13851, 19683, 20577, 29241, 32547, 39609, 41553, 59049, 61731, 83619, 87723, 97641, 118179, 118827, 124659, 177147, 185193, 250857, 263169

Offset: 1

Robert G. Wilson v

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..200

Solutions to b^k == -1 (mod k): A006521 (b=2), A015949 (b=3), A015950 (b=4), A015951 (b=5), A015953 (b=6), A015954 (b=7), this sequence (b=8), A015957 (b=9), A015958 (b=10), A015960 (b=11), A015961 (b=12), A015963 (b=13), A015965 (b=14), A015968 (b=15), A015969 (b=16).

Column k=8 of A333429.

cp's OEIS Frontend

A006521 Numbers n such that n divides 2^n + 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Extensions

A015951 Numbers k such that k | 5^k + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

A015949 Numbers k such that k | 3^k + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Extensions

A015963 Numbers k such that k | 13^k + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A015950 Numbers k such that k | 4^k + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

A015954 Numbers k such that k | 7^k + 1.

Views

Author

Keywords

Links

Crossrefs

A015960 Numbers k such that k | 11^k + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A015965 Numbers k such that k | 14^k + 1.

Views

Author

Keywords