OFFSET
0,5
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics, Prime Power
FORMULA
a(n) = [x^n] Product_{p^k|n, p prime, k >= 1} 1/(1 - x^(p^k)).
a(n) = 1 if n is a prime.
a(n) = 2 if n is a semiprime.
EXAMPLE
a(8) = 4 because 8 has 4 divisors {1, 2, 4, 8} among which 3 are prime powers {2, 4, 8} therefore we have [8], [4, 4], [4, 2, 2] and [2, 2, 2, 2].
MAPLE
with(numtheory):
a:= proc(n) option remember; local b, l; l, b:= sort(
[select(x-> nops(ifactors(x)[2])=1, divisors(n))[]]),
proc(m, i) option remember; `if`(m=0, 1, `if`(i<1, 0,
b(m, i-1)+`if`(l[i]>m, 0, b(m-l[i], i))))
end; b(n, nops(l))
end:
seq(a(n), n=0..100); # Alois P. Heinz, Mar 30 2017
MATHEMATICA
Table[d = Divisors[n]; Coefficient[Series[Product[1/(1 - Boole[PrimePowerQ[d[[k]]]] x^d[[k]]), {k, Length[d]}], {x, 0, n}], x, n], {n, 0, 90}] (* or *)
a[0]=1; a[1]=0; a[n_] := Length@IntegerPartitions[n, All, Join @@ (#[[1]]^Range[#[[2]]] & /@ FactorInteger[n])]; a /@ Range[0, 90] (* Giovanni Resta, Mar 25 2017 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Ilya Gutkovskiy, Mar 24 2017
STATUS
approved