

A064078


Zsigmondy numbers for a = 2, b = 1: Zs(n, 2, 1) is the greatest divisor of 2^n  1 (A000225) that is coprime to 2^m  1 for all positive integers m < n.


23



1, 3, 7, 5, 31, 1, 127, 17, 73, 11, 2047, 13, 8191, 43, 151, 257, 131071, 19, 524287, 41, 337, 683, 8388607, 241, 1082401, 2731, 262657, 3277, 536870911, 331, 2147483647, 65537, 599479, 43691, 8727391, 4033, 137438953471, 174763, 9588151, 61681
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

By Zsigmondy's theorem, the nth Zsigmondy number for bases a and b is not 1 except in the three cases (1) a = 2, b = 1, n = 1, (2) a = 2, b = 1, n = 6, (3) n = 2 and a + b is a power of 2.
Composite terms are the maximal overpseudoprimes to base 2 (see A141232) for which the multiplicative order of 2 mod a(n) equals n.  Vladimir Shevelev, Aug 26 2008
a(n) = 2^n  1 if and only if either n = 1 or n is prime.  Vladimir Shevelev, Sep 30 2008
a(n) == 1 (mod n), 2^(a(n)1) == 1 (mod a(n)), A002326((a(n)1)/2) = n.  Thomas Ordowski, Oct 25 2017
If n is odd, then the prime factors of a(n) are congruent to {1,7} mod 8, that is, they have 2 has a quadratic residue, and are congruent to 1 mod 2n. If n is divisible by 8, then the prime factors of a(n) are congruent to 1 mod 16.  Jianing Song, Apr 13 2019
Named after the Austrian mathematician Karl Zsigmondy (18671925).  Amiram Eldar, Jun 20 2021


LINKS

T. D. Noe, Table of n, a(n) for n=1..1000
Wikipedia, Zsigmondy's theorem.
Karl Zsigmondy, Zur Theorie der Potenzreste, Monatshefte für Mathematik, Vol. 3 (1892), pp. 265284.


FORMULA

Denominator of Sum_{dn} d*moebius(n/d)/(2^d1).  Vladeta Jovovic, Apr 02 2004
a(n) = A019320(n)/gcd(n, A019320(n)).  T. D. Noe, Apr 13 2010
a(n) = A019320(n)/(A019320(n) mod n) for n > 1.  Thomas Ordowski, Oct 24 2017


EXAMPLE

a(4) = 5 because 2^4  1 = 15 and its divisors being 1, 3, 5, 15, only 1 and 5 are coprime to 2^2  1 = 3 and 2^3  1 = 7, and 5 is the greater of these.
a(5) = 31 because 2^5  1 = 31 is prime.
a(6) = 1 because 2^6  1 = 63 and its divisors being 1, 3, 7, 9, 21, 63, only 1 is coprime to all of 3, 7, 15, 31.


MATHEMATICA

Table[Cyclotomic[n, 2]/GCD[n, Cyclotomic[n, 2]], {n, 40}] (* Alonso del Arte, Mar 14 2013 *)


PROG

(PARI) a(n) = my(m = polcyclo(n, 2)); m/gcd(m, n); \\ Michel Marcus, Mar 07 2015


CROSSREFS

Cf. A000225, A064079, A064080, A064081, A064082, A064083.
Cf. A019320, A063982.
Sequence in context: A046561 A112927 A097406 * A292015 A342660 A186522
Adjacent sequences: A064075 A064076 A064077 * A064079 A064080 A064081


KEYWORD

nonn,changed


AUTHOR

Jens Voß, Sep 04 2001


EXTENSIONS

More terms from Vladeta Jovovic, Apr 02 2004
Definition corrected by Jerry Metzger, Nov 04 2009


STATUS

approved



