A076716 Number of distinct factorizations of n! with all factors > 1.

1, 1, 2, 7, 21, 98, 392, 2116, 11830, 70520, 425240, 2787810, 19530213, 144890639, 1149978830, 8558078111, 76417516719, 618437486332, 6087770992601, 54574732902278, 525656554130914, 5290117056157616, 61626071051832409, 555057889968635744, 5809502058957961682

Offset: 1

Author

Donald S. McDonald, Oct 27 2002

Keywords

• nonn

Examples

			a(3) = 2 because 3! = 6 = 2*3 has just 2 factorizations.
a(4) = 7 because 4! = 24 = 2*12 = 2*2*6 = 2*2*2*3 = 2*3*4 = 3*8 = 4*6 has 7 factorizations.
		

Crossrefs

Cf. A001055, A157612, A162247, A318284.

Programs

Maple

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

Mathematica

c[1, r_] := c[1, r]=1; c[n_, r_] := c[n, r]=Module[{ds, i}, ds=Select[Divisors[n], 1<#<=r&]; Sum[c[n/ds[[i]], ds[[i]]], {i, 1, Length[ds]}]]; a[n_] := c[n!, n! ]; a/@Range[16] (* c[n, r] is the number of factorizations of n with factors <= r. - Dean Hickerson, Oct 29 2002 *)

PARI

\\ See A318284 for count.
a(n)={if(n<=1, 1, count(factor(n!)[,2]))} \\ Andrew Howroyd, Feb 01 2020

Formula

a(n) = A001055(n!).

Extensions

Edited by Robert G. Wilson v, Oct 29 2002

4 more terms from Ryan Propper, May 20 2007

a(20)-a(25) from Andrew Howroyd, Feb 01 2020