A050370 Number of ways to factor n into composite factors.

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

Author

Christian G. Bower, Nov 15 1999

Keywords

• nonn

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

• Alois P. Heinz, Table of n, a(n) for n = 1..10000
• N. J. A. Sloane, Transforms

Crossrefs

Cf. A001055, A002808, A050371, A050372, A050373, A050374, A050375.

a(p^k)=A002865. a(A002110)=A000296.

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

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

Formula

Dirichlet g.f.: Product_{n is composite}(1/(1-1/n^s)).

Moebius transform of A001055. - Vladeta Jovovic, Mar 17 2004