A253240 -id:A253240 - cp's OEIS frontend

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

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

Offset: 1

Jianing Song, Mar 07 2021

T(n,k) is either 1 or a prime.

Since p is a prime factor of Phi_k(n) => either p == 1 (mod k) or p is the largest prime factor of k. As a result, T(n,k) = 1 if and only if all prime factors of Phi_k(n) are congruent to 1 modulo k.

			Table begins
  n\k |  1  2  3  4  5  6  7  8  9 10 11 12
  ------------------------------------------
    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 = 1..5050 (the first 100 antidiagonals)
Jianing Song, Proof for the first formula

Cf. A253240, A323748, A014963 (row 1), A253235 (indices of columns with only 1), A342256 (indices of columns with some elements > 1), A342257 (period of each column, also maximum value of each column), A013595 (coefficients of cyclotomic polynomials).

A342323 is the same table with offset 0.

A342255[n_, k_] := GCD[k, Cyclotomic[k, n]];
Table[A342255[n-k+1,k], {n, 15}, {k, n}] (* 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. See my link above for the proof.
T(n,k) = T(n,k*p^a) for all a, where p is the largest prime factor of k.
T(n,k) = Phi_k(n)/A323748(n,k) for n >= 2, k != 2.
For prime p, T(n,p^e) = p if n == 1 (mod p), 1 otherwise.
For odd prime p, T(n,2*p^e) = p if n == -1 (mod p), 1 otherwise.

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula