A292886 -id:A292886 - cp's OEIS frontend

A325990 Numbers with more than one perfect factorization.

8, 24, 27, 32, 40, 54, 56, 72, 88, 96, 104, 108, 120, 125, 128, 135, 136, 152, 160, 168, 184, 189, 200, 216, 224, 232, 243, 248, 250, 256, 264, 270, 280, 288, 296, 297, 312, 328, 343, 344, 351, 352, 360, 375, 376, 378, 384, 392, 408, 416, 424, 432, 440, 456

Offset: 1

Gus Wiseman, May 30 2019

nonn

First differs from A060476 in lacking 1 and having 432.

A perfect factorization of n is an orderless factorization of n into factors > 1 such that every divisor of n is the product of exactly one submultiset of the factors. This is the intersection of covering (or complete) factorizations (A325988) and knapsack factorizations (A292886).

Positions of terms > 1 in A325989.

Cf. A002033, A292886, A325780, A325781, A325782, A325787, A325789, A325988.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Select[Range[100],Function[n,Length[Select[facs[n],Sort[Times@@@Union[Subsets[#]]]==Divisors[n]&]]>1]]

A294150 Number of knapsack partitions of n that are also knapsack factorizations.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 4, 6, 8, 10, 12, 13, 20, 20, 29, 30, 41, 41, 56, 53, 81, 75

Offset: 1

Gus Wiseman, Oct 23 2017

a(n) is the number of finite multisets of positive integers summing to n such that every distinct submultiset has a different sum, and also every distinct submultiset has a different product.

			The a(12) = 13 partitions are:
(12),
(10 2), (9 3), (8 4), (7 5), (6 6),
(8 2 2), (7 3 2), (5 5 2), (5 4 3), (4 4 4),
(3 3 3 3),
(2 2 2 2 2 2).

R. Ehrenborg and M. Readdy, The Mobius function of partitions with restricted block sizes, Advances in Applied Mathematics, Volume 39, Issue 3, September 2007, Pages 283-292.

Cf. A000041, A001055, A108917, A275972, A292886, A293627.

nn=22;
dubQ[y_]:=And[UnsameQ@@Times@@@Union[Rest@Subsets[y]],UnsameQ@@Plus@@@Union[Rest@Subsets[y]]];
Table[Length@Select[IntegerPartitions[n],dubQ],{n,nn}]

A325989 Number of perfect factorizations of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Gus Wiseman, May 30 2019

nonn

A perfect factorization of n is an orderless factorization of n into factors > 1 such that every divisor of n is the product of exactly one submultiset of the factors. This is the intersection of covering (or complete) factorizations (A325988) and knapsack factorizations (A292886).

			The a(216) = 4 perfect factorizations:
  (2*2*2*3*3*3)
  (2*2*2*3*9)
  (2*3*3*3*4)
  (2*3*4*9)

Positions of terms > 1 are A325990.

Cf. A002033, A103300, A292886, A325685, A325780, A325787, A325789, A325988.

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],Sort[Times@@@Union[Subsets[#]]]==Divisors[n]&]],{n,100}]

a(2^n) = A002033(n).

A347709 Number of distinct rational numbers of the form x * z / y for some factorization x * y * z = n, 1 < x <= y <= z.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Oct 14 2021

nonn

This is also the number of distinct possible alternating products of length-3 factorizations of n, where we define the alternating product of a sequence (y_1,...,y_k) to be Product_i y_i^((-1)^(i-1)), and where a factorization of n is a weakly increasing sequence of positive integers > 1 with product n.

			Representative factorizations for each of the a(360) = 9 alternating products:
   (2,2,90) -> 90
   (2,3,60) -> 40
   (2,4,45) -> 45/2
   (2,5,36) -> 72/5
   (2,6,30) -> 10
   (2,9,20) -> 40/9
  (2,10,18) -> 18/5
  (2,12,15) -> 5/2
   (3,8,15) -> 45/8

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

Allowing factorizations of any length <= 3 gives A033273.
Positions of positive terms are A033942.
Positions of 0's are A037143.
The length-2 version is A072670.
Allowing any length gives A347460, reverse A038548.
Allowing any odd length gives A347708.
A001055 counts factorizations (strict A045778, ordered A074206).
A122179 counts length-3 factorizations.
A292886 counts knapsack factorizations, by sum A293627.
A301957 counts distinct subset-products of prime indices.
A304792 counts distinct subset-sums of partitions, positive A276024.
Cf. A000040, A001358, A002033, A046951, A339846, A339890, A347437, A347438, A347439, A347440, A347442, A347456, A347461.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
altprod[q_]:=Product[q[[i]]^(-1)^(i-1),{i,Length[q]}];
Table[Length[Union[altprod/@Select[facs[n],Length[#]==3&]]],{n,100}]

A347709(n) = { my(rats=List([])); fordiv(n,z,my(yx=n/z); fordiv(yx, y, my(x = yx/y); if((y <= z) && (x <= y) && (x > 1), listput(rats,x*z/y)))); #Set(rats); }; \\ Antti Karttunen, Jan 29 2025

More terms from Antti Karttunen, Jan 29 2025

A301970 Heinz numbers of integer partitions with more subset-products than subset-sums.

Original entry on oeis.org

165, 273, 325, 351, 495, 525, 561, 595, 675, 741, 765, 819, 825, 931, 1045, 1053, 1155, 1173, 1425, 1485, 1495, 1575, 1625, 1653, 1683, 1771, 1785, 1815, 1911, 2025, 2139, 2145, 2223, 2275, 2277, 2295, 2310, 2415, 2457, 2465, 2475, 2625, 2639, 2695, 2805, 2945

Offset: 1

Gus Wiseman, Mar 29 2018

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). A subset-sum (or subset-product) of a multiset y is any number equal to the sum (or product) of some submultiset of y.

Numbers n such that A301957(n) > A299701(n).

			Sequence of partitions begins: (532), (642), (633), (6222), (5322), (4332), (752), (743), (33222), (862), (7322), (6422), (5332), (844), (853), (62222), (5432), (972), (8332), (53222), (963), (43322), (6333).

Cf. A000712, A003963, A056239, A108917, A276024, A284640, A292886, A296150, A299701, A299702, A299729, A301854, A301855, A301856, A301957, A301979.

Select[Range[1000],With[{ptn=If[#===1,{},Join@@Cases[FactorInteger[#],{p_,k_}:>Table[PrimePi[p],{k}]]]},Length[Union[Times@@@Subsets[ptn]]]>Length[Union[Plus@@@Subsets[ptn]]]]&]

A316364 Number of factorizations of n into factors > 1 such that every distinct submultiset of the factors has a different average.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Jun 30 2018

nonn

Note that such a factorization is necessarily strict.

			The a(80) = 6 factorizations are (80), (10*8), (16*5), (20*4), (40*2), (10*4*2).

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

Cf. A001055, A108917, A275972, A276024, A284640, A292886, A293627, A294150, A316313, A316314, A316365.

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@@Mean/@Union[Subsets[#]]&]],{n,50}]

choosebybits(v,m) = { my(s=vector(hammingweight(m)),i=j=1); while(m>0,if(m%2,s[j] = v[i];j++); i++; m >>= 1); s; };
hasdupavgs(v) = { my(avgs=Map(), k); for(i=1,(2^(#v))-1,k = (vecsum(choosebybits(v,i))/hammingweight(i)); if(mapisdefined(avgs,k),return(i),mapput(avgs,k,i))); (0); };
A316364(n, m=n, facs=List([])) = if(1==n, (0==hasdupavgs(Vec(facs))), my(s=0, newfacs); fordiv(n, d, if((d>1)&&(d<=m), newfacs = List(facs); listput(newfacs,d); s += A316364(n/d, d, newfacs))); (s)); \\ Antti Karttunen, Sep 21 2018

More terms from Antti Karttunen, Sep 21 2018

A316365 Number of factorizations of n into factors > 1 such that every distinct subset of the factors has a different sum.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 4, 1, 4, 1, 4, 2, 2, 1, 7, 2, 2, 3, 4, 1, 4, 1, 6, 2, 2, 2, 9, 1, 2, 2, 7, 1, 5, 1, 4, 4, 2, 1, 9, 2, 4, 2, 4, 1, 6, 2, 7, 2, 2, 1, 10, 1, 2, 4, 9, 2, 5, 1, 4, 2, 4, 1, 14, 1, 2, 4, 4, 2, 5, 1, 11, 5, 2, 1, 9, 2, 2, 2, 7, 1, 10, 2, 4, 2, 2, 2, 15, 1, 4, 4, 9, 1, 5, 1, 7, 5

Offset: 1

Gus Wiseman, Jun 30 2018

nonn

Also the number of factorizations of n into factors > 1 which form a knapsack partition.

			The a(24) = 7 factorizations are (2*2*2*3), (2*2*6), (2*3*4), (2*12), (3*8), (4*6), (24).
The a(54) = 6 factorizations are (2*3*3*3), (2*3*9), (2*27), (3*18), (6*9), (54).

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

Cf. A001055, A108917, A275972, A292886, A293627, A294150, A299702, A316313, A316314, A316364.

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@@Total/@Union[Subsets[#]]&]],{n,100}]

primeprodbybits(v,b) = { my(m=1,i=1); while(b>0,if(b%2, m *= prime(v[i])); i++; b >>= 1); (m); };
sumbybits(v,b) = { my(s=0,i=1); while(b>0,s += (b%2)*v[i]; i++; b >>= 1); (s); };
all_distinct_subsets_have_different_sums(v) = { my(m=Map(),s,pp); for(i=0,(2^#v)-1, pp = primeprodbybits(v,i); s = sumbybits(v,i); if(mapisdefined(m,s), if(mapget(m,s)!=pp, return(0)), mapput(m,s,pp))); (1); };
A316365(n, m=n, facs=List([])) = if(1==n, all_distinct_subsets_have_different_sums(Vec(facs)), my(s=0, newfacs); fordiv(n, d, if((d>1)&&(d<=m), newfacs = List(facs); listput(newfacs,d); s += A316365(n/d, d, newfacs))); (s)); \\ Antti Karttunen, Oct 08 2018

More terms from Antti Karttunen, Oct 08 2018

A321143 Number of non-isomorphic knapsack multiset partitions of weight n.

Original entry on oeis.org

1, 1, 4, 10, 31, 87, 272, 835, 2673, 8805, 29583

Offset: 0

Gus Wiseman, Oct 28 2018

A multiset partition is knapsack if every distinct submultiset of the parts has a different multiset union.

			Non-isomorphic representatives of the a(1) = 1 through a(4) = 31 knapsack multiset partitions:
  {{1}}  {{1,1}}    {{1,1,1}}      {{1,1,1,1}}
         {{1,2}}    {{1,2,2}}      {{1,1,2,2}}
         {{1},{1}}  {{1,2,3}}      {{1,2,2,2}}
         {{1},{2}}  {{1},{1,1}}    {{1,2,3,3}}
                    {{1},{2,2}}    {{1,2,3,4}}
                    {{1},{2,3}}    {{1},{1,1,1}}
                    {{2},{1,2}}    {{1,1},{1,1}}
                    {{1},{1},{1}}  {{1},{1,2,2}}
                    {{1},{2},{2}}  {{1,1},{2,2}}
                    {{1},{2},{3}}  {{1,2},{1,2}}
                                   {{1},{2,2,2}}
                                   {{1,2},{2,2}}
                                   {{1},{2,3,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,2}}
                                   {{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},{1},{1},{1}}
                                   {{1},{1},{2},{2}}
                                   {{1},{2},{2},{2}}
                                   {{1},{2},{3},{3}}
                                   {{1},{2},{3},{4}}
Missing from this list are {{1},{1},{1,1}} and {{1},{2},{1,2}}, which are not knapsack.

Cf. A002219, A006827, A007716, A108917, A275972, A276024, A292886, A316983, A319616.

A323086 Number of factorizations of n into factors > 1 such that no factor is a power of any other (unequal) factor.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 4, 1, 2, 2, 3, 1, 4, 1, 4, 2, 2, 1, 6, 2, 2, 2, 4, 1, 5, 1, 3, 2, 2, 2, 9, 1, 2, 2, 6, 1, 5, 1, 4, 4, 2, 1, 9, 2, 4, 2, 4, 1, 6, 2, 6, 2, 2, 1, 11, 1, 2, 4, 4, 2, 5, 1, 4, 2, 5, 1, 14, 1, 2, 4, 4, 2, 5, 1, 9, 3, 2, 1, 11, 2, 2

Offset: 1

Gus Wiseman, Jan 04 2019

nonn

			The a(72) = 14 factorizations:
  (2*2*2*3*3),
  (2*2*2*9), (2*2*3*6),
  (2*2*18), (2*3*12), (2*6*6), (3*3*8), (3*4*6),
  (2*36), (3*24), (4*18), (6*12), (8*9),
  (72).

Cf. A001055, A001597, A002865, A007916, A052410, A101417, A292886, A303707, A305149, A323053, A323087.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[facs[n],stableQ[Union[#],IntegerQ[Log[#1,#2]]&]&]],{n,100}]

A323091 Number of strict knapsack factorizations of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 2, 2, 1, 3, 1, 3, 2, 2, 1, 5, 1, 2, 2, 3, 1, 5, 1, 3, 2, 2, 2, 4, 1, 2, 2, 5, 1, 5, 1, 3, 3, 2, 1, 7, 1, 3, 2, 3, 1, 5, 2, 5, 2, 2, 1, 9, 1, 2, 3, 3, 2, 5, 1, 3, 2, 5, 1, 9, 1, 2, 3, 3, 2, 5, 1, 7, 2, 2, 1, 9, 2, 2, 2

Offset: 1

Gus Wiseman, Jan 04 2019

nonn

A strict knapsack factorization is a finite set of positive integers > 1 such that every subset has a different product.

			The a(144) = 11 factorizations:
  (144),
  (2*72), (3*48), (4*36),(6*24), (8*18), (9*16),
  (2*3*24), (2*4*18), (2*8*9), (3*6*8).
Missing from this list are (2*6*12), (3*4*12), (2*3*4*6), which are not knapsack.

Cf. A001055, A045778, A108917, A120641, A275972, A292886, A305150, A323087.

strfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[strfacs[n/d],Min@@#>d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[strfacs[n],UnsameQ@@Times@@@Subsets[#]&]],{n,100}]

a(prime^n) = A275972(n).

cp's OEIS Frontend

A325990 Numbers with more than one perfect factorization.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A294150 Number of knapsack partitions of n that are also knapsack factorizations.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A325989 Number of perfect factorizations of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A347709 Number of distinct rational numbers of the form x * z / y for some factorization x * y * z = n, 1 < x <= y <= z.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A301970 Heinz numbers of integer partitions with more subset-products than subset-sums.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A316364 Number of factorizations of n into factors > 1 such that every distinct submultiset of the factors has a different average.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A316365 Number of factorizations of n into factors > 1 such that every distinct subset of the factors has a different sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A321143 Number of non-isomorphic knapsack multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples