A065026 -id:A065026 - 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

A067027 Numbers n such that (prime(n)# + 4)/2 is a prime, where x# is the primorial A034386(x).

Original entry on oeis.org

1, 2, 3, 4, 6, 10, 11, 12, 15, 17, 29, 48, 63, 77, 88, 187, 190, 338, 1133, 1311, 1832, 2782, 2907, 3180, 3272, 5398, 17530

Offset: 1

Labos Elemer, Dec 29 2001

nonn

Numbers n such that [A002110(n)/2]+2 is prime.
These primes are products of consecutive odd primes plus 2: 2+[3.5.7.....p(n)] if n is here.
a(19)-a(22) are Fermat and Lucas PRPs. (prime(2782)# + 4)/2 has 10865 digits. PFGW Version 1.2.0 for Windows [FFT v23.8] Primality testing (p(2782)#+4)/2 [N-1/N+1, Brillhart-Lehmer-Selfridge] Running N-1 test using base 5 Running N+1 test using discriminant 13, base 1+sqrt(13) (p(2782)#+4)/2 is Fermat and Lucas PRP! - Jason Earls, Dec 12 2006
a(28) > 25000. - Robert Price, Sep 29 2017

Cf. A002110, A067024, A065026.

p = 1; Do[p = p*Prime[n]; If[PrimeQ[(p + 4)/2], Print[n]], {n, 1, 400} ]
Flatten[Position[FoldList[Times,Prime[Range[3000]]],?(PrimeQ[ (#+4)/2]&)]] (* _Harvey P. Dale, May 24 2015 *)

n=0;pr=1/2;forprime(p=2,1e4,n++;pr*=p;if(ispseudoprime(pr+2),print1(n", "))) \\ Charles R Greathouse IV, Jul 25 2011

More terms from Robert G. Wilson v, Dec 30 2001
a(19)-a(22) from Jason Earls, Dec 12 2006
a(23) from Ray Chandler, Jun 16 2013
a(24)-a(27) from Robert Price, Sep 29 2017

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

A318948 Number of ways to choose an integer partition of each factor in a factorization of n.

Original entry on oeis.org

1, 2, 3, 9, 7, 17, 15, 40, 39, 56, 56, 126, 101, 165, 197, 336, 297, 496, 490, 774, 837, 1114, 1255, 1948, 2007, 2638, 3127, 4123, 4565, 6201, 6842, 9131, 10311, 12904, 14988, 19516, 21637, 26995, 31488, 39250, 44583, 55418, 63261, 77683, 89935, 108068, 124754

Offset: 1

Gus Wiseman, Sep 05 2018

nonn

			The a(4) = 9 ways: (1+1)*(1+1), (1+1+1+1), (1+1)*(2), (2)*(1+1), (2+1+1), (2)*(2), (2+2), (3+1), (4).

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

facs[n_]:=If[n<=1,{{}},Join@@Table[(Prepend[#1,d]&)/@Select[facs[n/d],Min@@#1>=d&],{d,Rest[Divisors[n]]}]];
Table[Sum[Times@@PartitionsP/@fac,{fac,facs[n]}],{n,10}]

Dirichlet g.f.: Product_{n > 1} 1 / (1 - P(n) / n^s) where P = A000041. [clarified by Ilya Gutkovskiy, Oct 26 2019]

A126326 a(1) = 1; for n>1, a(n) = smallest number which is not a sum or product or power of any subset of the numbers a(1) to a(n-1).

Original entry on oeis.org

1, 2, 5, 9, 13, 31, 35, 92, 118, 280, 516, 752, 1618, 1968, 5090, 6594, 15620, 19556, 48364, 61552, 149028, 188140, 460272, 583376, 1419928, 1796208, 4382888, 5549640, 13524944, 17117360, 41741584, 52840864, 128817168, 163051888, 397550784, 503232512, 1226887072

Offset: 1

Jonathan Vos Post, Mar 11 2007

nonn

Analog of A065026, with powers.

			a(4) = 9 because the possible sums and products of a(1), a(2), a(3) are 1, 2, 5, 1+2, 1+5, 2+5, 1+2+5, 2*5, 2^2, 2^3, ..., 5^2, 5^3, ... = 1, 2, 4, 3, 4, 5, 6, 7, 8, 10, 16, 25, ... The smallest missing number is 9.

Cf. A065026.

A126326 := proc(amax) local a,n,sumset,prodset,j,powset,aprev,newsumset,newprodset ; a := [1,2] ; n := 3 ; sumset := {} ; prodset := {1} ; powset := {1} ; while n <= amax do aprev := op(-1,a) ; newsumset := sumset ; for j from 1 to nops(sumset) do if op(j,sumset)+aprev <= amax then newsumset := newsumset union { op(j,sumset)+aprev } ; fi ; od ; for j from 1 to nops(a)-1 do if op(j,a)+aprev <= amax then newsumset := newsumset union { op(j,a)+aprev } ; fi ; od ; sumset := newsumset ; newprodset := prodset ; for j from 1 to nops(prodset) do if op(j,prodset)*aprev <= amax then newprodset := newprodset union { op(j,prodset)*aprev } ; fi ; od ; for j from 1 to nops(a)-1 do if op(j,a)*aprev <= amax then newprodset := newprodset union { op(j,a)*aprev } ; fi ; od ; prodset := newprodset ; for j from 2 to floor(log(amax)/log(aprev)) do if aprev^j <= amax then powset := powset union { aprev^j } ; fi ; od ; while n in sumset or n in prodset or n in powset do n := n+1 ; od ; if n <= amax then a := [op(a),n] ; fi ; print(a) ; n := n+1 ; od ; RETURN(a) ; end: A126326(200000) ; # R. J. Mathar, Apr 03 2007

Conjectures from Colin Barker, Jun 21 2019: (Start)
G.f.: x*(1 - x)*(1 + 3*x + 6*x^2 + 11*x^3 + 10*x^4 + 15*x^5 + 6*x^6 + 4*x^7 + 10*x^8 + 166*x^10 + 52*x^11 + 236*x^12 - 236*x^13 - 210*x^14) / (1 - 2*x^2 - 4*x^4 + 2*x^6).
a(n) = 2*a(n-2) + 4*a(n-4) - 2*a(n-6) for n>16.
(End)

More terms from R. J. Mathar, Apr 03 2007
a(21)-a(22) from Nathaniel Johnston, Oct 02 2011
a(23)-a(28) from Charlie Neder, Jun 02 2019
a(29)-a(37) from Giovanni Resta, Jun 03 2019

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

A067027 Numbers n such that (prime(n)# + 4)/2 is a prime, where x# is the primorial A034386(x).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Extensions

A066815 Number of partitions of n into sums of products.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A318948 Number of ways to choose an integer partition of each factor in a factorization of n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A126326 a(1) = 1; for n>1, a(n) = smallest number which is not a sum or product or power of any subset of the numbers a(1) to a(n-1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

Extensions