login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 42
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..10000

N. J. A. Sloane, Transforms

FORMULA

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

EXAMPLE

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

MAPLE

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

MATHEMATICA

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

PROG

(Python)

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 xrange(1, n + 1)])/n

print map(a, xrange(61)) # Indranil Ghosh, Aug 19 2017, after Maple code

CROSSREFS

Cf. A000041, A001055.

Cf. A066815, A066816, A066806.

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

Sequence in context: A182269 A321360 A321566 * A066815 A106182 A097097

Adjacent sequences:  A066736 A066737 A066738 * A066740 A066741 A066742

KEYWORD

easy,nonn

AUTHOR

Naohiro Nomoto, Jan 16 2002

EXTENSIONS

Edited by Dean Hickerson, Jan 19 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 17 08:39 EST 2019. Contains 329217 sequences. (Running on oeis4.)