login
A050370
Number of ways to factor n into composite factors.
16
1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 2, 0, 1, 0, 1, 1, 1, 0, 2, 1, 1, 1, 1, 0, 1, 0, 2, 1, 1, 1, 3, 0, 1, 1, 2, 0, 1, 0, 1, 1, 1, 0, 3, 1, 1, 1, 1, 0, 2, 1, 2, 1, 1, 0, 3, 0, 1, 1, 4, 1, 1, 0, 1, 1, 1, 0, 4, 0, 1, 1, 1, 1, 1, 0, 3, 2, 1, 0, 3, 1, 1, 1, 2, 0, 3, 1, 1, 1, 1, 1, 5, 0, 1, 1, 3, 0, 1
OFFSET
1,16
COMMENTS
a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24 = 2^3*3 and 375 = 3*5^3 both have prime signature (3,1).
LINKS
N. J. A. Sloane, Transforms
FORMULA
Dirichlet g.f.: Product_{n is composite}(1/(1-1/n^s)).
Moebius transform of A001055. - Vladeta Jovovic, Mar 17 2004
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:
a:= proc(n) a(n):= add(mobius(n/d)*g(d$2), d=divisors(n)) end:
seq(a(n), n=1..100); # Alois P. Heinz, May 16 2014
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}}]]; a[n_] := Sum[ MoebiusMu[n/d]*g[d, d], {d, Divisors[n]}]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Jan 23 2017, after Alois P. Heinz *)
PROG
(Python)
from sympy.core.cache import cacheit
from sympy import mobius, divisors, isprime
@cacheit
def g(n, k): return (0 if n>k else 1) + (0 if isprime(n) else sum((0 if d>k else g(n//d, d)) for d in divisors(n)[1:-1]))
def a(n): return sum(mobius(n//d)*g(d, d) for d in divisors(n))
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Aug 19 2017, after Maple code
KEYWORD
nonn
AUTHOR
Christian G. Bower, Nov 15 1999
STATUS
approved