A318948 -id:A318948 - cp's OEIS frontend

A066739 Number of representations of n as a sum of products of positive integers. 1 is not allowed as a factor, unless it is the only factor. Representations which differ only in the order of terms or factors are considered equivalent.

1, 1, 2, 3, 6, 8, 14, 19, 32, 44, 67, 91, 139, 186, 269, 362, 518, 687, 960, 1267, 1747, 2294, 3106, 4052, 5449, 7063, 9365, 12092, 15914, 20422, 26639, 34029, 44091, 56076, 72110, 91306, 116808, 147272, 187224, 235201, 297594, 372390, 468844, 584644, 732942

Offset: 0

Naohiro Nomoto, Jan 16 2002

			For n=5, 5 = 4+1 = 2*2+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1, so a(5) = 8.
For n=8, 8 = 4*2 = 2*2*2 = ... = 4+4 = 2*2+4 = 2*2+2*2 = ...; note that there are 3 ways to factor the terms of 4+4. In general, if a partition contains a number k exactly r times, then the number of ways to factor the k's is the binomial coefficient C(A001055(k)+r-1,r).

Alois P. Heinz, Table of n, a(n) for n = 0..10000
N. J. A. Sloane, Transforms

Cf. A000041, A001055.
Cf. A066815, A066816, A066806.
Cf. A001970, A050336, A063834, A065026, A066739, A281113, A284639, A318948, A318949.

with(numtheory):
b:= proc(n, k) option remember;
      `if`(n>k, 0, 1) +`if`(isprime(n), 0,
      add(`if`(d>k, 0, b(n/d, d)), d=divisors(n) minus {1, n}))
    end:
a:= proc(n) option remember;
      `if`(n=0, 1, add(add(d*b(d, d), d=divisors(j)) *a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..60); # Alois P. Heinz, Apr 22 2012

p[ n_, 1 ] := If[ n==1, 1, 0 ]; p[ 1, k_ ] := 1; p[ n_, k_ ] := p[ n, k ]=p[ n, k-1 ]+If[ Mod[ n, k ]==0, p[ n/k, k ], 0 ]; A001055[ n_ ] := p[ n, n ]; a[ n_, 1 ] := 1; a[ 0, k_ ] := 1; a[ n_, k_ ] := If[ k>n, a[ n, n ], a[ n, k ]=a[ n, k-1 ]+Sum[ Binomial[ A001055[ k ]+r-1, r ]a[ n-k*r, k-1 ], {r, 1, Floor[ n/k ]} ] ]; a[ n_ ] := a[ n, n ]; (* p[ n, k ]=number of factorizations of n with factors <= k. a[ n, k ]=number of representations of n as a sum of products of positive integers, with summands <= k *)
b[n_, k_] := b[n, k] = If[n>k, 0, 1] + If[PrimeQ[n], 0, Sum[If[d>k, 0, b[n/d, d]], {d, Divisors[n] ~Complement~ {1, n}}]]; a[0] = 1; a[n_] := a[n] = If[n == 0, 1, Sum[DivisorSum[j, #*b[#, #]&]*a[n-j], {j, 1, n}]/n]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Nov 10 2015, after Alois P. Heinz *)
facs[n_]:=If[n<=1,{{}},Join@@Table[(Prepend[#1,d]&)/@Select[facs[n/d],Min@@#1>=d&],{d,Rest[Divisors[n]]}]];
Table[Length[Union[Sort/@Join@@Table[Tuples[facs/@ptn],{ptn,IntegerPartitions[n]}]]],{n,50}] (* Gus Wiseman, Sep 05 2018 *)

from sympy.core.cache import cacheit
from sympy import divisors, isprime
@cacheit
def b(n, k): return (0 if n>k else 1) + (0 if isprime(n) else sum([0 if d>k else b(n//d, d) for d in divisors(n)[1:-1]]))
@cacheit
def a(n): return 1 if n==0 else sum(sum(d*b(d, d) for d in divisors(j))*a(n - j)  for j in range(1, n + 1))//n
print([a(n) for n in range(61)]) # Indranil Ghosh, Aug 19 2017, after Maple code

a(n) = Sum_{pi} Product_{m=1..n} binomial(k(m)+A001055(m)-1, k(m)), where pi runs through all partitions k(1) + 2 * k( 2) + ... + n * k(n) = n. a(n)=1/n*Sum_{m=1..n} a(n-m)*b(m), n > 0, a(0)=1, b(m)=Sum_{d|m} d*A001055(d). Euler transform of A001055(n): Product_{m=1..infinity} (1-x^m)^(-A001055(m)). - Vladeta Jovovic, Jan 21 2002

Edited by Dean Hickerson, Jan 19 2002

A318949 Number of ways to write n as an orderless product of orderless sums.

Original entry on oeis.org

1, 2, 3, 8, 7, 17, 15, 36, 36, 56, 56, 123, 101, 165, 197, 310, 297, 490, 490, 767, 837, 1114, 1255, 1925, 1986, 2638, 3110, 4108, 4565, 6201, 6842, 9043, 10311, 12904, 14988, 19398, 21637, 26995, 31488, 39180, 44583, 55418, 63261, 77627, 89914, 108068, 124754

Offset: 1

Gus Wiseman, Sep 05 2018

nonn

			The a(6) = 17 ways:
  (6)              (2)*(3)
  (3+3)            (2)*(2+1)
  (4+2)            (2)*(1+1+1)
  (5+1)            (1+1)*(3)
  (2+2+2)          (1+1)*(2+1)
  (3+2+1)          (1+1)*(1+1+1)
  (4+1+1)
  (2+2+1+1)
  (3+1+1+1)
  (2+1+1+1+1)
  (1+1+1+1+1+1)

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

Cf. A000041, A001055, A001970, A063834, A065026, A066739, A066815, A281113, A284639, A318948.

facs[n_]:=If[n<=1,{{}},Join@@Table[(Prepend[#1,d]&)/@Select[facs[n/d],Min@@#1>=d&],{d,Rest[Divisors[n]]}]];
prodsums[n_]:=Union[Sort/@Join@@Table[Tuples[IntegerPartitions/@fac],{fac,facs[n]}]];
Table[Length[prodsums[n]],{n,30}]

MultEulerT(u)={my(v=vector(#u)); v[1]=1; for(k=2, #u, forstep(j=#v\k*k, k, -k, my(i=j, e=0); while(i%k==0, i/=k; e++; v[j]+=binomial(e+u[k]-1, e)*v[i]))); v}
seq(n)={MultEulerT(vector(n, n, numbpart(n)))} \\ Andrew Howroyd, Oct 26 2019

Dirichlet g.f.: Product_{k>=2} 1 / (1 - k^(-s))^p(k), where p(k) = number of partitions of k (A000041). - Ilya Gutkovskiy, Oct 26 2019

A066815 Number of partitions of n into sums of products.

Original entry on oeis.org

1, 1, 2, 3, 6, 8, 14, 19, 33, 45, 69, 94, 148, 197, 289, 390, 575, 762, 1086, 1439, 2040, 2687, 3712, 4874, 6749, 8792, 11918, 15526, 20998, 27164, 36277, 46820, 62367, 80146, 105569, 135326, 177979, 227139, 296027, 377142, 490554, 622526, 804158

Offset: 0

Vladeta Jovovic, Jan 20 2002

nonn

Number of ways to choose a factorization of each part of an integer partition of n. - Gus Wiseman, Sep 05 2018

This sequence is obtained from the generalized Euler transform in A266964 by taking f(n) = 1, g(n) = A001055(n). - Seiichi Manyama, Nov 14 2018

			From _Gus Wiseman_, Sep 05 2018: (Start)
The a(6) = 14 partitions of 6 into sums of products:
  6, 2*3,
  5+1, 4+2, 2*2+2, 3+3,
  4+1+1, 2*2+1+1, 3+2+1, 2+2+2,
  3+1+1+1, 2+2+1+1,
  2+1+1+1+1,
  1+1+1+1+1+1.
(End)

Seiichi Manyama, Table of n, a(n) for n = 0..10000

Cf. A000041, A001055, A066739, A321460.

Cf. A001970, A050336, A063834, A065026, A281113, A284639, A318948, A318949.

facs[n_]:=If[n<=1,{{}},Join@@Table[(Prepend[#1,d]&)/@Select[facs[n/d],Min@@#1>=d&],{d,Rest[Divisors[n]]}]];
Table[Length[Join@@Table[Tuples[facs/@ptn],{ptn,IntegerPartitions[n]}]],{n,20}] (* Gus Wiseman, Sep 05 2018 *)

G.f.: Product_{k>=1} 1/(1-A001055(k)*x^k).

a(n) = 1/n*Sum_{k=1..n} a(n-k)*b(k), n > 0, a(0)=1, b(k)=Sum_{d|k} d*(A001055(d))^(k/d).

Renamed by T. D. Noe, May 24 2011

A319850 Number of distinct positive integers that can be obtained, starting with the initial interval partition (1, ..., n), by iteratively adding or multiplying together parts until only one part remains.

Original entry on oeis.org

1, 2, 5, 21, 94, 446, 2287, 12568, 78509

Offset: 1

Gus Wiseman, Sep 29 2018

			The n-th row lists all integers that can be obtained starting with (1, ..., n):
  1
  2 3
  5 6 7 8 9
  9 10 11 12 13 14 15 16 17 18 19 20 21 24 25 26 27 28 30 32 36

Cf. A000041, A001055, A001970, A048249, A066739, A066815, A070960, A201163, A318948, A318949, A319841.

ReplaceListRepeated[forms_,rerules_]:=Union[Flatten[FixedPointList[Function[pre,Union[Flatten[ReplaceList[#,rerules]&/@pre,1]]],forms],1]];
Table[Length[Select[ReplaceListRepeated[{Range[n]},{{foe___,x_,mie___,y_,afe___}:>Sort[Append[{foe,mie,afe},x+y]],{foe___,x_,mie___,y_,afe___}:>Sort[Append[{foe,mie,afe},x*y]]}],Length[#]==1&]],{n,6}]

A319909 Number of distinct positive integers that can be obtained by iteratively adding any two or multiplying any two non-1 parts of an integer partition until only one part remains, starting with 1^n.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 4, 5, 10, 15, 21, 34, 49, 68, 101, 142, 197, 280, 387, 538, 751, 1045, 1442, 2010, 2772, 3865, 5339, 7396, 10273, 14201, 19693

Offset: 0

Gus Wiseman, Oct 01 2018

			We have
   7 = 1+1+1+1+1+1+1,
   8 = (1+1)*(1+1+1)+1+1,
   9 = (1+1)*(1+1)*(1+1)+1,
  10 = (1+1+1+1+1)*(1+1),
  12 = (1+1+1)*(1+1+1+1),
so a(7) = 5.

Cf. A000792, A001970, A005520, A048249, A066739, A066815, A070960, A201163, A275870, A319850, A318948, A318949, A319912, A319913.

ReplaceListRepeated[forms_,rerules_]:=Union[Flatten[FixedPointList[Function[pre,Union[Flatten[ReplaceList[#,rerules]&/@pre,1]]],forms],1]];
mexos[ptn_]:=If[Length[ptn]==0,{0},Union@@Select[ReplaceListRepeated[{Sort[ptn]},{{foe___,x_,mie___,y_,afe___}:>Sort[Append[{foe,mie,afe},x+y]],{foe___,x_?(#>1&),mie___,y_?(#>1&),afe___}:>Sort[Append[{foe,mie,afe},x*y]]}],Length[#]==1&]];
Table[Length[mexos[Table[1,{n}]]],{n,30}]

A319855 Minimum number that can be obtained by iteratively adding or multiplying together parts of the integer partition with Heinz number n until only one part remains.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Sep 29 2018

nonn

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

			a(30) = 5 because the minimum number that can be obtained starting with (3,2,1) is 3+2*1 = 5.

Cf. A000792, A001970, A048249, A056239, A066739, A066815, A070960, A201163, A319850, A318948, A318949, A319841, A319856.

ReplaceListRepeated[forms_,rerules_]:=Union[Flatten[FixedPointList[Function[pre,Union[Flatten[ReplaceList[#,rerules]&/@pre,1]]],forms],1]];
nexos[ptn_]:=If[Length[ptn]==0,{0},Union@@Select[ReplaceListRepeated[{Sort[ptn]},{{foe___,x_,mie___,y_,afe___}:>Sort[Append[{foe,mie,afe},x+y]],{foe___,x_,mie___,y_,afe___}:>Sort[Append[{foe,mie,afe},x*y]]}],Length[#]==1&]];
Table[Min[nexos[If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]]],{n,100}]

a(1) = 0, a(n) = max(A056239(n) - A007814(n), 1). - Charlie Neder, Oct 03 2018

A319856 Maximum number that can be obtained by iteratively adding or multiplying together parts of the integer partition with Heinz number n until only one part remains.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Sep 29 2018

nonn

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

			a(30) = 9 because the maximum number that can be obtained starting with (3,2,1) is 3*(2+1) = 9.

Cf. A000792, A001970, A048249, A056239, A066739, A066815, A070960, A201163, A319850, A318948, A318949, A319841, A319855.

ReplaceListRepeated[forms_,rerules_]:=Union[Flatten[FixedPointList[Function[pre,Union[Flatten[ReplaceList[#,rerules]&/@pre,1]]],forms],1]];
nexos[ptn_]:=If[Length[ptn]==0,{0},Union@@Select[ReplaceListRepeated[{Sort[ptn]},{{foe___,x_,mie___,y_,afe___}:>Sort[Append[{foe,mie,afe},x+y]],{foe___,x_,mie___,y_,afe___}:>Sort[Append[{foe,mie,afe},x*y]]}],Length[#]==1&]];
Table[Max[nexos[If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]]],{n,100}]

A319841 Number of distinct positive integers that can be obtained by iteratively adding or multiplying together parts of the integer partition with Heinz number n until only one part remains.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Sep 29 2018

nonn

			60 is the Heinz number of (3,2,1,1) and
   5 = (3+2)*1*1
   6 = 3*2*1*1
   7 = 3+2+1+1
   8 = (3+1)*2*1
   9 = 3*(2+1)*1
  10 = (3+2)*(1+1)
  12 = (3+1)*(2+1)
so we have a(60) = 7. It is not possible to obtain 11 by adding or multiplying together the parts of (3,2,1,1).

Cf. A001055, A001970, A048249, A056239, A063834, A066739, A066815, A281113, A318948, A318949, A319855, A319856.

ReplaceListRepeated[forms_,rerules_]:=Union[Flatten[FixedPointList[Function[pre,Union[Flatten[ReplaceList[#,rerules]&/@pre,1]]],forms],1]];
Table[Length[Select[ReplaceListRepeated[{If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]},{{foe___,x_,mie___,y_,afe___}:>Sort[Append[{foe,mie,afe},x+y]],{foe___,x_,mie___,y_,afe___}:>Sort[Append[{foe,mie,afe},x*y]]}],Length[#]==1&]],{n,100}]

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

A357858 Number of integer partitions that can be obtained by iteratively adding and multiplying together parts of the integer partition with Heinz number n.

Original entry on oeis.org

1, 1, 1, 3, 1, 3, 1, 6, 2, 3, 1, 7, 1, 3, 3, 11, 1, 7, 1, 8, 3, 3, 1, 14, 3, 3, 4, 8, 1, 11, 1, 19, 3, 3, 3, 18, 1, 3, 3, 18, 1, 12, 1, 8, 8, 3, 1, 27, 3, 10, 3, 8, 1, 16, 3, 19, 3, 3, 1, 25, 1, 3, 8, 33, 3, 12, 1, 8, 3, 12, 1, 35, 1, 3, 11, 8, 3, 12, 1, 34, 9

Offset: 1

Gus Wiseman, Oct 17 2022

nonn

The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.

			The a(n) partitions for n = 1, 4, 8, 9, 12, 16, 20, 24:
  ()  (1)   (1)    (4)   (2)    (1)     (3)    (2)
      (2)   (2)    (22)  (3)    (2)     (4)    (3)
      (11)  (3)          (4)    (3)     (5)    (4)
            (11)         (21)   (4)     (6)    (5)
            (21)         (22)   (11)    (31)   (6)
            (111)        (31)   (21)    (32)   (21)
                         (211)  (22)    (41)   (22)
                                (31)    (311)  (31)
                                (111)          (32)
                                (211)          (41)
                                (1111)         (211)
                                               (221)
                                               (311)
                                               (2111)

The single-part partitions are counted by A319841, with an inverse A319913.
The minimum is A319855, maximum A319856.
A000041 counts integer partitions.
A001222 counts prime indices, distinct A001221.
A056239 adds up prime indices.
A066739 counts representations as a sum of products.
Cf. A000792, A001055, A001970, A005520, A048249, A063834, A066815, A318948, A319850, A319909, A319910.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
ReplaceListRepeated[forms_,rerules_]:=Union[Flatten[FixedPointList[Function[pre,Union[Flatten[ReplaceList[#,rerules]&/@pre,1]]],forms],1]];
Table[Length[ReplaceListRepeated[{primeMS[n]},{{foe___,x_,mie___,y_,afe___}:>Sort[Append[{foe,mie,afe},x+y]],{foe___,x_,mie___,y_,afe___}:>Sort[Append[{foe,mie,afe},x*y]]}]],{n,100}]

cp's OEIS Frontend

A066739 Number of representations of n as a sum of products of positive integers. 1 is not allowed as a factor, unless it is the only factor. Representations which differ only in the order of terms or factors are considered equivalent.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A318949 Number of ways to write n as an orderless product of orderless sums.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A066815 Number of partitions of n into sums of products.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A319850 Number of distinct positive integers that can be obtained, starting with the initial interval partition (1, ..., n), by iteratively adding or multiplying together parts until only one part remains.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A319909 Number of distinct positive integers that can be obtained by iteratively adding any two or multiplying any two non-1 parts of an integer partition until only one part remains, starting with 1^n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A319855 Minimum number that can be obtained by iteratively adding or multiplying together parts of the integer partition with Heinz number n until only one part remains.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A319856 Maximum number that can be obtained by iteratively adding or multiplying together parts of the integer partition with Heinz number n until only one part remains.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A319841 Number of distinct positive integers that can be obtained by iteratively adding or multiplying together parts of the integer partition with Heinz number n until only one part remains.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica