A050372 Number of ways to factor n into distinct composite factors.

1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 2, 1, 1, 1, 1, 0, 1, 0, 2, 1, 1, 1, 2, 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, 2, 1, 1, 0, 1, 1, 1, 0, 4, 0, 1, 1, 1, 1, 1, 0, 3, 1, 1, 0, 3, 1, 1, 1, 2, 0, 3, 1, 1, 1, 1, 1, 4, 0, 1, 1, 2, 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

Crossrefs

Cf. A002808, A045778, A050370-A050375. a(p^k)=A025147. a(A002110)=A000296.

Programs

Maple

with(numtheory):
b:= proc(n, k) option remember;
     `if`(isprime(n), 0, `if`(n>k, 0, 1)+
      add(`if`(d>k or isprime(d), 0, b(n/d, d-1))
          , d=divisors(n) minus {1, n}))
    end:
a:= n-> b(n$2):
seq(a(n), n=1..120);  # Alois P. Heinz, May 26 2013

Mathematica

b[n_, k_] := b[n, k] = If[PrimeQ[n], 0, If[n>k, 0, 1] + Sum[If[d>k || PrimeQ[d], 0, b[n/d, d-1]], {d, Divisors[n] ~Complement~ {1, n}}]];
a[n_] := b[n, n];
Array[a, 120] (* Jean-François Alcover, Mar 21 2017, after Alois P. Heinz *)

Formula

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