A034876 Number of ways to write n! as a product of smaller factorials each greater than 1.

0, 0, 0, 1, 0, 1, 0, 1, 1, 2, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset

1,10

Comments

By definition, a(n) > 0 if and only if n is a member of A034878. If n > 2, then a(n!) > max(a(n), a(n!-1)), as (n!)! = n!*(n!-1)!. Similarly, a(A001013(n)) > 0 for n > 2. Clearly a(n)=0 if n is a prime A000040. So a(n+1)=1 if n=2^p-1 is a Mersenne prime A000668, as (n+1)!=(2!)^p*n! and n is prime. - Jonathan Sondow, Dec 15 2004

From Antti Karttunen, Dec 25 2018: (Start)

If n! = a! * x! * y! * ... * z!, with a > x >= y >= z, then A006530(n!) = A006530(a!) > A006530(x!). This follows because all rows in A115627 end with 1, that is, because all factorials >= 2 are in A102750.

If all the two-term solutions are of the form n! = a! * x! = b! * y! = ... = c! * z! (that is, all are products of two factorials larger than one), with a > x, b > y, ..., c > z, then a(n) = (a(x)+1 + a(y)+1 + ... + a(z)+1).

Values 0..5 occur for the first time at n = 1, 4, 10, 576, 13824, 69120.

In range 1..69120 differs from A322583 only at positions n = 1, 2, 9, 10 and 16.

(End)

References

R. K. Guy, Unsolved Problems in Number Theory, B23.

Links

Antti Karttunen, Table of n, a(n) for n = 1..69120

Eric Weisstein's World of Mathematics, Factorial Products

Index entries for sequences related to factorial numbers

Formula

a(1) = 0; for n > 1, a(n) = Sum_{x=A007917(n)..n-1} A322583(n!/x!) when n is a composite, and a(n) = 0 when n is a prime. - Antti Karttunen, Dec 25 2018

Example

a(10) = 2 because 10! = 3! * 5! * 7! = 6! * 7! are the only two ways to write 10! as a product of smaller factorials > 1.
From Antti Karttunen, Dec 25 2018: (Start)
a(8) = 1 because 8! = 7! * (2!)^3.
a(9) = 1 because 9! = 7! * 3! * 3! * 2!.
a(16) = 2 because 16! = 15! * (2!)^4 = 14! * 5! * 2!.
a(144) = 2 because 144! = 143! * 4! * 3! = 143! * 3! * 3! * 2! * 2!.
a(576) = 3 because 576! = 575! * 4! * 4! = 575! * 4! * 3! * 2! * 2! = 575! * 3! * 3! * 2! * 2! * 2! * 2!.
a(720) = 2 because 720! = 719! * 6! = 719! * 5! * 3!.
a(3456) = 3 because 3456! = 3455! * 4! * 4! * 3! = 3455! * 4! * 3! * 3! * 2! * 2! = 3455! * 3! * 3! * 3! * 2! * 2! * 2! * 2!.
(End)

Prog

(PARI)
A034876aux(n, m, p) = if(1==n, 1, my(s=0); forstep(i=m, p, -1, my(f=i!); if(!(n%f), s += A034876aux(n/f, i, 2))); (s));
A034876(n) = if(1==n, 0, A034876aux(n!, n-1, precprime(n))); \\ (Slow) - Antti Karttunen, Dec 24 2018
(PARI)
A322583aux(n, m) = if(1==n, 1, my(s=0); for(i=2, oo, my(f=i!); if(f>m, return(s)); if(!(n%f), s += A322583aux(n/f, f))));
memoA322583 = Map();
A322583(n) = { my(c); if(mapisdefined(memoA322583, n, &c), c, c = A322583aux(n, n); mapput(memoA322583, n, c); (c)); };
A034876aux(n, m, p) = if(1==n, 1, my(s=0); forstep(i=m, p, -1, my(f=i!); s += A322583(n/f)); (s));
A034876(n) = if(1==n, 0, A034876aux(n!, n-1, precprime(n))); \\ Antti Karttunen, Dec 25 2018

Crossrefs

Cf. A034878, A001013, A075082, A085604, A115627, A322583.

Sequence in context: A219558 A279210 A232243 * A091393 A359735 A284557

Adjacent sequences: A034873 A034874 A034875 * A034877 A034878 A034879

Keyword

easy,nonn,nice

Author

Erich Friedman

Extensions

Corrected by Jonathan Sondow, Dec 18 2004

Status

approved