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,24

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

Formula

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

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

Crossrefs

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

Sequence in context: A258940 A340607 A319659 * A037802 A037879 A178535

Adjacent sequences: A050369 A050370 A050371 * A050373 A050374 A050375

Keyword

nonn

Author

Christian G. Bower, Nov 15 1999

Status

approved