A050372 - OEIS

%I #13 Mar 21 2017 05:55:10

%S 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,

%T 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,

%U 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

%N Number of ways to factor n into distinct composite factors.

%C 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).

%H Alois P. Heinz, <a href="/A050372/b050372.txt">Table of n, a(n) for n = 1..10000</a>

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

%p with(numtheory):

%p b:= proc(n, k) option remember;

%p      `if`(isprime(n), 0, `if`(n>k, 0, 1)+

%p       add(`if`(d>k or isprime(d), 0, b(n/d, d-1))

%p           , d=divisors(n) minus {1, n}))

%p     end:

%p a:= n-> b(n$2):

%p seq(a(n), n=1..120);  # _Alois P. Heinz_, May 26 2013

%t 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}}]];

%t a[n_] := b[n, n];

%t Array[a, 120] (* _Jean-François Alcover_, Mar 21 2017, after _Alois P. Heinz_ *)

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

%K nonn

%O 1,24

%A _Christian G. Bower_, Nov 15 1999