A206442 -id:A206442 - cp's OEIS frontend

A206284 Numbers that match irreducible polynomials over the nonnegative integers.

3, 6, 9, 10, 12, 18, 20, 22, 24, 27, 28, 30, 36, 40, 42, 44, 46, 48, 50, 52, 54, 56, 60, 66, 68, 70, 72, 76, 80, 81, 88, 92, 96, 98, 100, 102, 104, 108, 112, 114, 116, 118, 120, 124, 126, 130, 132, 136, 140, 144, 148, 150, 152, 154, 160, 162, 164, 168, 170

Offset: 1

Clark Kimberling, Feb 05 2012

nonn

Starting with 1, which encodes 0-polynomial, each integer m encodes (or "matches") a polynomial p(m,x) with nonnegative integer coefficients determined by the prime factorization of m. Write m = prime(1)^e(1) * prime(2)^e(2) * ... * prime(k)^e(k); then p(m,x) = e(1) + e(2)x + e(3)x^2 + ... + e(k)x^k.
Identities:
  p(m*n,x) = p(m,x) + p(n,x),
  p(m*n,x) = p(gcd(m,n),x) + p(lcm(m,n),x),
  p(m+n,x) = p(gcd(m,n),x) + p((m+n)/gcd(m,n),x), so that if A003057 is read as a square matrix, then
  p(A003057,x) = p(A003989,x) + p(A106448,x).
Apart from powers of 3, all terms are even. - Charles R Greathouse IV, Feb 11 2012
Contains 2*p^m and p*2^m if p is an odd prime and m is in A052485. - Robert Israel, Oct 09 2016

			Polynomials having nonnegative integer coefficients are matched to the positive integers as follows:
   m    p(m,x)    irreducible
  ---------------------------
   1    0         no
   2    1         no
   3    x         yes
   4    2         no
   5    x^2       no
   6    1+x       yes
   7    x^3       no
   8    3         no
   9    2x        yes
  10    1+x^2     yes

Antti Karttunen, Table of n, a(n) for n = 1..10566

Cf. A052485, A206285 (complement), A206296.
Positions of ones in A277322.
Terms of A277318 form a proper subset of this sequence. Cf. also A277316.
Other sequences about factorization in the same polynomial ring: A206442, A284010.
Polynomial multiplication using the same encoding: A297845.

P:= n -> add(f[2]*x^(numtheory:-pi(f[1])-1), f =  ifactors(n)[2]):
select(irreduc @ P, [$1..200]); # Robert Israel, Oct 09 2016

b[n_] := Table[x^k, {k, 0, n}];
f[n_] := f[n] = FactorInteger[n]; z = 400;
t[n_, m_, k_] := If[PrimeQ[f[n][[m, 1]]] && f[n][[m, 1]]
== Prime[k], f[n][[m, 2]], 0];
u = Table[Apply[Plus,
    Table[Table[t[n, m, k], {k, 1, PrimePi[n]}], {m, 1,
      Length[f[n]]}]], {n, 1, z}];
p[n_, x_] := u[[n]].b[-1 + Length[u[[n]]]]
Table[p[n, x], {n, 1, z/4}]
v = {}; Do[n++; If[IrreduciblePolynomialQ[p[n, x]],
AppendTo[v, n]], {n, z/2}]; v  (* A206284 *)
Complement[Range[200], v]      (* A206285 *)

is(n)=my(f=factor(n));polisirreducible(sum(i=1, #f[,1], f[i,2]*'x^primepi(f[i,1]-1))) \\ Charles R Greathouse IV, Feb 12 2012

Introductory comments edited by Antti Karttunen, Oct 09 2016 and Peter Munn, Aug 13 2022

A284010 a(n) = least natural number with the same prime signature polynomial p(n,x) has when it is factored over Z. Polynomial p(n,x) has only nonnegative integer coefficients that are encoded in the prime factorization of n.

Original entry on oeis.org

0, 0, 2, 0, 4, 2, 8, 0, 2, 2, 16, 2, 32, 6, 6, 0, 64, 2, 128, 2, 6, 2, 256, 2, 4, 6, 2, 2, 512, 2, 1024, 0, 30, 6, 12, 2, 2048, 6, 6, 2, 4096, 2, 8192, 2, 6, 2, 16384, 2, 8, 2, 30, 2, 32768, 2, 12, 2, 30, 30, 65536, 2, 131072, 6, 6, 0, 60, 2, 262144, 2, 30, 2, 524288, 2, 1048576, 6, 6, 2, 24, 6, 2097152, 2, 2, 6, 4194304, 6, 12, 6, 6, 2, 8388608, 4, 24, 2, 210

Offset: 1

Antti Karttunen, Mar 20 2017

nonn

Let p(n,x) be the completely additive polynomial-valued function such that p(prime(n),x) = x^(n-1) as defined by Clark Kimberling in A206284. To compute a(n), factor p(n,x) over Z and collect the exponents of its irreducible polynomial factors using them as exponents of primes (in Z) as 2^e1 * 3^e2 * 5^e3 * ..., with e1 >= e2 >= e3 >= ...

			For n = 7 = prime(4), the corresponding polynomial is x^3, which factorizes as (x)(x)(x), thus a(7) = 2^3 = 8.
For n = 14 = prime(4) * prime(1), the corresponding polynomial is x^3 + 1, which factorizes as (x + 1)(x^2 - x + 1), thus a(14) = 2^1 * 3^1 = 6.
For n = 90 = prime(3) * prime(2)^2 * prime(1), the corresponding polynomial is x^2 + 2x + 1, which factorizes as (x + 1)^2, thus a(90) = 2^2 = 4.

Antti Karttunen, Table of n, a(n) for n = 1..8192

Cf. A046523, A206284 (positions of 2's), A206442, A277322, A284011, A284012.

Cf. also A260443, A278233, A278243.

\\ After Charles R Greathouse IV's code in A046523 and A277322:
pfps(n) = { my(f=factor(n)); sum(i=1, #f~, f[i, 2] * 'x^(primepi(f[i, 1])-1)); };
A284010(n) = { if(!bitand(n, (n-1)), 0, my(p=0, f=vecsort(factor(pfps(n))[, 2], ,4)); prod(i=1, #f, (p=nextprime(p+1))^f[i])); }

a(2^n) = 0. [By an explicit convention.]
Other identities. For all n >= 1:
A284011(n) = a(A260443(n)).

A277322 a(n) = number of irreducible polynomial factors (counted with multiplicity) in the polynomial (with nonnegative integral coefficients) constructed from the prime factorization of n.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 3, 0, 1, 1, 4, 1, 5, 2, 2, 0, 6, 1, 7, 1, 2, 1, 8, 1, 2, 2, 1, 1, 9, 1, 10, 0, 3, 2, 3, 1, 11, 2, 2, 1, 12, 1, 13, 1, 2, 1, 14, 1, 3, 1, 3, 1, 15, 1, 3, 1, 3, 3, 16, 1, 17, 2, 2, 0, 4, 1, 18, 1, 3, 1, 19, 1, 20, 2, 2, 1, 4, 2, 21, 1, 1, 2, 22, 2, 3, 2, 2, 1, 23, 2, 4, 1, 4, 2, 4, 1, 24, 1, 2, 1, 25, 1, 26, 1, 2

Offset: 1

Antti Karttunen, Oct 09 2016

nonn

Let p(n,x) be the completely additive polynomial-valued function such that p(prime(n),x) = x^(n-1) as defined by Clark Kimberling in A206284. Then this sequence is the number of irreducible factors in p(n,x), counted with multiplicity.

			For n = 7 = prime(4), the corresponding polynomial is x^3, which factorizes as (x)(x)(x), thus a(7) = 3.
For n = 14 = prime(4) * prime(1), the corresponding polynomial is x^3 + 1, which factorizes as (x + 1)(x^2 - x + 1), thus a(14) = 2.
For n = 90 = prime(3) * prime(2)^2 * prime(1), the corresponding polynomial is x^2 + 2x + 1, which factorizes as (x + 1)^2, thus a(90) = 2.
pfps(660) = pfps(2^2*3*5*11) = pfps(2^2) + pfps(3) + pfps(5) + pfps(11) = 2 + x + x^2 + x^4 which is irreducible, so a(660) = 1.
For n = 30030 = Product_{i=1..6} prime(i), the corresponding polynomial is x^5 + x^4 + x^3 + x^2 + x + 1, which factorizes as (x+1)(x^2 - x + 1)(x^2 + x + 1), thus a(30030) = 3.

Antti Karttunen, Table of n, a(n) for n = 1..30033

Cf. A206442 (gives the number of irreducible polynomial factors without multiplicity), A206284 (positions of 1's, i.e., irreducible polynomials).

Cf. A000040, A007188, A064989, A260443, A277013.

allocatemem(2^29);
A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
pfps(n) = if(1==n, 0, if(!(n%2), 1 + pfps(n/2), 'x*pfps(A064989(n))));
A277322 = n -> if(!bitand(n,(n-1)), 0, vecsum(factor(pfps(n))[,2]));
for(n=1, 121121, write("b277322.txt", n, " ", A277322(n)));

pfps(n)=my(f=factor(n)); sum(i=1,#f~, f[i,2] * 'x^(primepi(f[i,1])-1))
A277322(n) = if(1==n, 0, vecsum(factor(pfps(n))[, 2])); \\ Charles R Greathouse IV, test for one added by Antti Karttunen, Oct 09 2016

a(2^n) = 0. [By an explicit convention.]
a(A000040(n)) = n-1.
a(A007188(n)) = n.
a(A260443(n)) = A277013(n).

A206719 Number of distinct irreducible factors of the polynomial p(n,x) defined at A206073.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 2, 1, 1, 3, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 1, 2, 2, 2, 3, 1, 2, 2, 2, 1, 3, 1, 2, 3, 2, 1, 2, 2, 2, 2, 2, 1, 3, 1, 2, 2, 2, 1, 3, 1, 2, 3, 1, 2, 3, 1, 2, 1, 3, 1, 3, 1, 2, 3, 2, 1, 3, 1, 2, 1, 2, 1, 3, 2, 2, 1, 2, 1, 4, 1, 2, 2, 2, 2, 2, 1, 3, 2

Offset: 1

Clark Kimberling, Feb 11 2012

nonn

The polynomials having coefficients in {0,1} are enumerated as in A206074 (and A206073).

			p(1,n) = 1, so a(1)=0
p(2,n) = x, so a(2)=1
p(6,n) = x(1+x), so a(6)=2
p(18,n) = x(x+1)(1-x+x^2), so a(18)=3
p(90,n) = x(1+x)(1+x^2)(1-x+x^2), so a(90)=4

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A206073, A206074, A257000.

Cf. also A091221, A206442.

t = Table[IntegerDigits[n, 2], {n, 1, 1000}];
b[n_] := Reverse[Table[x^k, {k, 0, n}]]
p[n_, x_] := p[n, x] = t[[n]].b[-1 + Length[t[[n]]]]
TableForm[Table[{n, p[n, x],
   FactorList[p[n, x]], -1 + Length[FactorList[p[n, x]]]}, {n, 1, 9}]]
Table[Length[FactorList[p[n, x]]], {n, 1, 120}]

A206719(n) = { my(f = factor(Pol(binary(n)))); (#f~); }; \\ Antti Karttunen, Dec 16 2017

cp's OEIS Frontend

A206284 Numbers that match irreducible polynomials over the nonnegative integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A284010 a(n) = least natural number with the same prime signature polynomial p(n,x) has when it is factored over Z. Polynomial p(n,x) has only nonnegative integer coefficients that are encoded in the prime factorization of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A277322 a(n) = number of irreducible polynomial factors (counted with multiplicity) in the polynomial (with nonnegative integral coefficients) constructed from the prime factorization of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A206719 Number of distinct irreducible factors of the polynomial p(n,x) defined at A206073.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI