A075082

[David Wasserman]

I have confirmed Robert G. Wilson v's extension of this sequence.   
I'm not sure that 10 and 16 are the only members of A075082 that  
aren't members of A058295, but I have proved that there are no such  
members between 60480 and 1209600.  The details are at the end of  
this message.

%I A075082
%S A075082  
1,6,10,12,16,24,48,120,144,240,288,720,1440,2880,4320,5040,5760,8640,
%T A075082 10080,17280,30240,34560,40320,60480
%N A075082 Numbers n such that n! is a product of distinct factorials  
k!*l!*m!*... with k, l, m etc. < n.
%C A075082 r! is a member for r>2, since (r!)! = (r!)*(r!-1)!.
%C A075082 Robert G. Wilson v (rgwv(AT)rgwv.com), Jun 18 2005,  
suggests that the sequence begins as follows:
%C A075082  
1,6,10,12,16,24,48,120,144,240,288,720,1440,2880,4320,5040,5760,8640,
%C A075082  
10080,17280,30240,34560,40320,60480,80640,86400,103680,120960,172800,
%C A075082  
207360,241920,362880,483840,518400,604800,725760,967680,1036800,1209600
%C A075082 Here are his arguments: r!s!t!... is a member for distinct  
r,s,t,... > 1. Except for 1, 10 & 16, all the mem\
   bers are of these forms. Except for 10 and 16, all terms n have  
(n-1)! as the greatest factorial in the product. For \
   n to be a member, the largest distinct factorial m! less than n!  
must not be less than the greatest prime less than n\
   . He then gave the Mma code below. This extension needs to be  
checked before it can be accepted. - njas, Jun 25 2005
%C A075082 Subsequence of A034878 (all n such that n! is a product of  
smaller factorials). It is conjectured that A0348\
   78 and A001013 (Jordan-Polya numbers = products of factorials) are  
the same sequence (except for the numbers 2, 9, an\
   d 10). If this is true, then obviously A075082 (without the number  
10) is also a subsequence of A001013. On the other\
    hand, this special case of the conjecture might be easier to  
prove. (a(n)!)^2 is a member of A058295 (products of di\
   stinct factorials); for example, (6!)^2 = 6!*5!*3!. - Jonathan  
Sondow (jsondow(AT)alumni.princeton.edu), Dec 21 2004
%C A075082 May be the same as A058295 except for 2, 10 and 16. - Jud  
McCranie (j.mccranie(AT)adelphia.net), Jun 13 2005
%D A075082 R. K. Guy, Unsolved Problems in Number Theory, B23.
%H A075082 <a href="http://www.research.att.com/~njas/sequences/ 
Sindx_Fa.html#factorial">Index entries for sequences re\
   lated to factorial numbers.</a>
%e A075082 1! = 0!, 6! = 5!*3!, 10! = 7!*6!, 12! = 11!*3!*2!, 16! =  
14!*5!*2!,
%e A075082 24! = 23!*4!, 48! = 47!*4!*2!, 120! = 119!*5!, 144! = 143! 
*4!*3!,
%e A075082 240! = 239!*5!*2!, 288! = 287!*4!*3!*2!, 720! = 719!*6!,  
1440! = 1439!6!*2!, etc.
%t A075082 (* first do *) Needs["DiscreteMath`Combinatorica`"] (*  
then *) s = Sort[ Table[ Times @@ Factorial /@ Unrank\
   Subset[n, Table[i, {i, 2, 12}]], {n, 2047}]]; f[n_] := Block[{k =  
Prime[ PrimePi[n]]}, While[k < n && Position[s, Pro\
   duct[i, {i, k + 1, n}]] == {}, k++ ]; If[k == n, 0, k]]; Do[a = f 
[n]; If[a != 0, Print[{n, a}]], {n, 3, 1210000}] (fr\
   om Robert G. Wilson v (rgwv(AT)rgwv.com), Jun 20 2005)
%Y A075082 Cf. A034878, A001013, A058295.
%Y A075082 Sequence in context: A108315 A081390 A063214 this_sequence  
A101503 A102148 A107407
%Y A075082 Adjacent sequences: A075079 A075080 A075081 this_sequence  
A075083 A075084 A075085
%K A075082 nonn
%O A075082 1,2
%A A075082 Amarnath Murthy (amarnath_murthy(AT)yahoo.com), Sep 11 2002
%E A075082 Corrected and extended by Jud McCranie (JudMcCr(AT) 
BellSouth.net), Sep 13 2002
%E A075082 More terms from Jud McCranie (j.mccranie(AT)adelphia.net),  
Jun 13 2005
_______________________________________________________

Let ff(n, k) = n!/(n - k)! ("falling factorial").  Let nl = 60480 and  
nh = 1209600.

Theorem: For nl <= n <= nh and 2 <= k <= 114, ff(n, k) is not a  
product of distinct factorials.
(Note: I chose the limit 114 because it is the largest gap between  
primes < nh.)

	The key observation is that if n >> k, then ff(n, k) will usually  
have prime factors in ratios that are typical of numbers on the order  
of n.  In contrast, factorials have a lot of small prime factors.  My  
proof is mostly based on counting powers of 2.

	We need a bunch of notation:
Define ord(p, m) to be the greatest i such that p^i | m.
Define r2(m) = ord(2, m)/log(m).  (r is short for "richness".)
Observe that if c1 <= r2(x_i) <= c2 for 1 <= i <= s, then c1 <= r2 
(prod_{i = 1..s} x_i) <= c2.
Let mrf(m) = min {r2(i!) | i <= m}.  (mrf is short for "minimum  
richness of factorials".)

Let g(m) be the least number such that g(m)! >= m.
Let q(m) be min {ord(2, x) | x >= m is a product of factorials}.

Claim: For any m, q(m) >= log(m)*mrf(g(m)).
Proof: Let this minimum be yielded by x = a_1!*a_2!*...*a_s!, a_1 <=  
a_2 <= ... <= a_s.  If there is more than one x that yields the same  
minimum ord(2, x), we choose the smallest such x.  Then a_s <= g(m),  
because otherwise replacing a_s with g(m) would produce a smaller x  
 >= m without increasing ord(2, x).  Then r2(x)  >= min_{i = 1..s} r2 
(a_i!) >= mrf(g(m)).  q(m) = ord(2, x) = r2(x)*log(x) >= r2(x)*log(m)  
 >= log(m)*mrf(g(m)).

Let so2(m) = sum_{i = 1..m} ord(2, i).  If x is the product of k  
consecutive numbers, and ord(2, x) = c, then one of these k numbers  
is divisible by 2^(c - so2(k - 1)).

Proof of theorem:
	Case 1: 2 <= k <= 12: This is done by computation.  I found all  
products of distinct factorials <= ff(nh, k), and then checked that  
none of them could be factored into k consecutive numbers.
	For the rest of the cases, let x = ff(n, k) and suppose x is a  
product of factorials.  (We no longer need the "distinct" hypothesis.)
	Case 2: 13 <= k <= 28: Let m = ff(nl, 13) > 1.44e62.  g(m) = 49; mrf 
(49) > 0.307.  x >= m, so ord(2, x) >= q(m) >= log(m)*mrf(g(m)) >  
0.307*log(1.44e62) > 43.9.  So one of the numbers between n and n - k  
is divisible by 2^(44 - so2(27)) = 2^21 > nh, contradicting n <= nh.
	Case 3: 29 <= k <= 68: Let m = ff(nl, 29) > 4.61e138.  g(m) = 91; mrf 
(91) > 0.266.  So ord(2, x) > 0.266*log(4.61e138) > 84.9.  So one of  
the numbers between n and n - k is divisible by 2^(85 - so2(67)) =  
2^21 > nh, a contradiction.
	Case 4: 69 <= k <= 114: Let m = ff(nl, 69) > 8.21e329.  g(m) = 181;  
mrf(181) > 0.23.  So ord(2, x) > 0.23*log(8.21e329) > 174.7.  So one  
of the numbers between n and n - k is divisible by 2^(175 - so2(114))  
= 2^65 > nh, a contradiction.