A303710 -id:A303710 - cp's OEIS frontend

A303707 Number of factorizations of n using elements of A007916 (numbers that are not perfect powers).

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 5, 1, 1, 2, 2, 2, 5, 1, 2, 2, 4, 1, 5, 1, 3, 3, 2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 9, 1, 2, 3, 1, 2, 5, 1, 3, 2, 5, 1, 8, 1, 2, 3, 3, 2, 5, 1, 5, 1, 2, 1, 9, 2, 2, 2

Offset: 1

Gus Wiseman, Apr 29 2018

nonn

First differs from A081707 at a(60) = 9, A081707(60) = 8.

			The a(60) = 9 factorizations are (2*2*3*5), (2*2*15), (2*3*10), (2*5*6), (2*30), (3*20), (5*12), (6*10), (60).

Cf. A000837, A001055, A001597, A007716, A007916, A045778, A052409, A052410, A162247, A281113, A281116, A303708, A303709, A303710.

radQ[n_]:=Or[n===1,GCD@@FactorInteger[n][[All,2]]===1];
facsr[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facsr[n/d],Min@@#>=d&]],{d,Select[Rest[Divisors[n]],radQ]}]];
Table[Length[facsr[n]],{n,100}]

Dirichlet g.f.: Product_{n in A007916} 1/(1 - n^s).

A294068 Number of factorizations of n using perfect powers (elements of A001597) other than 1.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, May 05 2018

nonn

			The a(1152) = 7 factorizations are (4*4*8*9), (4*8*36), (4*9*32), (8*9*16), (8*144), (9*128), (32*36).

Robert Israel, Table of n, a(n) for n = 1..10000

Positions of zeros are A052485.

Cf. A000961, A001055, A001222, A001597, A001694, A007716, A007916, A045778, A052409, A052410, A052486, A091050, A203025, A303707, A303710.

ispp:= proc(n) local F;
  F:= ifactors(n)[2];
  igcd(op(map(t -> t[2],F)))>1
end proc:
f:= proc(n) local F, np, Q;
  F:= map(t -> t[2], ifactors(n)[2]);
  np:= mul(ithprime(i)^F[i],i=1..nops(F));
  Q:= select(ispp, numtheory:-divisors(np));
  G(Q,np)
end proc:
G:= proc(Q,n) option remember; local q,t,k;
    if not numtheory:-factorset(n) subset `union`(seq(numtheory:-factorset(q),q=Q)) then return 0 fi;
    q:= Q[1]; t:= 0;
    for k from 0 while n mod q^k = 0 do
      t:= t + procname(Q[2..-1],n/q^k)
    od;
    t
end proc:
G({},1):= 1:
map(f, [$1..200]); # Robert Israel, May 06 2018

ppQ[n_]:=And[n>1,GCD@@FactorInteger[n][[All,2]]>1];
facsp[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facsp[n/d],Min@@#>=d&]],{d,Select[Divisors[n],ppQ]}]];
Table[Length[facsp[n]],{n,100}]

A303708 Number of aperiodic factorizations of n using elements of A007916 (numbers that are not perfect powers).

Original entry on oeis.org

0, 1, 1, 0, 1, 2, 1, 0, 0, 2, 1, 3, 1, 2, 2, 0, 1, 3, 1, 3, 2, 2, 1, 4, 0, 2, 0, 3, 1, 5, 1, 0, 2, 2, 2, 3, 1, 2, 2, 4, 1, 5, 1, 3, 3, 2, 1, 5, 0, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 9, 1, 2, 3, 0, 2, 5, 1, 3, 2, 5, 1, 8, 1, 2, 3, 3, 2, 5, 1, 5, 0, 2, 1, 9, 2, 2, 2, 4, 1, 9, 2

Offset: 1

Gus Wiseman, Apr 29 2018

nonn

An aperiodic factorization of n is a finite multiset of positive integers greater than 1 whose product is n and whose multiplicities are relatively prime.

The positions of zeros in this sequence are the prime powers A000961.

			The a(144) = 8 aperiodic factorizations are (2*2*2*3*6), (2*2*2*18), (2*2*3*12), (2*3*24), (2*6*12), (2*72), (3*48) and (6*24). Missing from this list are (12*12), (2*2*6*6) and (2*2*2*2*3*3).

Cf. A000740, A000837, A001055, A001597, A007716, A007916, A052409, A052410, A100953, A275870, A281116, A301700, A303386, A303431, A303546, A303551, A303707, A303709, A303710.

radQ[n_]:=Or[n===1,GCD@@FactorInteger[n][[All,2]]===1];
facsr[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facsr[n/d],Min@@#>=d&]],{d,Select[Rest[Divisors[n]],radQ]}]];
Table[Length[Select[facsr[n],GCD@@Length/@Split[#]===1&]],{n,100}]

a(n) = Sum_{d in A007916, d|A052409(n)} mu(d) * A303707(n^(1/d)).

A303709 Number of periodic factorizations of n using elements of A007916 (numbers that are not perfect powers).

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0

Offset: 1

Gus Wiseman, Apr 29 2018

nonn

A periodic factorization of n is a finite multiset of positive integers greater than 1 whose product is n and whose multiplicities have a common divisor greater than 1. Note that a factorization of a number that is not a perfect power (A007916) is always aperiodic (A303386), so the indices of nonzero entries of this sequence all lie at perfect powers (A001597).

			The a(900) = 5 periodic factorizations are (2*2*3*3*5*5), (2*2*15*15), (3*3*10*10), (5*5*6*6), (30*30).

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

Cf. A000740, A000837, A001055, A001597, A007716, A007916, A052409, A052410, A281116, A303547, A303552, A303553, A303386, A303707, A303708, A303710.

radQ[n_]:=Or[n===1,GCD@@FactorInteger[n][[All,2]]===1];
facsr[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facsr[n/d],Min@@#>=d&]],{d,Select[Rest[Divisors[n]],radQ]}]];
Table[Length[Select[facsr[n],GCD@@Length/@Split[#]!=1&]],{n,200}]

gcd_of_multiplicities(lista) = { my(u=length(lista)); if(u<2, u, my(g=0, pe = lista[1], j=1); for(i=2,u,if(lista[i]==pe, j++, g = gcd(j,g); j=1; pe = lista[i])); gcd(g,j)); }; \\ the supplied lista (newfacs) should be monotonic
A303709(n, m=n, facs=List([])) = if(1==n, (1!=gcd_of_multiplicities(facs)), my(s=0, newfacs); fordiv(n, d, if((d>1)&&(d<=m)&&!ispower(d), newfacs = List(facs); listput(newfacs,d); s += A303709(n/d, d, newfacs))); (s)); \\ Antti Karttunen, Dec 06 2018

a(n) <= A303553(n) <= A001055(n). - Antti Karttunen, Dec 06 2018

Changed a(1) to 1 by Gus Wiseman, Dec 06 2018

A320803 Number of non-isomorphic multiset partitions of weight n in which all parts are aperiodic multisets.

Original entry on oeis.org

1, 1, 3, 7, 21, 56, 174, 517, 1664, 5383, 18199, 62745, 223390, 813425, 3040181, 11620969, 45446484, 181537904, 740369798, 3079779662, 13059203150, 56406416004, 248027678362, 1109626606188, 5048119061134, 23342088591797, 109648937760252, 523036690273237

Offset: 0

Gus Wiseman, Nov 06 2018

nonn

A multiset is aperiodic if its multiplicities are relatively prime.

The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(1) = 1 through a(4) = 21 multiset partitions with aperiodic parts:
  {{1}}  {{1,2}}    {{1,2,2}}      {{1,2,2,2}}
         {{1},{1}}  {{1,2,3}}      {{1,2,3,3}}
         {{1},{2}}  {{1},{2,3}}    {{1,2,3,4}}
                    {{2},{1,2}}    {{1},{1,2,2}}
                    {{1},{1},{1}}  {{1,2},{1,2}}
                    {{1},{2},{2}}  {{1},{2,3,3}}
                    {{1},{2},{3}}  {{1},{2,3,4}}
                                   {{1,2},{3,4}}
                                   {{1,3},{2,3}}
                                   {{2},{1,2,2}}
                                   {{3},{1,2,3}}
                                   {{1},{1},{2,3}}
                                   {{1},{2},{1,2}}
                                   {{1},{2},{3,4}}
                                   {{1},{3},{2,3}}
                                   {{2},{2},{1,2}}
                                   {{1},{1},{1},{1}}
                                   {{1},{1},{2},{2}}
                                   {{1},{2},{2},{2}}
                                   {{1},{2},{3},{3}}
                                   {{1},{2},{3},{4}}

Andrew Howroyd, Table of n, a(n) for n = 0..50

Cf. A000740, A000837, A007716, A007916, A100953, A301700, A303386, A303546, A303707, A303708, A303709, A303710, A320800-A320810.

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t, k)={EulerT(Vec(sum(j=1, #q, gcd(t, q[j])*x^lcm(t, q[j])) + O(x*x^k), -k))}
a(n)={if(n==0, 1, my(mbt=vector(n, d, moebius(d)), s=0); forpart(q=n, s+=permcount(q)*polcoef(exp(x*Ser(dirmul(mbt, sum(t=1, n, K(q, t, n)/t)))), n)); s/n!)} \\ Andrew Howroyd, Jan 16 2023

Terms a(11) and beyond from Andrew Howroyd, Jan 16 2023

A320805 Number of non-isomorphic multiset partitions of weight n in which each part, as well as the multiset union of the parts, is an aperiodic multiset.

Original entry on oeis.org

1, 1, 2, 6, 16, 55, 139, 516, 1500, 5269, 17017

Offset: 0

Gus Wiseman, Nov 07 2018

Also the number of nonnegative integer matrices up to row and column permutations with sum of elements equal to n and no zero rows or columns, in which (1) the positive entries in each row are relatively prime and (2) the column sums are relatively prime.
A multiset is aperiodic if its multiplicities are relatively prime.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(1) = 1 through a(4) = 16 multiset partitions:
  {{1}}  {{1,2}}    {{1,2,2}}      {{1,2,2,2}}
         {{1},{2}}  {{1,2,3}}      {{1,2,3,3}}
                    {{1},{2,3}}    {{1,2,3,4}}
                    {{2},{1,2}}    {{1},{2,3,3}}
                    {{1},{2},{2}}  {{1},{2,3,4}}
                    {{1},{2},{3}}  {{1,2},{3,4}}
                                   {{1,3},{2,3}}
                                   {{2},{1,2,2}}
                                   {{3},{1,2,3}}
                                   {{1},{1},{2,3}}
                                   {{1},{2},{3,4}}
                                   {{1},{3},{2,3}}
                                   {{2},{2},{1,2}}
                                   {{1},{2},{2},{2}}
                                   {{1},{2},{3},{3}}
                                   {{1},{2},{3},{4}}

Cf. A000740, A000837, A007716, A007916, A100953, A301700, A303386, A303546, A303707, A303708, A303710, A320800-A320810, A321283.

cp's OEIS Frontend

A303707 Number of factorizations of n using elements of A007916 (numbers that are not perfect powers).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A294068 Number of factorizations of n using perfect powers (elements of A001597) other than 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A303708 Number of aperiodic factorizations of n using elements of A007916 (numbers that are not perfect powers).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A303709 Number of periodic factorizations of n using elements of A007916 (numbers that are not perfect powers).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A320803 Number of non-isomorphic multiset partitions of weight n in which all parts are aperiodic multisets.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A320805 Number of non-isomorphic multiset partitions of weight n in which each part, as well as the multiset union of the parts, is an aperiodic multiset.

Views

Author

Keywords

Comments

Examples

Crossrefs