cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

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

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

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

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

Crossrefs

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.

Programs

  • Haskell
    a006521 n = a006521_list !! (n-1)
a006521_list = filter (\x -> a000051 x `mod` x == 0) [1..]
-- Reinhard Zumkeller, Jul 17 2014
  • Magma
    [n: n in [1..6*10^5] | (2^n+1) mod n eq 0 ]; // Vincenzo Librandi, Dec 14 2018
  • 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 *)
  • 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

Extensions

More terms from David W. Wilson, Jul 06 2009

A057719 Prime factors of numbers in A006521 (numbers k that divide 2^k + 1).

Original entry on oeis.org

3, 19, 163, 571, 1459, 8803, 9137, 17497, 41113, 52489, 78787, 87211, 135433, 139483, 144667, 164617, 174763, 196579, 274081, 370009, 370387, 478243, 760267, 941489, 944803, 1041619, 1220347, 1236787, 1319323, 1465129, 1663579, 1994659
Offset: 1

Views

Author

Ignacio Larrosa Cañestro, Oct 26 2000

Keywords

Comments

A prime p is in this sequence iff all prime divisors of ord_p(2)/2 are in this sequence, where ord_p(2) is the order of 2 modulo p. - Max Alekseyev, Jul 30 2006

Examples

			2^171 + 1 == 0 (mod 171), 171 = 3^2*19, 2^13203+1 == 0 (mod 13203), 13203 = 3^4*163.

Links

Crossrefs

Cf. A006521, A066364.
Cf. A136474, A136473.

Programs

  • Mathematica
    S = {2}; Reap[For[p = 3, p < 2 10^6, p = NextPrime[p], f = FactorInteger[ MultiplicativeOrder[2, p]]; If[f[[1, 1]] != 2 || f[[1, 2]] != 1, Continue[]]; f = f[[All, 1]]; If[Length[Intersection[S, f]] == Length[f], S = Union[S, {p}]; Print[p]; Sow[p]]]][[2, 1]] (* Jean-François Alcover, Nov 11 2018, from PARI *)
  • PARI
    { A057719() = local(S,f); S=Set([2]); forprime(p=3,10^7, f=factorint(znorder(Mod(2,p))); if(f[1,1]!=2||f[1,2]!=1,next); f=f[,1]; if(length(setintersect(S,Set(f)))==length(f), S=setunion(S,[p]); print1(p,", "))) }

Extensions

Edited by Max Alekseyev, Jul 30 2006

A136474 Primes that divide 2^(3^n)+1 for some n.

Original entry on oeis.org

3, 19, 163, 1459, 17497, 52489, 87211, 135433, 139483, 1220347, 5419387, 6049243, 28934011, 86093443, 227862073, 272010961
Offset: 1

Views

Author

Christopher J. Smyth, Feb 16 2008

Keywords

Comments

This sequence is a subsequence of A057719.
272010961 is the last term less than 3*10^9. The n for each prime is 0, 2, 4, 5, 7, 8, 3, 4, 5, 9, 7, 7, 8, 16, 6, 4. Some terms from A111974 are in this sequence also: 411782264189299, 116299474006080119380780339, and 84782316550432407028588866403. If p=2*3^k+1 is prime for an even k, then p is in this sequence.

Examples

			1220347 belongs to the sequence as it is a factor of 2^(3^9)+1 (This is the largest member of the sequence less than 5000000)

Crossrefs

Cf. A057719, A136475, A005621, A136473.

Programs

  • Maple
    with(numtheory):L:=3;for p from 5 to 5000000 do if isprime(p) then q:=op(2,ifactors(order(2,p)));if nops(q)=2 then if op(1,op(1,q))=2 and op(2,op(1,q))=1 and op(1,op(2,q))=3 then L:=L,p;fi;fi;fi;od;L;
  • Mathematica
    Reap[Do[p=Prime[n]; mo=MultiplicativeOrder[2, p]; If[EvenQ[mo] && IntegerQ[Log[3,mo/2]], Sow[p]], {n, PrimePi[10^7]}]][[2,1]]

A136475 Irregular triangle read by rows: row n gives prime factors of (2^(3^(n+1))+1)/(2^(3^n)+1).

Original entry on oeis.org

3, 3, 19, 3, 87211, 3, 163, 135433, 272010961, 3, 1459, 139483, 10429407431911334611, 918125051602568899753, 3, 227862073, 3110690934667, 216892513252489863991753, 1102099161075964924744009, 393063301203384521164229656203691748263012766081190297429488962985651210769817
Offset: 0

Views

Author

Christopher J. Smyth, Feb 16 2008

Keywords

Comments

1. The motivation for this sequence is to quickly generate integers n such that n divides 2^n+1 (sequences A006521, A136473). From the link, it is known that if 3^k||n with n|2^n+1 and n not a power of 3, then n is divisible by a prime p dividing 2^(3^k)+1. Thus for any fixed k every n with n|2^n+1 not a power of 3 is divisible by one of the following numbers: 3^k or some 3^j*p, where p>3 is a prime in A136475 before the k-th '3' and j is the number of '3's before p in the sequence.
2. Note: (2^(3^(k+1))+1)/(2^(3^k)+1) = 2^(2*3^k) - 2^(3^k) + 1.
3. For the primes dividing 2^(3^k)+1 for some k see A136474.
4. Are these numbers always squarefree?

Examples

			1. (2^(3^4)+1)/(2^(3^3)+1) = 3*163*135433*272010961, the factorization starting at the 4th '3' and ending just before the 5th '3'.
2. From Comment 1 below and k=5, we see that every n not a power of 3 satisfying n|2^n+1 (sequences A006521, A136473) is divisible by 3^5 or 3^2*19 or 3^3*87211 or 3^4*163 or 3^4*135433 or 3^4*272010961.

Links

Crossrefs

Cf. A006521, A136473, A136474.

Programs

  • Maple
    S:=[];for k from 0 to 4 do f:=op(2,ifactors((2^(3^(k+1))+1)/(2^(3^k)+1)));T:=[];for j to nops(f) do T:=[op(T),op(1,op(j,f))];od;S:=[op(S),op(sort(T))];od;op(S);

Formula

The prime factors of (2^(3^(k+1))+1)/(2^(3^k)+1) are given in ascending order *for each k*. For each new value of k the factorization starts with a '3', thus delimiting the different factorizations.
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.