A253235 -id:A253235 - 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.

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.

A253236 The unique prime p <= n such that n-th cyclotomic polynomial has a root mod p, or 0 if no such p exists.

Original entry on oeis.org

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

Offset: 1

Eric Chen, Apr 07 2015

nonn

There is at most one prime p <= n such that n-th cyclotomic polynomial has a root mod p.
For prime n and every natural number k, a(n^k) = n.
If a(n) != 0, then a(n)|n.
a(n) is either 0 or A006530(n). See Corollary 23 of the Shevelev et al. link. - Robert Israel, Sep 07 2016

Eric Chen and Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 1500 terms from Chen)
V. Shevelev, G. Garcia-Pulgarin, J. M. Velasquez-Soto and J. H. Castillo, Overpseudoprimes, and Mersenne and Fermat Numbers as Primover Numbers, J. of Integer Sequences, Vol. 15 (2012), Art. 12.7.7.

For a(n) = 0, see A253235.
For a(n) = 2, see A000079.
For a(n) = 3, see A038754.
For a(n) = 5, see A245478.
For a(n) = 7, see A245479.
For a(n) = 11, see A245480.
For a(n) = 13, see A245481.
Cf. A006530.

N:= 1000: # to get a(1) to a(N)
f:= proc(n) local p,x,C,v;
    C:= numtheory:-cyclotomic(n,x);
    p:= max(numtheory:-factorset(n));
    for v from 0 to p-1 do
      if eval(C,x=v) mod p = 0 then return p fi
    od:
    0
end proc:
f(1):= 0:
seq(f(n),n=1..N); # Robert Israel, Sep 07 2016

a[n_] := Module[{p, x, c, v}, c[x_] = Cyclotomic[n, x]; p = FactorInteger[ n][[-1, 1]]; For[v=0, vJean-François Alcover, Jul 27 2020, after Maple *)

a(n) = forprime(p=2, n, if(#polrootsmod(polcyclo(n), p), return(p)))

a(n)=my(P=polcyclo(n),f=factor(n)[,1]); for(i=1,#f, if(#polrootsmod(P, f[i]), return(f[i]))); 0 \\ Charles R Greathouse IV, Apr 07 2015

A276469 Triangle read by rows: T(n,k) = n-th cyclotomic polynomial evaluated at x = k and then reduced mod n.

Original entry on oeis.org

0, 1, 0, 1, 0, 1, 1, 2, 1, 2, 1, 0, 1, 1, 1, 1, 1, 3, 1, 1, 3, 1, 0, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Peter A. Lawrence, Sep 04 2016

Let C_n(x) denote the n-th cyclotomic polynomial. Then T(n,k) = C_n(k) mod n.
Conjectures:
1) (mod p)  C_p(k) == 1, except C_p(1) == 0, for prime p, 0<=k2) (mod 2^e) C_[2^e](k) == 1 if k odd, == 0 k even, for e>1, 0<=k<2^e
3) (mod p^e) C_[p^e](k) == 1, except C_[p^e](1+np) = p, e>1, 0<=n4.a) (mod m) C_m(k) for some composite m has values all 1's,
     but it is not clear for which m this happens,
4.b) (mod m) C_m(m) for other composite m has values 1 and x,
4.c) with recurring period x
4.d) x is the largest prime dividing m.
Remarks: (1) is trivial, I suspect (2) and (3) are simple algebra-crunching, (4) seems to be an interesting question. (4) seems to partition the natural numbers into primes union A253235 union A276628.

			Let C_N(x) be the N'th cyclotomic polynomial, then the values of C_N(k) mod N, m=0,...,N-1, are:
    \  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 -- k -->
C_1:   0
C_2:   1 0
C_3:   1 0 1
C_4:   1 2 1 2
C_5:   1 0 1 1 1
C_6:   1 1 3 1 1 3     (note period 3)
C_7:   1 0 1 1 1 1 1
C_8:   1 2 1 2 1 2 1 2
C_9:   1 3 1 1 3 1 1 3 1     (note period 3)
C_10:  1 1 1 1 5 1 1 1 1 5     (note period 5)
C_11:  1 0 1 1 1 1 1 1 1 1 1
C_12:  1 1 1 1 1 1 1 1 1 1 1 1
C_13:  1 0 1 1 1 1 1 1 1 1 1 1 1
C_14:  1 1 1 1 1 1 7 1 1 1 1 1 1 7     (note period 7)
C_15:  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
C_16:  1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2

Cf. A253235 (numbers m such that T(m,j) are all 1's), A276628 (composites m such that T(m,j) are not all 1's).

Table[Mod[Cyclotomic[i, j], i], {i, 12}, {j, 0, i - 1}] // Flatten (* Michael De Vlieger, Sep 23 2016 *)

T(n, k) = polcyclo(n, k) % n; \\ Michel Marcus, Sep 22 2016

T(i,j) = Cyclotomic_i(j) (mod i); for i>=1 and j=0..i-1.

a(1) corrected by Jinyuan Wang, Jul 09 2020

A276628 Composite m such that A276469(m,k) are not all 1's.

Original entry on oeis.org

4, 6, 8, 9, 10, 14, 16, 18, 20, 21, 22, 25, 26, 27, 32, 34, 38, 39, 42, 46, 49, 50, 52, 54, 55, 57, 58, 62, 64, 68, 74, 78, 81, 82, 86, 93, 94, 98, 100, 106, 110, 111, 114, 116, 118, 121, 122, 125, 128, 129, 134, 136, 142, 146, 147, 148, 155, 156, 158, 162, 164, 166, 169

Offset: 1

Peter A. Lawrence, Sep 07 2016

nonn

Cf. A253235, A276469.

T(m, k) = polcyclo(m, k) % m;
isok(m) = !isprime(m+(m<2)) && vector(m, k, T(m, k-1)) != vector(m, k, 1); \\ Michel Marcus, Sep 22 2016 and modified by Jinyuan Wang, Jul 09 2020

More terms from Michel Marcus, Sep 22 2016

Showing 1-6 of 6 results.

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

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

A253236 The unique prime p <= n such that n-th cyclotomic polynomial has a root mod p, or 0 if no such p exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

A276469 Triangle read by rows: T(n,k) = n-th cyclotomic polynomial evaluated at x = k and then reduced mod n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A276628 Composite m such that A276469(m,k) are not all 1's.

Views

Author

Keywords

Crossrefs

Programs

PARI

Extensions