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.
Original entry on oeis.org
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
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.
-
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
A064080
Zsigmondy numbers for a = 4, b = 1: Zs(n, 4, 1) is the greatest divisor of 4^n - 1^n (A024036) that is relatively prime to 4^m - 1^m for all positive integers m < n.
Original entry on oeis.org
3, 5, 7, 17, 341, 13, 5461, 257, 1387, 41, 1398101, 241, 22369621, 3277, 49981, 65537, 5726623061, 4033, 91625968981, 61681, 1826203, 838861, 23456248059221, 65281, 1100586419201, 13421773, 22906579627, 15790321, 96076792050570581
Offset: 1
A064081
Zsigmondy numbers for a = 5, b = 1: Zs(n, 5, 1) is the greatest divisor of 5^n - 1^n (A024049) that is relatively prime to 5^m - 1^m for all positive integers m < n.
Original entry on oeis.org
4, 3, 31, 13, 781, 7, 19531, 313, 15751, 521, 12207031, 601, 305175781, 13021, 315121, 195313, 190734863281, 5167, 4768371582031, 375601, 196890121, 8138021, 2980232238769531, 390001, 95397958987501, 203450521, 3814699218751, 234750601, 46566128730773925781, 464881, 1164153218269348144531
Offset: 1
A064079
Zsigmondy numbers for a = 3, b = 1: Zs(n, 3, 1) is the greatest divisor of 3^n - 1^n (A024023) that is relatively prime to 3^m - 1^m for all positive integers m < n.
Original entry on oeis.org
2, 1, 13, 5, 121, 7, 1093, 41, 757, 61, 88573, 73, 797161, 547, 4561, 3281, 64570081, 703, 581130733, 1181, 368089, 44287, 47071589413, 6481, 3501192601, 398581, 387440173, 478297, 34315188682441, 8401, 308836698141973, 21523361
Offset: 1
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.
Original entry on oeis.org
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
-
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
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
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
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
-
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
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
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
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
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).
-
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))
Showing 1-10 of 10 results.
Comments