A342255 -id:A342255 - cp's OEIS frontend

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.

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

A342256 Numbers k such that gcd(k, Phi_k(a)) > 1 for some a, where Phi_k is the k-th cyclotomic polynomial.

Original entry on oeis.org

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29, 31, 32, 34, 37, 38, 39, 41, 42, 43, 46, 47, 49, 50, 52, 53, 54, 55, 57, 58, 59, 61, 62, 64, 67, 68, 71, 73, 74, 78, 79, 81, 82, 83, 86, 89, 93, 94, 97, 98, 100, 101

Offset: 1

Jianing Song, Mar 07 2021

Indices of columns of A342255 with some elements greater than 1.
For k > 1, let p be the largest prime factor of k, then k is a term if and only if k = p^e*d with d | (p-1). See A342255 for more information.
Also numbers k such that A342257(k) > 1.

			6 is a term since gcd(6, Phi_6(2)) = gcd(6, 3) = 3 > 1.
55 is a term since 55 = 11*5, 5 | (11-1). Indeed, gcd(55, Phi_55(3)) = gcd(55, 8138648440293876241) = 11 > 1.
12 is not a term since 12 = 3*4 but 4 does not divide 3-1. Indeed, gcd(12, Phi_12(a)) = gcd(12, a^4-a^2+1) = 1 for all a.

Jianing Song, Table of n, a(n) for n = 1..10000

Cf. A342255, A342257. Complement of A253235.

isA342256(k) = if(k>1, my(L=factor(k), d=omega(k), p=L[d,1]); (p-1)%(k/p^L[d,2])==0, 0)

Equals Union_{p prime} (Union_{d|(p-1)} {d*p, d*p^2, ..., d*p^e, ...}).

A342257 Period of the sequence {gcd(n, Phi_n(a)): a in Z}, where Phi_n is the n-th cyclotomic polynomial.

Original entry on oeis.org

1, 2, 3, 2, 5, 3, 7, 2, 3, 5, 11, 1, 13, 7, 1, 2, 17, 3, 19, 5, 7, 11, 23, 1, 5, 13, 3, 1, 29, 1, 31, 2, 1, 17, 1, 1, 37, 19, 13, 1, 41, 7, 43, 1, 1, 23, 47, 1, 7, 5, 1, 13, 53, 3, 11, 1, 19, 29, 59, 1, 61, 31, 1, 2, 1, 1, 67, 17, 1, 1, 71, 1, 73, 37, 1

Offset: 1

Jianing Song, Mar 07 2021

a(n) is the period of the n-th column of A342255. See A342255 for more information.

Also a(n) is the maximum value of the n-th column of A342255. - Jianing Song, Aug 09 2022

			gcd(6, Phi_6(a)) = gcd(6, a^2-a+1) = 3 for a == 2 (mod 3), 1 otherwise, so {gcd(6, Phi_6(a)): a in Z} has period 3, hence a(6) = 3.
gcd(12, Phi_12(a)) = gcd(12, a^4-a^2+1) = 1 for all n, so {gcd(12, Phi_12(a)): a in Z} has period 1, hence a(12) = 1.

Jianing Song, Table of n, a(n) for n = 1..10000

Cf. A342255, A253235 (indices of 1), A342256 (indices of terms other than 1), A006530, A013595 (coefficients of cyclotomic polynomials).

a(n) = if(n>1, my(L=factor(n), d=omega(n), p=L[d, 1]); if((p-1)%(n/p^L[d, 2])==0, p, 1), 1)

a(n) is the largest prime factor of n if n is in A342256, 1 otherwise.

A342323 Square array read by ascending antidiagonals: T(n,k) = gcd(k, Phi_k(n)), where Phi_k is the k-th cyclotomic polynomial, n >= 0, k >= 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 5, 1, 1, 2, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 3, 7, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 1, 2, 1, 2, 5, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 2, 3, 2, 1, 1, 1, 2, 3, 1, 1, 1, 1

Offset: 0

Jianing Song, Mar 08 2021

This is the same table as A342255 but with offset 0. Therefore, the resulting sequences as flattened tables are different. The main entry is A342255.

			Table begins:
  n\k |  1  2  3  4  5  6  7  8  9 10 11 12
  ------------------------------------------
    0 |  1  1  1  1  1  1  1  1  1  1  1  1
    1 |  1  2  3  2  5  1  7  2  3  1 11  1
    2 |  1  1  1  1  1  3  1  1  1  1  1  1
    3 |  1  2  1  2  1  1  1  2  1  1  1  1
    4 |  1  1  3  1  1  1  1  1  3  5  1  1
    5 |  1  2  1  2  1  3  1  2  1  1  1  1
    6 |  1  1  1  1  5  1  1  1  1  1  1  1
    7 |  1  2  3  2  1  1  1  2  3  1  1  1
    8 |  1  1  1  1  1  3  7  1  1  1  1  1
    9 |  1  2  1  2  1  1  1  2  1  5  1  1
   10 |  1  1  3  1  1  1  1  1  3  1  1  1
   11 |  1  2  1  2  5  3  1  2  1  1  1  1
   12 |  1  1  1  1  1  1  1  1  1  1 11  1

Jianing Song, Table of n, a(n) for n = 0..5049 (the first 100 antidiagonals)

Cf. A342255.

A342323[n_, k_] := GCD[k, Cyclotomic[k, n]];
Table[A342323[n-k+1, k], {n, 0, 15}, {k, n+1}] (* Paolo Xausa, Feb 09 2024 *)

PARI
```
T(n,k) = gcd(k, polcyclo(k,n))
```

For k > 1, let p be the largest prime factor of k, then T(n,k) = p if p does not divide n and k = p^e*ord(p,n) for some e > 0, where ord(p,n) is the multiplicative order of n modulo p.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A342256 Numbers k such that gcd(k, Phi_k(a)) > 1 for some a, where Phi_k is the k-th cyclotomic polynomial.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A342257 Period of the sequence {gcd(n, Phi_n(a)): a in Z}, where Phi_n is the n-th cyclotomic polynomial.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A342323 Square array read by ascending antidiagonals: T(n,k) = gcd(k, Phi_k(n)), where Phi_k is the k-th cyclotomic polynomial, n >= 0, k >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula