A303431 -id:A303431 - cp's OEIS frontend

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

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)).

A303547 Number of non-isomorphic periodic multiset partitions of weight n.

Original entry on oeis.org

0, 1, 1, 4, 1, 13, 1, 33, 10, 94, 1, 327, 1, 913, 100, 3017, 1, 10233, 1, 34236, 919, 119372, 1, 432234, 91, 1574227, 9945, 5916177, 1, 22734231, 1, 89003059, 119378, 356058543, 1000, 1453509039, 1, 6044132797, 1574233, 25612601420, 1, 110509543144, 1, 485161348076

Offset: 1

Gus Wiseman, Apr 26 2018

nonn

A multiset is periodic if its multiplicities have a common divisor greater than 1. For this sequence neither the parts nor their multiset union are required to be periodic, only the multiset of parts.

			Non-isomorphic representatives of the a(4) = 4 multiset partitions are {{1,1},{1,1}}, {{1,2},{1,2}}, {{1},{1},{1},{1}}, {{1},{1},{2},{2}}.

Cf. A000740, A000837, A001055, A007716, A007916, A049311, A100953, A255906, A269134, A275024, A293993, A301700, A303386, A303431, A303546.

a(n) = 1 if n is prime.

a(n) = A007716(n) - A303546(n).

More terms from Jinyuan Wang, Jun 21 2020

A305150 Number of factorizations of n into distinct, pairwise indivisible factors greater than 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 1, 2, 1, 5, 1, 1, 2, 2, 2, 2, 1, 2, 2, 3, 1, 5, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 1, 3, 2, 3, 2, 2, 1, 6, 1, 2, 2, 1, 2, 5, 1, 2, 2, 5, 1, 3, 1, 2, 2, 2, 2, 5, 1, 3, 1, 2, 1, 6, 2, 2, 2, 3, 1, 6, 2, 2, 2, 2, 2, 4, 1, 2, 2, 2, 1, 5, 1, 3, 5

Offset: 1

Gus Wiseman, May 26 2018

nonn

			The a(60) = 6 factorizations are (3 * 4 * 5), (3 * 20), (4 * 15), (5 * 12), (6 * 10), (60). Missing from this list are (2 * 3 * 10), (2 * 5 * 6), (2 * 30).

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Cf. A001055, A001970, A007716, A045778, A162247, A259936, A275024, A285572, A281113, A281116, A303386, A303431, A305001, A305148, A305149, A305253.

facs[n_] := If[n <= 1, {{}}, Join@@Table[Map[Prepend[#, d] &, Select[facs[n/d], Min@@ # >= d &]], {d, Rest[Divisors[n]]}]]; Table[Length[Select[facs[n], UnsameQ@@ # && Select[Tuples[Union[#], 2], UnsameQ@@ # && Divisible@@ # &] == {} &]], {n, 100}]

A305150(n, m=n, facs=List([])) = if(1==n, 1, my(s=0, newfacs); fordiv(n, d, if((d>1)&&(d<=m)&&factorback(apply(x -> (x%d),Vec(facs))), newfacs = List(facs); listput(newfacs,d); s += A305150(n/d, d-1, newfacs))); (s)); \\ Antti Karttunen, Dec 06 2018

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

More terms from Antti Karttunen, Dec 06 2018

A321283 Number of non-isomorphic multiset partitions of weight n in which the part sizes are relatively prime.

Original entry on oeis.org

1, 1, 2, 7, 21, 84, 214, 895, 2607, 9591, 31134, 119313, 400950, 1574123, 5706112, 22572991, 86933012, 356058243, 1427784135, 6044132304, 25342935667, 110414556330, 481712291885, 2166488898387, 9784077216457, 45369658599779, 211869746691055, 1011161497851296, 4871413403219085

Offset: 0

Gus Wiseman, Nov 06 2018

nonn

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 the row sums are relatively prime.
Also the number of non-isomorphic multiset partitions of weight n in which the multiset union of the parts is aperiodic, where 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 relatively prime part-sizes:
  {{1}}  {{1},{1}}  {{1},{1,1}}    {{1},{1,1,1}}
         {{1},{2}}  {{1},{2,2}}    {{1},{1,2,2}}
                    {{1},{2,3}}    {{1},{2,2,2}}
                    {{2},{1,2}}    {{1},{2,3,3}}
                    {{1},{1},{1}}  {{1},{2,3,4}}
                    {{1},{2},{2}}  {{2},{1,2,2}}
                    {{1},{2},{3}}  {{3},{1,2,3}}
                                   {{1},{1},{1,1}}
                                   {{1},{1},{2,2}}
                                   {{1},{1},{2,3}}
                                   {{1},{2},{1,2}}
                                   {{1},{2},{2,2}}
                                   {{1},{2},{3,3}}
                                   {{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}}
Non-isomorphic representatives of the a(1) = 1 through a(4) = 21 multiset partitions with aperiodic multiset union:
  {{1}}  {{1,2}}    {{1,2,2}}      {{1,2,2,2}}
         {{1},{2}}  {{1,2,3}}      {{1,2,3,3}}
                    {{1},{2,2}}    {{1,2,3,4}}
                    {{1},{2,3}}    {{1},{2,2,2}}
                    {{2},{1,2}}    {{1,2},{2,2}}
                    {{1},{2},{2}}  {{1},{2,3,3}}
                    {{1},{2},{3}}  {{1,2},{3,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},{2,2}}
                                   {{1},{2},{3,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}}

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

Cf. A000740, A000837, A007716, A007916, A100953, A301700, A303386, A303431, A303546, A303547, A320800-A320810.

\\ See links in A339645 for combinatorial species functions.
seq(n)={my(A=symGroupSeries(n)); NumUnlabeledObjsSeq(sCartProd(sExp(A), 1 + sum(d=1, n, moebius(d) * (-1 + sExp(O(x*x^n) + sum(i=1, n\d, polcoef(A,i*d)*x^(i*d)))) )))} \\ Andrew Howroyd, Jan 17 2023

\\ faster self contained program.
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, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k))}
a(n)={if(n==0, 1, my(s=0); forpart(q=n, my(u=vector(n, t, K(q, t, n\t))); s+=permcount(q)*polcoef(sum(d=1, n, moebius(d)*exp(sum(t=1, n\d, sum(i=1, n\(t*d), u[t][i*d]*x^(i*d*t))/t, O(x*x^n)) )), n)); s/n!)} \\ Andrew Howroyd, Jan 17 2023

a(n) = A007716(n) - A320810(n). - Andrew Howroyd, Jan 17 2023

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

A317709 Aperiodic relatively prime tree numbers. Matula-Goebel numbers of aperiodic relatively prime trees.

Original entry on oeis.org

1, 2, 3, 5, 6, 10, 11, 12, 13, 15, 18, 20, 22, 24, 26, 29, 30, 31, 33, 37, 40, 41, 44, 45, 47, 48, 50, 52, 54, 55, 58, 60, 61, 62, 66, 71, 72, 74, 75, 78, 79, 80, 82, 88, 89, 90, 93, 94, 96, 99, 101, 104, 108, 109, 110, 113, 116, 120, 122, 123, 124, 127, 130

Offset: 1

Gus Wiseman, Aug 05 2018

nonn

A positive integer n is in the sequence iff either n = 1 or n is a prime number whose prime index already belongs to the sequence or n is not a perfect power and its prime indices are relatively prime numbers already belonging to the sequence. A prime index of n is a number m such that prime(m) divides n.

			The sequence of aperiodic relatively prime tree numbers together with their Matula-Goebel trees begins:
   1: o
   2: (o)
   3: ((o))
   5: (((o)))
   6: (o(o))
  10: (o((o)))
  11: ((((o))))
  12: (oo(o))
  13: ((o(o)))
  15: ((o)((o)))
  18: (o(o)(o))
  20: (oo((o)))
  22: (o(((o))))
  24: (ooo(o))
  26: (o(o(o)))
  29: ((o((o))))
  30: (o(o)((o)))
  31: (((((o)))))

Cf. A000081, A061775, A111299, A214577, A276625, A277098, A301700, A303431, A316503.

Cf. A317705, A317707, A317708, A317710, A317711, A317712.

rupQ[n_]:=Or[n==1,If[PrimeQ[n],rupQ[PrimePi[n]],And[GCD@@FactorInteger[n][[All,2]]==1,GCD@@PrimePi/@FactorInteger[n][[All,1]]==1,And@@rupQ/@PrimePi/@FactorInteger[n][[All,1]]]]];
Select[Range[100],rupQ]

A317711 Numbers that are not uniform tree numbers.

Original entry on oeis.org

12, 18, 20, 24, 28, 37, 40, 44, 45, 48, 50, 52, 54, 56, 60, 61, 63, 68, 71, 72, 74, 75, 76, 80, 84, 88, 89, 90, 92, 96, 98, 99, 104, 107, 108, 111, 112, 116, 117, 120, 122, 124, 126, 132, 135, 136, 140, 142, 144, 147, 148, 150, 152, 153, 156, 157, 160, 162

Offset: 1

Gus Wiseman, Aug 05 2018

nonn

A positive integer n is a uniform tree number iff either n = 1 or n is a power of a squarefree number whose prime indices are also uniform tree numbers. A prime index of n is a number m such that prime(m) divides n.

			The sequence of non-uniform tree numbers together with their Matula-Goebel trees begins:
  12: (oo(o))
  18: (o(o)(o))
  20: (oo((o)))
  24: (ooo(o))
  28: (oo(oo))
  37: ((oo(o)))
  40: (ooo((o)))
  44: (oo(((o))))
  45: ((o)(o)((o)))
  48: (oooo(o))
  50: (o((o))((o)))
  52: (oo(o(o)))
  54: (o(o)(o)(o))
  56: (ooo(oo))
  60: (oo(o)((o)))

Cf. A061775, A072774, A111299, A214577, A276625, A277098, A303431, A317590.

Cf. A317705, A317707, A317708, A317709, A317710 (complement), A317712, A317717, A317718.

rupQ[n_]:=Or[n==1,And[SameQ@@FactorInteger[n][[All,2]],And@@rupQ/@PrimePi/@FactorInteger[n][[All,1]]]];
Select[Range[100],!rupQ[#]&]

A320800 Number of non-isomorphic multiset partitions of weight n in which both the multiset union of the parts and the multiset union of the dual parts are aperiodic.

Original entry on oeis.org

1, 1, 1, 5, 14, 78, 157, 881, 2267, 9257, 28397

Offset: 0

Gus Wiseman, Nov 02 2018

The latter condition is equivalent to the parts having relatively prime sizes.
A multiset is aperiodic if its multiplicities are relatively prime.
The dual of a multiset partition has, for each vertex, one part consisting of the indices (or positions) of the parts containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,2}} is {{1},{1,2,2}}.
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) = 14 multiset partitions:
  {{1}}  {{1},{2}}  {{1},{2,2}}    {{1},{2,2,2}}
                    {{1},{2,3}}    {{1},{2,3,3}}
                    {{2},{1,2}}    {{1},{2,3,4}}
                    {{1},{2},{2}}  {{2},{1,2,2}}
                    {{1},{2},{3}}  {{3},{1,2,3}}
                                   {{1},{1},{2,3}}
                                   {{1},{2},{2,2}}
                                   {{1},{2},{3,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, A303431, A303546, A303547, A316983, A320801-A320810.

A324766 Matula-Goebel numbers of recursively anti-transitive rooted trees.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 16, 17, 19, 20, 21, 22, 23, 25, 27, 29, 31, 32, 33, 34, 35, 40, 44, 46, 49, 50, 51, 53, 57, 59, 62, 63, 64, 67, 68, 71, 73, 77, 79, 80, 81, 83, 85, 87, 88, 92, 93, 95, 97, 99, 100, 103, 109, 115, 118, 121, 124, 125, 127, 128

Offset: 1

Gus Wiseman, Mar 17 2019

nonn

The complement is {6, 12, 13, 14, 15, 18, 24, 26, 28, 30, 36, ...}.

An unlabeled rooted tree is recursively anti-transitive if no branch of a branch of a terminal subtree is a branch of the same subtree.

			The sequence of recursively anti-transitive rooted trees together with their Matula-Goebel numbers begins:
   1: o
   2: (o)
   3: ((o))
   4: (oo)
   5: (((o)))
   7: ((oo))
   8: (ooo)
   9: ((o)(o))
  10: (o((o)))
  11: ((((o))))
  16: (oooo)
  17: (((oo)))
  19: ((ooo))
  20: (oo((o)))
  21: ((o)(oo))
  22: (o(((o))))
  23: (((o)(o)))
  25: (((o))((o)))
  27: ((o)(o)(o))
  29: ((o((o))))
  31: (((((o)))))
  32: (ooooo)
  33: ((o)(((o))))
  34: (o((oo)))
  35: (((o))(oo))
  40: (ooo((o)))
  44: (oo(((o))))
  46: (o((o)(o)))
  49: ((oo)(oo))
  50: (o((o))((o)))

Cf. A007097, A000081, A290689, A303431, A304360, A306844, A316502, A318186.

Cf. A324695, A324751, A324756, A324758, A324765, A324767, A324769, A324838, A324841, A324844.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
totantiQ[n_]:=And[Intersection[Union@@primeMS/@primeMS[n],primeMS[n]]=={},And@@totantiQ/@primeMS[n]];
Select[Range[100],totantiQ]

A304486 Number of inequivalent leaf-colorings of the unlabeled rooted tree with Matula-Goebel number n.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 2, 3, 2, 2, 1, 4, 2, 4, 2, 5, 2, 4, 3, 4, 4, 2, 2, 7, 2, 5, 3, 9, 2, 5, 1, 7, 2, 4, 4, 9, 4, 7, 5, 7, 2, 11, 4, 4, 4, 4, 2, 12, 7, 4, 4, 11, 5, 7, 2, 16, 7, 5, 2, 11, 4, 2, 9, 11, 5, 5, 3, 9, 4, 11

Offset: 1

Gus Wiseman, Aug 17 2018

			Inequivalent representatives of the a(52) = 11 colorings of the tree (oo(o(o))) are the following.
  (11(1(1)))
  (11(1(2)))
  (11(2(1)))
  (11(2(2)))
  (11(2(3)))
  (12(1(1)))
  (12(1(2)))
  (12(1(3)))
  (12(3(1)))
  (12(3(3)))
  (12(3(4)))

Cf. A000081, A001678, A004111, A007097, A049076, A061773, A061775, A109082, A109129, A300626, A303024, A303431, A317713, A317994.

A303551 Number of aperiodic multisets of compositions of total weight n.

Original entry on oeis.org

1, 2, 6, 15, 41, 95, 243, 567, 1366, 3189, 7532, 17428, 40590, 93465, 215331, 493150, 1127978, 2569049, 5841442, 13240351, 29953601, 67596500, 152258270, 342235866, 767895382, 1719813753, 3845442485, 8584197657, 19133459138, 42583565928, 94641591888

Offset: 1

Gus Wiseman, Apr 26 2018

nonn

A multiset is aperiodic if its multiplicities are relatively prime.

			The a(4) = 15 aperiodic multisets of compositions are:
{4}, {31}, {22}, {211}, {13}, {121}, {112}, {1111},
{1,3}, {1,21}, {1,12}, {1,111}, {2,11},
{1,1,2}, {1,1,11}.
Missing from this list are {1,1,1,1}, {2,2}, and {11,11}.

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Cf. A000740, A000837, A007716, A007916, A034691, A100953, A255906, A269134, A301700, A303386, A303431, A303546, A303552.

with(numtheory):
b:= proc(n) option remember; `if`(n=0, 1, add(add(
      d*2^(d-1), d=divisors(j))*b(n-j), j=1..n)/n)
    end:
a:= n-> add(mobius(d)*b(n/d), d=divisors(n)):
seq(a(n), n=1..35);  # Alois P. Heinz, Apr 26 2018

nn=20;
ser=Product[1/(1-x^n)^2^(n-1),{n,nn}]
Table[Sum[MoebiusMu[d]*SeriesCoefficient[ser,{x,0,n/d}],{d,Divisors[n]}],{n,1,nn}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(u=EulerT(vector(n, n, 2^(n-1)))); vector(n, n, sumdiv(n, d, moebius(d)*u[n/d]))} \\ Andrew Howroyd, Sep 15 2018

a(n) = Sum_{d|n} mu(d) * A034691(n/d).

cp's OEIS Frontend

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

A303547 Number of non-isomorphic periodic multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A305150 Number of factorizations of n into distinct, pairwise indivisible factors greater than 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A321283 Number of non-isomorphic multiset partitions of weight n in which the part sizes are relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A317709 Aperiodic relatively prime tree numbers. Matula-Goebel numbers of aperiodic relatively prime trees.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A317711 Numbers that are not uniform tree numbers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A320800 Number of non-isomorphic multiset partitions of weight n in which both the multiset union of the parts and the multiset union of the dual parts are aperiodic.

Views

Author

Keywords

Comments

Examples

Crossrefs

A324766 Matula-Goebel numbers of recursively anti-transitive rooted trees.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A304486 Number of inequivalent leaf-colorings of the unlabeled rooted tree with Matula-Goebel number n.