A064078 -id:A064078 - cp's OEIS frontend

A109347 Zsigmondy numbers for a = 5, b = 3: Zs(n, 5, 3) is the greatest divisor of 5^n - 3^n (A005058) that is relatively prime to 5^m - 3^m for all positive integers m < n.

2, 1, 49, 17, 1441, 19, 37969, 353, 19729, 421, 24325489, 481, 609554401, 10039, 216001, 198593, 381405156481, 12979, 9536162033329, 288961, 18306583, 6125659, 5960417405949649, 346561, 103408180634401, 152787181, 3853528045489, 179655841, 93132223146359169121

Offset: 1

Jonathan Vos Post, Aug 21 2005

nonn

Eric Weisstein's World of Mathematics, Zsigmondy's Theorem

Cf. A064078, A064079, A064080, A064081, A064082, A064083, A109325, A109348, A109349.

rad(n) = factorback(factor(n)[, 1])
lista(nn) = {prad = 1; for (n=1, nn, val = 5^n-3^n; d = divisors(val); gd = 1; forstep(k=#d, 1, -1, if (gcd(d[k], prad) == 1, g = d[k]; break)); print1(g, ", "); prad = ra(prad*val););} \\ Michel Marcus, Nov 15 2016

Edited, corrected and extended by Ray Chandler, Aug 26 2005
Definition corrected by Jerry Metzger, Nov 04 2009
More terms from Michel Marcus, Nov 14 2016

A144755 Primes which divide none of overpseudoprimes to base 2 (A141232).

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 17, 19, 31, 41, 43, 73, 127, 151, 241, 257, 331, 337, 683, 2731, 5419, 8191, 43691, 61681, 65537, 87211, 131071, 174763, 262657, 524287, 599479, 2796203, 15790321, 18837001, 22366891, 715827883, 2147483647, 4278255361

Offset: 1

Vladimir Shevelev, Sep 20 2008

nonn

Odd prime p is in the sequence iff A064078(A002326((p-1)/2))=p. For example, for p=127 we have A002326((127-1)/2)=7 and A064078(7)=127. Thus p=127 is in the sequence.
Primes p such that the binary expansion of 1/p has a unique period length; that is, no other prime has the same period. Sequence A161509 sorted. - T. D. Noe, Apr 13 2010
Since A161509 has terms of varying magnitude, sorting any finite initial segment of A161509 cannot provide a guarantee that there are no other terms missed in between. Any prime p not (yet) appearing in A161509 should be tested via A064078(A002326((p-1)/2))=p to conclude whether it belongs to the current sequence. - Max Alekseyev, Feb 10 2024

			Overpseudoprimes to base 2 are odd, then a(1)=2.

Cf. A141232, A002326, A064078, A112927.

Cf. A040017 (unique-period primes in base 10). - T. D. Noe, Apr 13 2010

b=2; t={}; Do[c=Cyclotomic[n,b]; q=c/GCD[n,c]; If[PrimePowerQ[q], p=FactorInteger[q][[1,1]]; If[p<10^12, AppendTo[t,p]; Print[{n,p}]]], {n,1000}]; t=Sort[t] (* T. D. Noe, Apr 13 2010 *)

{ is_a144755(p) = my(q,m,g); q=znorder(Mod(2,p)); m=2^q-1; fordiv(q,d, if(d1,m\=g))); m==p; } \\ Max Alekseyev, Feb 10 2024

Extended by T. D. Noe, Apr 13 2010

b-file deleted by Max Alekseyev, Feb 10 2024.

A161508 Numbers k such that 2^k-1 has only one primitive prime factor.

Original entry on oeis.org

2, 3, 4, 5, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 26, 27, 30, 31, 32, 33, 34, 38, 40, 42, 46, 49, 54, 56, 61, 62, 65, 69, 77, 78, 80, 85, 86, 89, 90, 93, 98, 107, 120, 122, 126, 127, 129, 133, 145, 147, 150, 158, 165, 170, 174, 184, 192, 195, 202, 208

Offset: 1

T. D. Noe, Jun 17 2009

nonn

Also, numbers k such that A086251(k) = 1.
Also, numbers k such that A064078(k) is a prime power.
The corresponding primitive primes are listed in A161509.
The binary expansion of 1/p has period k and this is the only prime with such a period. The binary analog of A007498.
This sequence has many terms in common with A072226. A072226 has the additional term 6; but it does not have terms 18, 20, 21, 54, 147, 342, 602, and 889 (less than 10000).
All known terms that are not in A072226 belong to A333973.

T. D. Noe, Table of n, a(n) for n=1..179
Wikipedia, Unique prime, section Binary unique primes.

Cf. A007498, A064078, A072226, A086251, A144755, A161509, A247071, A333973.

Select[Range[1000], PrimePowerQ[Cyclotomic[ #,2]/GCD[Cyclotomic[ #,2],# ]]&]

is_A161508(n) = my(t=polcyclo(n,2)); isprimepower(t/gcd(t,n)); \\ Charles R Greathouse IV, Nov 17 2014

A064082 Zsigmondy numbers for a = 6, b = 1: Zs(n, 6, 1) is the greatest divisor of 6^n - 1^n (A024062) that is relatively prime to 6^m - 1^m for all positive integers m < n.

Original entry on oeis.org

5, 7, 43, 37, 311, 31, 55987, 1297, 46873, 1111, 72559411, 1261, 2612138803, 5713, 1406371, 1679617, 3385331888947, 46441, 121871948002099, 1634221, 1822428931, 51828151, 157946044610720563, 1678321, 731325737104301

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.

K. Zsigmondy, Zur Theorie der Potenzreste, Monatsh. f. Math. 3 (1892) 265-284.

Cf. A024062, A064078, A064079, A064080, A064081, A064083.

More terms from Vladeta Jovovic, Sep 06 2001

Definition corrected by Jerry Metzger, Nov 04 2009

A093106 Numbers k such that the k-th cyclotomic polynomial evaluated at 2 (=A019320(k)) is not coprime to k.

Original entry on oeis.org

6, 18, 20, 21, 54, 100, 110, 136, 147, 155, 156, 162, 253, 342, 486, 500, 602, 657, 812, 820, 889, 979, 1029, 1081, 1210, 1332, 1458, 2028, 2265, 2312, 2485, 2500, 2756, 3081, 3164, 3422, 3660, 3924, 4112, 4374, 4422, 4656, 4805, 5253, 5784, 5819, 6498

Offset: 1

Ralf Stephan, Mar 20 2004

nonn

Also, numbers k such that the Zsigmondy number Zs(k, 2, 1) differs from the k-th cyclotomic polynomial evaluated at 2, i.e., A064078(k) differs from A019320(k).

Numbers k > 0 such that A019320(k) is not congruent to 1 mod k. These numbers are of the form k = p^j * A002326((p-1)/2), where p is an odd prime and j > 0. Then A019320(k) mod k = gcd(A019320(k), k) = A019320(k) / A064078(k) = p. - Thomas Ordowski, Oct 07 2017

Jeppe Stig Nielsen, Table of n, a(n) for n = 1..51350

Cf. A093107, A093108, A093109.

Select[Range[10000],GCD[#,Cyclotomic[#,2]]!=1 &] (* Emmanuel Vantieghem, Nov 13 2016 *)

isok(k) = gcd(polcyclo(k, 2), k) != 1; \\ Michel Marcus, Oct 07 2017

upto(K)=li=List();forprime(p=3,K*log(2)/log(K+1),r=znorder(Mod(2,p))*p;while(r<=K,listput(li,r);r*=p));Set(li) \\ Jeppe Stig Nielsen, Sep 10 2020

More terms from Vladeta Jovovic, Apr 03 2004
Definition corrected by Jerry Metzger, Nov 04 2009
Edited by Max Alekseyev, Oct 23 2017

A097406 Largest primitive prime factor of 2^n-1, or a(n) = 1 if no such prime exists.

Original entry on oeis.org

1, 3, 7, 5, 31, 1, 127, 17, 73, 11, 89, 13, 8191, 43, 151, 257, 131071, 19, 524287, 41, 337, 683, 178481, 241, 1801, 2731, 262657, 113, 2089, 331, 2147483647, 65537, 599479, 43691, 122921, 109, 616318177, 174763, 121369, 61681, 164511353, 5419

Offset: 1

Marco Matosic, Aug 16 2004

By Zsigmondy's theorem, a(n) > 1 except for n = 1 or 6.
Conjectures: (1) For every n the highest unique prime factor is of the form kn+1. The values for k are in A097407. (2) For each composite n many factors of the form kn+1 occur intermittently but always singly in any cofactor pair. (3) For each prime n every factor is of the form kn+1.
A prime factor of 2^n-1 is called primitive if it does not divide 2^r-1 for any rA086251.
a(n) is the greatest prime such that the multiplicative order of 2 mod a(n) equals n, or a(n)=1 if no such prime exists. - Jianing Song, Oct 23 2019

Max Alekseyev, Table of n, a(n) for n = 1..1206

Cf. A064078, A097407.

For the smallest primitive prime factor of 2^n-1 see A112927.

isprimitive(p, n) = {for (r=1, n-1, if (((2^r-1) % p) == 0, return (0));); return (1);}
a(n) = {f = factor(2^n-1); forstep(i=#f~, 1, -1, if (isprimitive(f[i, 1], n), return (f[i, 1]));); return (1);} \\ Michel Marcus, Jul 15 2013

a(n) = A006530(A064078(n)). - Jianing Song, Oct 23 2019

More terms and better description from Vladeta Jovovic, Sep 03 2004

a(1) and a(6) changed from 0 to 1 by Jianing Song, Oct 23 2019

A109325 Zsigmondy numbers for a = 3, b = 2: Zs(n, 3, 2) is the greatest divisor of 3^n - 2^n (A001047) that is relatively prime to 3^m - 2^m for all positive integers m < n.

Original entry on oeis.org

1, 5, 19, 13, 211, 7, 2059, 97, 1009, 11, 175099, 61, 1586131, 463, 3571, 6817, 129009091, 577, 1161737179, 4621, 267331, 35839, 94134790219, 5521, 4015426801, 320503, 397760329, 369181, 68629840493971, 7471, 617671248800299, 43112257

Offset: 1

Gottfried Helms, Aug 09 2005

nonn

The full factorization is multiplicative; meaning that the composition of factors is determined by the prime-factorization of n.

			Let n be 7; then the factorization of g(n) := 3^n-2^n is then g(7) = A(7) = 2059 since n is prime; let n be 3 then the factorization of g(3) = A(3) = 19 since n is prime; let n be 21, then the factorization is g(21) = A(3)*A(7)*A(21); and whether n is composite or not, with each n (at least) one new factor occurs besides the factors determined by the prime factors of n - so it is not purely multiplicative.

N. Bliss, B. Fulan, S. Lovett, and J. Sommars, Strong Divisibility, Cyclotomic Polynomials, and Iterated Polynomials, Amer. Math. Monthly, 120 (2013), 519-536.
Eric Weisstein's World of Mathematics, Zsigmondy's Theorem

Cf. A064078-A064083, A109347, A109348, A109349, A001047.

f:=proc(a,M) local n,b,d,t1,t2;
b:=[];
for n from 1 to M do
t1:=divisors(n);
t2:=mul(a[d]^mobius(n/d), d in t1);
b:=[op(b),t2];
od;
b;
end; a:=[seq(3^n-2^n,n=1..50)];
f(a,50); #  N. J. A. Sloane, Jun 07 2013

a(n) = Product_{d|n} b(d)^Moebius(n/d), where b() = A001047(). - N. J. A. Sloane, Jun 07 2013

Edited and extended by Ray Chandler, Aug 26 2005

A109348 Zsigmondy numbers for a = 7, b = 3: Zs(n, 7, 3) is the greatest divisor of 7^n - 3^n that is relatively prime to 7^m - 3^m for all positive integers m < n.

Original entry on oeis.org

4, 5, 79, 29, 4141, 37, 205339, 1241, 127639, 341, 494287399, 2041, 24221854021, 82573, 3628081, 2885681, 58157596211761, 109117, 2849723505777919, 4871281, 8607961321, 197750389, 6842186811484434379, 5576881, 80962848274370701

Offset: 1

Jonathan Vos Post, Aug 21 2005

nonn

Eric Weisstein's World of Mathematics, Zsigmondy's Theorem

Cf. A064078-A064083, A109325, A109347, A109349.

Edited, corrected and extended by Ray Chandler, Aug 26 2005

Definition corrected by Jerry Metzger, Nov 04 2009

A109349 Zsigmondy numbers for a = 7, b = 5: Zs(n, 7, 5) is the greatest divisor of 7^n - 5^n that is relatively prime to 7^m - 5^m for all positive integers m < n.

Original entry on oeis.org

2, 3, 109, 37, 6841, 13, 372709, 1513, 176149, 1661, 964249309, 1801, 47834153641, 75139, 3162961, 3077713, 115933787267041, 30133, 5689910849522509, 3949201, 6868494361, 168846239, 13678413205562919109, 4654801, 97995219736887001

Offset: 1

Jonathan Vos Post, Aug 21 2005

nonn

Eric Weisstein's World of Mathematics, Zsigmondy's Theorem

Cf. A064078-A064083, A109325, A109347, A109348.

Edited, corrected and extended by Ray Chandler, Aug 26 2005

Definition corrected by Jerry Metzger, Nov 04 2009

A323748 Square array read by ascending antidiagonals: the n-th row lists the Zsigmondy numbers for a = n, b = 1, that is, T(n,k) = Zs(k, n, 1) is the greatest divisor of n^k - 1 that is coprime to n^m - 1 for all positive integers m < k, with n >= 2, k >= 1.

Original entry on oeis.org

1, 2, 3, 3, 1, 7, 4, 5, 13, 5, 5, 3, 7, 5, 31, 6, 7, 31, 17, 121, 1, 7, 1, 43, 13, 341, 7, 127, 8, 9, 19, 37, 781, 13, 1093, 17, 9, 5, 73, 25, 311, 7, 5461, 41, 73, 10, 11, 91, 65, 2801, 31, 19531, 257, 757, 11, 11, 3, 37, 41, 4681, 43, 55987, 313, 1387, 61, 2047, 12, 13, 133, 101, 7381, 19, 137257, 1297, 15751, 41, 88573, 13

Offset: 2

Jianing Song, Jan 25 2019

By Zsigmondy's theorem, T(n,k) = 1 if and only if n = 2 and k = 1 or 6, or n + 1 is a power of 2 and k = 2.
All prime factors of T(n,k) are congruent to 1 modulo k.
If T(n,k) = p^e where p is prime, then p is a unique-period prime in base n. By the property above, k must be a divisor of p - 1.
There are many squares of primes in the third, fourth or sixth column (e.g., T(7,4) = 25 = 5^2, T(22,3) = T(23,6) = 169 = 13^2, T(41,4) = 841 = 29^2, etc.). Conjecturally all other prime powers with exponent >= 2 in the table excluding the first two columns are T(3,5) = 121 = 11^2, T(18,3) = T(19,6) = 343 = 7^3 and T(239,4) = 28561 = 13^4.

			In the following list, "*" identifies a prime power.
Table begins
   n\k |  1    2     3     4       5     6         7       8
   2   |  1 ,  3*,   7*,   5*,    31*,   1 ,     127*,    17*
   3   |  2*,  1 ,  13*,   5*,   121*,   7*,    1093*,    41*
   4   |  3*,  5*,   7*,  17*,   341 ,  13*,    5461 ,   257*
   5   |  4*,  3*,  31*,  13*,   781 ,   7*,   19531*,   313*
   6   |  5*,  7*,  43*,  37*,   311*,  31*,   55987*,  1297*
   7   |  6 ,  1 ,  19*,  25*,  2801*,  43*,  137257 ,  1201*
   8   |  7*,  9*,  73*,  65 ,  4681 ,  19*,   42799 ,  4097
   9   |  8*,  5*,  91 ,  41*,  7381 ,  73*,  597871 ,  3281
  10   |  9*, 11*,  37*, 101*, 11111 ,  91 , 1111111 , 10001
  11   | 10 ,  3*, 133 ,  61*,  3221*,  37*, 1948717 ,  7321*
  12   | 11*, 13*, 157*, 145 , 22621*, 133 , 3257437 , 20737
The first few columns:
  T(n,1) = n - 1;
  T(n,2) = A000265(n+1);
  T(n,3) = (n^2 + n + 1)/3 if n == 1 (mod 3), n^2 + n + 1 otherwise;
  T(n,4) = (n^2 + 1)/2 if n == 1 (mod 2), n^2 + 1 otherwise;
  T(n,5) = (n^4 + n^3 + n^2 + n + 1)/5 if n == 1 (mod 5), n^4 + n^3 + n^2 + n + 1 otherwise;
  T(n,6) = (n^2 - n + 1)/3 if n == 2 (mod 3), n^2 - n + 1 otherwise;
  T(n,7) = (n^6 + n^5 + ... + 1)/7 if n == 1 (mod 7), n^6 + n^5 + ... + 1 otherwise;
  T(n,8) = (n^4 + 1)/2 if n == 1 (mod 2), n^4 + 1 otherwise;
  T(n,9) = (n^6 + n^3 + 1)/3 if n == 1 (mod 3), n^6 + n^3 + 1 otherwise;
  T(n,10) = (n^4 - n^3 + n^2 - n + 1)/5 if n == 4 (mod 5), n^4 - n^3 + n^2 - n + 1 otherwise;
  T(n,11) = (n^10 + n^9 + ... + 1)/11 if n == 1 (mod 11), n^10 + n^9 + ... + 1 otherwise;
  T(n,12) = n^4 - n^2 + 1 (12 is not of the form p^e*d for any prime p, exponent e >= 1 and d dividing p-1).

Jeppe Stig Nielsen, Table of n, a(n) for n = 2..11326 (so 150 antidiagonals)
Jianing Song, Notes for A323748
Wikipedia, Zsigmondy's theorem

Cf. A000265, A253240, A342255.

Rows 1..6 are A064078, A064079, A064080, A064081, A064082 and A064083.

Table[Function[n, SelectFirst[Reverse@ Divisors[n^k - 1], Function[m, AllTrue[n^Range[k - 1] - 1, GCD[#, m] == 1 &]]]][j - k + 2], {j, 12}, {k, j}] // Flatten (* or *)
Table[Function[n, If[k == 2, #/2^IntegerExponent[#, 2] &[n + 1], #/GCD[#, k] &@ Cyclotomic[k, n]]][j - k + 1], {j, 2, 13}, {k, j - 1}] // Flatten (* Michael De Vlieger, Feb 02 2019 *)

T(n,k) = if(k==2, (n+1)>>valuation(n+1, 2), my(m = polcyclo(k, n)); m/gcd(m, k))

T(n,k) = A000265(n+1) if k = 2, otherwise T(n,k) = Phi_k(n)/gcd(Phi_k(n), k) = A253240(k,n)/gcd(A253240(k,n), k) where Phi_k is the k-th cyclotomic polynomial.
T(n,k) = A000265(n+1) if k = 2, Phi_k(n)/p if k = p^e*ord(n,p) != 2 for some prime p and exponent e >= 1, Phi_k(n) otherwise, where ord(n,p) is the multiplicative order of n modulo p.
T(n,k) = Phi_k(n)/A342255(n,k) for n >= 2, k != 2.

Zs notation in Name changed by Jeppe Stig Nielsen, Oct 16 2020

cp's OEIS Frontend

A109347 Zsigmondy numbers for a = 5, b = 3: Zs(n, 5, 3) is the greatest divisor of 5^n - 3^n (A005058) that is relatively prime to 5^m - 3^m for all positive integers m < n.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A144755 Primes which divide none of overpseudoprimes to base 2 (A141232).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Extensions

A161508 Numbers k such that 2^k-1 has only one primitive prime factor.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A064082 Zsigmondy numbers for a = 6, b = 1: Zs(n, 6, 1) is the greatest divisor of 6^n - 1^n (A024062) that is relatively prime to 6^m - 1^m for all positive integers m < n.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A093106 Numbers k such that the k-th cyclotomic polynomial evaluated at 2 (=A019320(k)) is not coprime to k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

A097406 Largest primitive prime factor of 2^n-1, or a(n) = 1 if no such prime exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A109325 Zsigmondy numbers for a = 3, b = 2: Zs(n, 3, 2) is the greatest divisor of 3^n - 2^n (A001047) that is relatively prime to 3^m - 2^m for all positive integers m < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A109348 Zsigmondy numbers for a = 7, b = 3: Zs(n, 7, 3) is the greatest divisor of 7^n - 3^n that is relatively prime to 7^m - 3^m for all positive integers m < n.

Views

Author

Keywords

Links

Crossrefs