A326926 -id:A326926 - cp's OEIS frontend

A326933 Number of nonconstant irreducible polynomial divisors of the n-th polynomial given in A326926.

0, 1, 2, 2, 1, 5, 1, 3, 4, 3, 1, 8, 1, 3, 5, 4, 1, 9, 1, 5, 5, 3, 1, 11, 2, 3, 6, 5, 1, 11, 1, 5, 5, 3, 3, 14, 1, 3, 5, 7, 1, 11, 1, 5, 9, 3, 1, 14, 2, 5, 5, 5, 1, 13, 3, 7, 5, 3, 1, 17, 1, 3, 9, 6, 3, 11, 1, 5, 5, 7, 1, 19, 1, 3, 8, 5, 3, 11, 1, 9, 8, 3, 1

Offset: 0

Clark Kimberling, Nov 01 2019

nonn

It appears that each nonconstant polynomial is irreducible if and only if its degree is p-1 for some prime p other than 3.

			The 5 nonconstant irreducible divisors of the 5th polynomial appear in this factorization: -3 x (-2 + x) (-1 + x) (1 + x) (-1 + 2 x).

Antti Karttunen, Table of n, a(n) for n = 0..2048

Cf. A326926.

g[x_, n_] := Numerator[ Factor[D[1/(x^2 - x + 1), {x, n}]]];
Column[Expand[Table[g[x, n]/n!, {n, 0, 12}]]] (* polynomials *)
h[n_] := CoefficientList[g[x, n]/n!, x]
Table[h[n], {n, 0, 10}]
Column[%]  (* A326926 array *)
Table[-1 + Length[FactorList[g[x, n]/n!]], {n, 0, 100}]  (* A326933 *)

A326933(n) = { my(p=1/(1-x+x^2)); for(k=1,n, p = deriv(p)); #(factor(numerator(p)/n!)~); };

Starting offset corrected from 1 to 0 by Antti Karttunen, Mar 02 2023

A329062 Numbers k that are not prime powers (i.e., not in A000961) such that A328925(k) > 1; numbers k such that if we write k = Product_{i=1..t} p_i^e_i , then t > 1, and lcm_{1<=i,j<=t, i!=j} ord(p_i,p_j^e_j) < A002322(k), where ord(a,r) is the multiplicative order of a modulo r, and A002322 is the Carmichael lambda (usually written as psi).

Original entry on oeis.org

14, 34, 39, 46, 55, 62, 65, 68, 82, 86, 94, 95, 98, 111, 112, 117, 123, 124, 133, 136, 142, 145, 146, 153, 155, 158, 164, 172, 175, 178, 183, 194, 201, 203, 205, 206, 209, 218, 219, 221, 224, 226, 248, 253, 254, 259, 272, 274, 275, 287, 291, 292, 295, 299, 301, 302, 305, 309

Offset: 1

Jianing Song, Nov 02 2019

nonn

Write psi = A002322, b = A118106. These are numbers k that are not prime powers such that b(k) < psi(k).
If k = Product_{i=1..t} p_i^e_i (t > 1), where {p_i} are distinct odd primes such that p_i is a quadratic residue modulo p_j for all i != j, then k is here, as b(k) | psi(k)/2.
If k = 2 * Product_{i=1..t} p_i^e_i, where {p_i} are distinct odd primes such that p_i is a quadratic residue modulo p_j for all i != j, and p_i == 1, 7 (mod 8), then k is here. For example, k = 2p, where p == 1, 7 (mod 8).
If k = 2^e * Product_{i=1..t} p_i^e_i (e > 1), where {p_i} are distinct odd primes such that p_i is a quadratic residue modulo p_j for all i != j, and p_i == 1 (mod 8), then k is here. For example, k = 2^e*p, where p == 1 (mod 8).
If k = p_1^e_1 * p_2^e_2, where p_1 is not a primitive root modulo p_2^e_2, p_2 is not a primitive root modulo p_1^e_1, then k is not necessarily here: for k = 3^2 * 67 = 603, 3 is not a primitive root modulo 67, 67 is not a primitive root modulo 3^2, but b(603) = psi(603) = 66. Conversely, if p_1 is a primitive root modulo p_2^e_2, then k can still be here: for k = 3^2 * 17 = 153, 3 is a primitive root modulo 17, but b(153) = 16 while psi(153) = 48.
If k is an odd number, then 4k is here if and only if 8k is also here. Write k = Product_{i=1..t} p_i^e_i, then b(4k) = lcm(lcm_{i=1..t} ord(p_i,4),lcm_{i=1..t} ord(2,p_i^e_i),b(k)), b(8k) = lcm(lcm_{i=1..t} ord(p_i,8),lcm_{i=1..t} ord(2,p_i^e_i),b(k)). It is easy to see that lcm(ord(p_i,4),ord(2,p_i^e_i)) = lcm(ord(p_i,8),ord(2,p_i^e_i)), so b(4k) = b(8k). Note that psi(4k) = psi(8k).
If k is an odd number such that 4k is here, then 16k is also here (but the converse is not true). Write k = Product_{i=1..t} p_i^e_i, N = lcm(lcm_{i=1..t} ord(2,p_i^e_i),b(k)), then b(4k) = lcm(lcm_{i=1..t} ord(p_i,4),N), b(16k) = lcm(lcm_{i=1..t} ord(p_i,16),N) = b(4k) or b(4k)*2 or b(4k)*4. Note that psi(16k) = lcm(psi(4k),4). If we have b(4k) < psi(4k) and b(16k) = psi(16k), let M = psi(k), then:
Case (a): M == 2 (mod 4), then b(16k) = psi(16k) = 2*psi(4k) = 2M, and b(4k) = b(16k)/4 = M/2 which is an odd number, so ord(2,p_i^e_i) is odd for all i, so p_i == 1, 7 (mod 8), which gives ord(p_i,16) <= 2*ord(p_i,4). As a result, b(16k) <= 2*b(4k), a contradiction!
Case (b): M == 0 (mod 4), then b(16k) = psi(16k) = psi(4k) = M. If N is divisible by 4, then b(4k) = b(16k) = N, a contradiction. So 4 does not divide N, we have v(M,2) = v(lcm(lcm_{i=1..t} ord(p_i,16),N),2) <= 2, but 4 | M, so v(M,2) = 2, where v(,2) is the 2-adic valuation. As a result, there must exist p_i congruent to 5 mod 8 to make v(M,2) = 2, then 4 | ord(2,p_i^e_i), so 4 | N, a contradiction!
{a(n)} union A328926 = N* \ A000961 U {1, 2}.

			Let ord(a,r) be the multiplicative order of a modulo r.
For k = 175 = 5^2 * 7, b(175) = lcm(ord(7,5^2),ord(5,7)) = lcm(4,6) = 12, while psi(175) = lcm(20,6) = 60, so 175 is a term.
For k = 410 = 2 * 5 * 41, b(410) = lcm(ord(5,2),ord(41,2),ord(2,5),ord(41,5),ord(2,41),ord(5,41)) = 20, while psi(410) = lcm(1,4,40) = 40, so 410 is a term.

Cf. A118106, A002322, A326925, A326926, A000961.

isA329062(n) = !isprimepower(n) && (A002322(n) > A118106(n)) \\ See A002322 and A118106 for their programs

cp's OEIS Frontend

A326933 Number of nonconstant irreducible polynomial divisors of the n-th polynomial given in A326926.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions