A035310 Let f(n) = number of ways to factor n = A001055(n); a(n) = sum of f(k) over all terms k in A025487 that have n factors.
1, 4, 12, 47, 170, 750, 3255, 16010, 81199, 448156, 2579626, 15913058, 102488024, 698976419, 4976098729, 37195337408, 289517846210, 2352125666883, 19841666995265, 173888579505200, 1577888354510786, 14820132616197925, 143746389756336173, 1438846957477988926
Offset: 1
Examples
a(3) = 12 because there are 3 terms in A025487 with 3 factors, namely 8, 12, 30; and f(8)=3, f(12)=4, f(30)=5 and 3+4+5 = 12.
From _Gus Wiseman_, Dec 31 2019: (Start)
The a(1) = 1 through a(3) = 12 multiset partitions of strongly normal multisets:
{{1}} {{1,1}} {{1,1,1}}
{{1,2}} {{1,1,2}}
{{1},{1}} {{1,2,3}}
{{1},{2}} {{1},{1,1}}
{{1},{1,2}}
{{1},{2,3}}
{{2},{1,1}}
{{2},{1,3}}
{{3},{1,2}}
{{1},{1},{1}}
{{1},{1},{2}}
{{1},{2},{3}}
(End)
Links
- Andrew Howroyd, Table of n, a(n) for n = 1..50
Crossrefs
Sequence A035341 counts the ordered cases. Tables A093936 and A095705 distribute the values; e.g. 81199 = 30 + 536 + 3036 + 6181 + 10726 + 11913 + 14548 + 13082 + 21147.
Row sums of A317449.
The uniform case is A317584.
The case with empty intersection is A317755.
The strict case is A317775.
The constant case is A047968.
The set-system case is A318402.
The case of strict parts is A330783.
Multiset partitions of integer partitions are A001970.
Unlabeled multiset partitions are A007716.
Programs
-
Maple
with(numtheory): g:= proc(n, k) option remember; `if`(n>k, 0, 1) +`if`(isprime(n), 0, add(`if`(d>k, 0, g(n/d, d)), d=divisors(n) minus {1, n})) end: b:= proc(n, i, l) `if`(n=0, g(mul(ithprime(t)^l[t], t=1..nops(l))$2), `if`(i<1, 0, add(b(n-i*j, i-1, [l[], i$j]), j=0..n/i))) end: a:= n-> b(n$2, []): seq(a(n), n=1..10); # Alois P. Heinz, May 26 2013 -
Mathematica
g[n_, k_] := g[n, k] = If[n > k, 0, 1] + If[PrimeQ[n], 0, Sum[If[d > k, 0, g[n/d, d]], {d, Divisors[n] ~Complement~ {1, n}}]]; b[n_, i_, l_] := If[n == 0, g[p = Product[Prime[t]^l[[t]], {t, 1, Length[l]}], p], If[i < 1, 0, Sum[b[n - i*j, i-1, Join[l, Array[i&, j]]], {j, 0, n/i}]]]; a[n_] := b[n, n, {}]; Table[Print[an = a[n]]; an, {n, 1, 13}] (* Jean-François Alcover, Dec 12 2013, after Alois P. Heinz *) -
PARI
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)} D(p, n)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); my(u=EulerT(v)); Vec(1/prod(k=1, n, 1 - u[k]*x^k + O(x*x^n))-1, -n)/prod(i=1, #v, i^v[i]*v[i]!)} seq(n)={my(s=0); forpart(p=n, s+=D(p,n)); s} \\ Andrew Howroyd, Dec 30 2020 -
Python
from sympy.core.cache import cacheit from sympy import divisors, isprime, prime from operator import mul @cacheit def g(n, k): return (0 if n > k else 1) + (0 if isprime(n) else sum(g(n//d, d) for d in divisors(n)[1:-1] if d <= k)) @cacheit def b(n, i, l): if n==0: p = reduce(mul, (prime(t + 1)**l[t] for t in range(len(l)))) return g(p, p) else: return 0 if i<1 else sum([b(n - i*j, i - 1, l + [i]*j) for j in range(n//i + 1)]) def a(n): return b(n, n, []) for n in range(1, 11): print(a(n)) # Indranil Ghosh, Aug 19 2017, after Maple code
Extensions
More terms from Erich Friedman.
81199 from Alford Arnold, Mar 04 2008
a(10) from Alford Arnold, Mar 31 2008
a(10) corrected by Alford Arnold, Aug 07 2008
a(11)-a(13) from Alois P. Heinz, May 26 2013
a(14) from Alois P. Heinz, Sep 27 2014
a(15) from Alois P. Heinz, Jan 10 2015
Terms a(16) and beyond from Andrew Howroyd, Dec 30 2020
Comments