A019320 -id:A019320 - cp's OEIS frontend

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.

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

Offset: 1

Jens Voß, Sep 04 2001

nonn

By Zsigmondy's theorem, the n-th 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 (1867-1925). - Amiram Eldar, Jun 20 2021

			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.

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. 265-284.

Cf. A000225, A064079, A064080, A064081, A064082, A064083.

Cf. A019320, A063982.

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

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

Denominator of Sum_{d|n} d*moebius(n/d)/(2^d-1). - 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

More terms from Vladeta Jovovic, Apr 02 2004

Definition corrected by Jerry Metzger, Nov 04 2009

A054432 a(n) = Sum_{1<=k<=n, gcd(k,n)=1} 2^(k-1).

Original entry on oeis.org

1, 1, 3, 5, 15, 17, 63, 85, 219, 325, 1023, 1105, 4095, 5397, 13515, 21845, 65535, 70737, 262143, 333125, 890523, 1397077, 4194303, 4527185, 16236015, 22365525, 57521883, 88429845, 268435455, 272962625, 1073741823, 1431655765, 3679302363, 5726557525

Offset: 1

Antti Karttunen

nonn

For n>0, numbers formed by interpreting the reduced residue set of n (the rows of triangle A054431) as binary numbers.

			For n=6 we have k = 1 and 5 and then 2^0 + 2^4 = 17 = a(6).

Robert Israel, Table of n, a(n) for n = 1..2658

Cf. A054431, A054433, A001317, A054521.

rrs2bincode := proc(n) local i,z; z := 0; for i from 1 to n-1 do z := z*2; if (1 = igcd(n,i)) then z := z + 1; fi; od; RETURN(z); end;

f[n_] := Sum[2^k, {k, Select[ Range@ n, GCD[#, n] == 1 &] - 1}]; Array[f, 35] (* Robert G. Wilson v, Jul 21 2014 *)

a(n) = sum(k=1, n, if (gcd(k,n)==1, 2^(k-1), 0)); \\ Michel Marcus, Jul 20 2014

a(n) = subst(Polrev(vector(n, i, gcd(n, i)==1)), x, 2); \\ Michel Marcus, Jul 21 2014

M * V, where M = A054521 is an infinite lower triangular matrix and V = [1, 2, 4, 8, ...] is a vector. - Gary W. Adamson, Jan 13 2007
a(4*n) = (2^(2*n) + 1)*a(2*n) [think how the reduced residue set of the numbers of the form 4n are formed].
For all primes p and integers e > 1, A054432(p^e) = A019320(p^e)*(((2^(p^(e-1)))-1)* ((2^(p-1))-1))/((2^p)-1).
a(n-1) = Sum_{k=1..n, gcd(n, k) = 1} 2^(k-1). - Vladeta Jovovic, Aug 15 2002

Edited by N. J. A. Sloane, Jul 03 2008 at the suggestion of R. J. Mathar

More terms from Michel Marcus, Jul 20 2014

A051258 Fibocyclotomic numbers: numbers formed from cyclotomic polynomials and Fibonacci numbers (A000045).

Original entry on oeis.org

1, 1, 1, 2, 1, 7, 0, 20, 3, 10, 1, 143, 2, 376, 4, 11, 21, 2583, 6, 6764, 15, 74, 33, 46367, 18, 7435, 88, 2618, 104, 832039, 25, 2178308, 987, 3399, 609, 20160, 136, 39088168, 1596, 23228, 861, 267914295, 182, 701408732, 4895, 35920, 10945, 4807526975

Offset: 0

Antti Karttunen, Oct 24 1999

For all primes p, a(p) = fib(p+1)-1 and for all n of the form 2^i*p^j (where p is an odd prime and i >= 0 and j >= 2) fib(p)|a(2^i*p^j).

a(0) depends on how the zeroth cyclotomic polynomial is defined.

			a(22) = fib(10)-fib(9)+fib(8)-fib(7)+fib(6)-fib(5)+fib(4)-fib(3)+fib(2)-fib(1) = 33 as the 22nd cyclotomic polynomial is x^10-x^9+x^8-x^7+x^6-x^5+x^4-x^3+x^2-x+1 (The constant term does not affect the result, as fib(0)=0.)

T. D. Noe, Table of n, a(n) for n = 0..500

Cf. A019320, A054433, A063704, A063706, A063708.

get_coefficient := proc(e); if(1 = nops(e)) then if(`integer` = op(0,e)) then RETURN(e); else RETURN(1); fi; else if(2 = nops(e)) then if(`*` = op(0,e)) then RETURN(op(1,e)); else RETURN(1); fi; else RETURN(`Cannot find coefficient!`); fi; fi; end;
get_exponent := proc(e); if((1 = e) or (-1 = e)) then RETURN(0); else if(1 = nops(e)) then RETURN(1); else if(2 = nops(e)) then if(`^` = op(0,e)) then RETURN(op(2,e)); else RETURN(get_exponent(op(2,e))); fi; else RETURN(`Cannot find exponent!`); fi; fi; fi; end;
fibo_cyclotomic := proc(j) local i,p; p := sort(cyclotomic(j,x)); RETURN(add((get_coefficient(op(i,p))*fibonacci(get_exponent(op(i,p)))),i=1..nops(p))); end;

f[n_]:=Module[{cy=CoefficientList[Cyclotomic[n,x],x]},Total[ Times@@@ Thread[ {Fibonacci[ Range[0, Length[cy]- 1]],cy}]]]; Join[{1},Array[f,50]] (* Harvey P. Dale, Oct 02 2011 *)

a(n)=my(P=polcyclo(n));sum(i=1,poldegree(P),polcoeff(P,i)*fibonacci(i)) \\ Charles R Greathouse IV, Jan 05 2013

a(n) = Sum (coefficient_of_term_i_of_cp_n times Fib(exponent_of_term_i_of_cp_n)), i=1..degree of cp_n, where cp_n is the n-th cyclotomic polynomial.

A051156 a(n) = (2^p^2 - 1)/(2^p - 1) where p is the n-th prime.

Original entry on oeis.org

5, 73, 1082401, 4432676798593, 1298708349570020393652962442872833, 91355004067076339167413824240109498970069278721, 7588608256743087977590500540116743445925584618982806531428980886590618779326218241

Offset: 1

N. J. A. Sloane

Note that a(n) = Phi(p,2^p) or a(n) = Phi(p^2,2), where Phi(m,x) is the m-th cyclotomic polynomial and p is the n-th prime. - Thomas Ordowski, Feb 18 2014

Cf. A051154, A051155, A051157.

Table[Cyclotomic[Prime[n]^2, 2], {n, 7}] (* Arkadiusz Wesolowski, May 13 2012 *)
Table[(2^Prime[n]^2-1)/(2^Prime[n]-1),{n,10}] (* Harvey P. Dale, Apr 06 2019 *)

a(n) = A070526(prime(n)), a(n) = A019320(prime(n)^2). - Thomas Ordowski, Feb 18 2014

A217465 Composite integers k such that 2^k == 2 (mod k*(k+1)).

Original entry on oeis.org

561, 1905, 4033, 4681, 5461, 6601, 8481, 11305, 13741, 13981, 16705, 23377, 30121, 31417, 41041, 49141, 52633, 57421, 88357, 88561, 101101, 107185, 121465, 130561, 162193, 196021, 196093, 204001, 208465, 219781, 266305, 276013, 278545, 282133, 285541, 314821, 334153, 341497, 390937, 399001

Offset: 1

V. Raman, Oct 04 2012

nonn

Terms A019320(k) belongs to this sequence for k in A297415. - Max Alekseyev, Dec 29 2017

Amiram Eldar, Table of n, a(n) for n = 1..12766 (terms below 10^12; terms 1..100 from Harvey P. Dale)
Mersenne Forum, Prime Conjecture, 2012.

Subsequence of A216822.
Contains A303531 as a subsequence.
Cf. A019320, A217466, A217468, A297415, A298758.

Select[Range[400000],!PrimeQ[#]&&PowerMod[2,#,#(#+1)]==2&] (* Harvey P. Dale, Oct 12 2012 *)

for(n=1,10000,if((2^n)%(n*(n+1))==2&&isprime(n)==0,printf(n",")))

forcomposite(n=4,10^6, if(Mod(2,n*(n+1))^n==2, print1(n", "))) \\ Charles R Greathouse IV, Aug 29 2024

from sympy import isprime
A217465_list = [n for n in range(1,10**6) if pow(2,n,n*(n+1)) == 2 and not isprime(n)] # Chai Wah Wu, Mar 25 2021

A217468 Composite values of n such that 2^n == 2 (mod n*(n-1)).

Original entry on oeis.org

91625794219, 8796093022207, 1557609722332488343, 18216643597893471403

Offset: 1

V. Raman, Oct 04 2012

No other terms below 2^64.
The next term is <= 25790417485109157029391019 = A019320(258). - Emmanuel Vantieghem, Dec 01 2014
Terms A019320(k) belongs to this sequence for k in A297412. - Max Alekseyev, Dec 29 2017

			a(1) = 91625794219 = (2^38 - 2^19 + 1)/3 = A019320(114).
a(2) = 8796093022207 = 2^43 - 1 = A019320(43).

Mersenne Forum, Prime Conjecture

Cf. A069051, A216822, A219037, A217465.

Intersection of A001567 and { 2*A014945(k) + 1 }.

is_A217468(n)={Mod(2,(n-1)*n)^n==2 & !isprime(n)}  \\ - M. F. Hasler, Oct 07 2012

A019326 Cyclotomic polynomials at x=8.

Original entry on oeis.org

8, 7, 9, 73, 65, 4681, 57, 299593, 4097, 262657, 3641, 1227133513, 4033, 78536544841, 233017, 14709241, 16777217, 321685687669321, 261633, 20587884010836553, 16519105, 60247241209, 954437177, 84327972908386521673, 16773121, 1152956690052710401, 61083979321

Offset: 0

Simon Plouffe

nonn

Paolo Xausa, Table of n, a(n) for n = 0..1000
Index entries for cyclotomic polynomials, values at X

Cf. A020500 (x = 1), A019320-A019331 (x = 2..13).

with(numtheory,cyclotomic); f := n->subs(x=8,cyclotomic(n,x)); seq(f(i),i=0..64);

Join[{8}, Cyclotomic[Range[50], 8]] (* Paolo Xausa, Feb 26 2024 *)

a(n) = if (n==0, 8, polcyclo(n, 8)); \\ Michel Marcus, Aug 07 2021

from sympy.polys.specialpolys import cyclotomic_poly
def a(n): return 8 if n == 0 else cyclotomic_poly(n, x=8)
print([a(n) for n in range(27)]) # Michael S. Branicky, Aug 07 2021

A020501 Cyclotomic polynomials at x=-2.

Original entry on oeis.org

-2, -3, -1, 3, 5, 11, 7, 43, 17, 57, 31, 683, 13, 2731, 127, 331, 257, 43691, 73, 174763, 205, 5419, 2047, 2796203, 241, 1016801, 8191, 261633, 3277, 178956971, 151, 715827883, 65537, 1397419, 131071, 24214051

Offset: 0

Simon Plouffe

sign

a(0) depends on the definition of the 0th cyclotomic polynomial; Maple defines it as x, but Mathematica defines it as 1. - T. D. Noe, Jul 23 2008 [a(0) = x is correct. - N. J. A. Sloane, Aug 01 2008]

A020501[2n] = A019320[n] for all odd n > 1. (Because if m > 1 is odd, then Phi_2m(x) = Phi_m(-x) as demonstrated by Bloom). - Antti Karttunen, Aug 02 2001

T. D. Noe, Table of n, a(n) for n = 0..1000
D. M. Bloom, On the Coefficients of the Cyclotomic Polynomials, Amer.Math.Monthly 75, 372-377, 1968.
Index entries for cyclotomic polynomials, values at X

Cf. A020500, A020513.

Cf. A105603

with(numtheory,cyclotomic); f := n->subs(x=-2,cyclotomic(n,x)); seq(f(i),i=0..64);

Join[{-2}, Cyclotomic[Range[50], -2]] (* Paolo Xausa, Feb 26 2024 *)

a(n) = if (n, polcyclo(n, -2), -2); \\ Michel Marcus, Mar 05 2016

A063698 Positions of negative coefficients in cyclotomic polynomial Phi_n(x), converted from binary to decimal. (The constant term in the least significant bit (bit-0), the term x in the next bit (bit-1) and so on).

Original entry on oeis.org

0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 10, 0, 4, 0, 42, 146, 0, 0, 8, 0, 68, 2322, 682, 0, 16, 0, 2730, 0, 1092, 0, 56, 0, 0, 599186, 43690, 8726850, 64, 0, 174762, 9585810, 4112, 0, 792, 0, 279620, 2101256, 2796202, 0, 256, 0, 32800, 2454267026, 4473924, 0, 512

Offset: 0

Antti Karttunen, Aug 03 2001

nonn

Maple procedures Phi_pos_terms and Phi_neg_terms are modeled after the formula given in Lam and Leung paper and they compute correct results for all integers x > 1 and for all n with at most two distinct odd prime factors (that is, up to n=104). Other procedures as in A063696 and A063694.

Antti Karttunen, Table of n, a(n) for n = 0..3003
D. M. Bloom, On the Coefficients of the Cyclotomic Polynomials, Amer.Math.Monthly 75, 372-377, 1968.
T.Y. Lam and K. H. Leung, On the Cyclotomic Polynomial Phi_pq(X), Amer.Math.Monthly 103, 562-564, August-September 1996.
H. Lenstra, Vanishing sums of roots of unity, in Proc. Bicentennial Congress Wiskundig Genootschap (Vrije Univ. Amsterdam, 1978), Part II, pp. 249-268.
Index entries for cyclotomic polynomials, positions of coefficients

A013594, A063696 gives the positions of the positive and A063697 the nonzero terms. This sequence in binary: A063699. A019320[n] = A063696[n]-A063698[n] for up to n=104

with(numtheory); [seq(Phi_neg_terms(j,2),j=0..104)];
Phi_neg_terms := proc(n,x) local a,m,p,q,e,f,r,s; if(n < 2) then RETURN(n); fi; a := op(2, ifactors(n)); m := nops(a); p := a[1][1]; e := a[1][2]; if(1 = m) then RETURN(0); fi; if(2 = m) then q := a[2][1]; f := a[2][2]; r := inv_p_mod_q(p,q)-1; s := inv_p_mod_q(q,p)-1;
RETURN( x^((s+1)*(q^f)*(p^(e-1))) * x^((r+1)*(p^e)*(q^(f-1))) * x^(-((p^e) * (q^f))) * (`if`((p-2)=s,1,(((x^((p-s-1)*((q^f)*(p^(e-1)))))-1)/((x^((q^f)*(p^(e-1))))-1)))) * (`if`((q-2)=r,1,(((x^((q-r-1)*((p^e)*(q^(f-1)))))-1)/((x^((p^e)*(q^(f-1))))-1)))) ); fi;
if((3 = m) and (2 = p)) then if(1 = e) then RETURN(every_other_pos(Phi_neg_terms(n/2,x),x,0)+every_other_pos(Phi_pos_terms(n/2,x),x,1)); else RETURN(dilate(Phi_neg_terms((n/(2^(e-1))),x),x,2^(e-1))); fi; else printf(`Cannot handle argument %a with >=3 distinct odd prime factors!\n`,n); RETURN(0); fi; end;

a[n_] := 2^(Flatten[Position[CoefficientList[Cyclotomic[n, x], x], ?Negative]] - 1) // Total; a[0] = 0; Table[a[n], {n, 0, 60}] (* _Jean-François Alcover, Mar 05 2016 *)

a(n)=my(p); if(n<1, 0, p=polcyclo(n); sum(i=0, n, 2^i*(polcoeff(p, i)<0))) \\ Michel Marcus, Mar 05 2016

A034268 a(n) = LCM_{k=1..n} (2^k - 1).

Original entry on oeis.org

1, 3, 21, 105, 3255, 9765, 1240155, 21082635, 1539032355, 16929355905, 34654391537535, 450507089987955, 3690103574091339405, 158674453685927594415, 23959842506575066756665, 6157679524189792156462905, 807093212915080247739749421255

Offset: 1

Jeffrey Shallit, Apr 20 2000

nonn

			a(3) = lcm(1,3,7) = 21.

Alois P. Heinz, Table of n, a(n) for n = 1..100
Gert Almkvist, Powers of a matrix with coefficients in a Boolean ring, Proc. Amer. Math. Soc. 53 (1975), 27-31. See v_n.
J. B. Marshall, On the extension of Fermat's theorem to matrices of order n, Proceedings of the Edinburgh Mathematical Society 6 (1939) 85-91. See (10) page 90 for p=2.
MathOverflow, Do we know any bound on lcm(2^1-1, 2^2-1, ..., 2^n-1)?

Cf. A003418, A019320, A051844.

[Lcm([2^k-1:k in [1..n]]): n in [1..17]]; // Marius A. Burtea, Jan 29 2020

a:= proc(n) option remember; `if`(n=1, 1, ilcm(a(n-1), 2^n-1)) end:
seq(a(n), n=1..20);  # Alois P. Heinz, Oct 16 2011

Table[LCM @@ (2^Range[n] - 1), {n, 1, 20}] (* Jean-François Alcover, Apr 02 2015 *)

A034268(n) = {local(r);r=1;for(k=1,n,r=lcm(r,2^k-1));r} \\ Michael B. Porter, Mar 02 2010

a(n) = lcm(vector(n, k, 2^k-1)); \\ Michel Marcus, Jul 29 2022

from math import lcm
from itertools import accumulate
def aupto(n): return list(accumulate((2**k-1 for k in range(1, n+1)), lcm))
print(aupto(17)) # Michael S. Branicky, Jul 04 2022

a(n) = lcm(1, 3, 7, ..., 2^n - 1).

a(n) = Product_{k=1..n} Phi_k(2), where Phi_n(2) is n-th cyclotomic polynomial at x=2 (cf. A019320). - Vladeta Jovovic, Jan 20 2002

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A054432 a(n) = Sum_{1<=k<=n, gcd(k,n)=1} 2^(k-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A051258 Fibocyclotomic numbers: numbers formed from cyclotomic polynomials and Fibonacci numbers (A000045).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A051156 a(n) = (2^p^2 - 1)/(2^p - 1) where p is the n-th prime.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A217465 Composite integers k such that 2^k == 2 (mod k*(k+1)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

A217468 Composite values of n such that 2^n == 2 (mod n*(n-1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A019326 Cyclotomic polynomials at x=8.

Views

Author

Keywords

Links

Crossrefs

Programs