OFFSET
0,3
COMMENTS
Also number of different LCM's of partitions of n.
a(n) <= A023893(n), which counts the nonisomorphic Abelian subgroups of S_n. - M. F. Hasler, May 24 2013
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
L. Elliott, A. Levine, and J. D. Mitchell, Counting monogenic monoids and inverse monoids, arXiv:2303.12387 [math.GR], 2023.
FORMULA
a(n) = Sum_{k=0..n} b(k), where b(k) is the number of partitions of k into distinct prime power parts (1 excluded) (A051613). - Vladeta Jovovic
G.f.: Product_{p prime} 1 + Sum(k >= 1, x^(p^k))) / (1-x). - David W. Wilson, Apr 19 2000
MAPLE
b:= proc(n, i) option remember; local p;
p:= `if`(i<1, 1, ithprime(i));
`if`(n=0 or i<1, 1, b(n, i-1)+
add(b(n-p^j, i-1), j=1..ilog[p](n)))
end:
a:= n-> b(n, numtheory[pi](n)):
seq(a(n), n=0..100); # Alois P. Heinz, Feb 15 2013
MATHEMATICA
Table[ Length[ Union[ Apply[ LCM, Partitions[ n ], 1 ] ] ], {n, 30} ]
f[n_] := Length@ Union[LCM @@@ IntegerPartitions@ n]; Array[f, 60, 0]
(* Caution, the following is Extremely Slow and Resource Intensive *) CoefficientList[ Series[ Expand[ Product[1 + Sum[x^(Prime@ i^k), {k, 4}], {i, 10}]/(1 - x)], {x, 0, 30}], x]
b[n_, i_] := b[n, i] = Module[{p}, p = If[i<1, 1, Prime[i]]; If[n == 0 || i<1, 1, b[n, i-1]+Sum[b[n-p^j, i-1], {j, 1, Log[p, n]}]]]; a[n_] := b[n, PrimePi[n]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 03 2014, after Alois P. Heinz *)
PROG
(PARI) /* compute David W. Wilson's g.f., needs <1 sec for 1000 terms */
N=1000; x='x+O('x^N); /* N terms */
gf=1; /* generating function */
{ forprime(p=2, N,
sm = 1; pp=p; /* sum; prime power */
while ( pp<N, sm += x^pp; pp *= p; );
gf *= sm; /* update g.f. */
); }
gf/=(1-x); /* cumulative sums */
Vec(gf) /* show terms */ /* Joerg Arndt, Jan 19 2011 */
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
STATUS
approved