2
$\begingroup$

I am trying to find the maximum value of $x$ such that $x! \leq 1000$. I tried the following:

NSolve[Factorial[x] - 1000 == 0, x]

but I got this message:

During evaluation of In[67]:= NSolve::ifun: Inverse functions are being used by NSolve, so some solutions may not be found; use Reduce for complete solution information. >>

Out[67]= {{x -> -2.001}}

What is the correct function to use here?

$\endgroup$
  • $\begingroup$ Factorial grows fast enough to do this by hand... the answer is 6! = 720. $\endgroup$ – zeldredge Apr 9 '15 at 15:50
  • $\begingroup$ @zeldredge, Yes but I other have much larger numbers to go through so I want a programmatic solution. $\endgroup$ – user27494 Apr 9 '15 at 15:52
  • $\begingroup$ You can easily do it procedurally using While. $\endgroup$ – Marius Ladegård Meyer Apr 9 '15 at 16:05
6
$\begingroup$

Use Maximize with a constraint:

Maximize[{x!, x! <= 1000}, x, Integers]

{720, {x -> 6}}

Or ArgMax for the value of x alone:

ArgMax[{x!, x! <= 1000}, x, Integers]

6

$\endgroup$
  • $\begingroup$ This doesn't seem to work with: Maximize[{Log2[x], Log2[x] <= 1000}, x, Integers] $\endgroup$ – user27494 Apr 9 '15 at 16:24
  • $\begingroup$ @I.K. Actually, it does work. It provides a symbolic result. It's providing you an exact integer assignment for x (or at least it does for me on v10.1). If you want a numerical approximation of the resulting for the maximized value, you should use FullSimplify (for value of 1000) or N, or similar. $\endgroup$ – kirma Apr 9 '15 at 16:28
  • $\begingroup$ @I.K. So, for simplification, see Maximize[{Log2[x], Log2[x] <= 1000}, x, Integers] // FullSimplify. $\endgroup$ – kirma Apr 9 '15 at 16:32
  • $\begingroup$ So I used this syntax to express the answer more manageably : N[Maximize[{Log2[x], Log2[x] <= 1000}, x, Integers], 5]. Is that the idiomatic way to do that in Mathematica. Also can you tell me why the output $\{1000.0, \{x -> 1.0715*10^301\}\}$ has 1000.0 in it? $\endgroup$ – user27494 Apr 9 '15 at 17:56
  • $\begingroup$ @I.K. Log2 is a bit special case because x is 2^1000 and Log2 of it is precisely 1000. In this case value of maximization is also known, but since simplification in general is non-trivial, not much simplification is done by default. To force more (in this case enough) FullSimplify produces precise answer. Your expression with N[..., 5] requests precisely five digits of precision; so that's what (1000.0) you get. $\endgroup$ – kirma Apr 9 '15 at 18:20
1
$\begingroup$
n = 1;
While[n! < 1000, Null; n++];
n - 1

(* 6 *)

Speedups for large n

If you seek the solutions to very large $n$ problems, it is faster if you use Stirling's approximation, that is:

$n! \approx \sqrt{2 \pi n} \left({ n \over e} \right)^n$.

Start at a safe lower limit (e.g., Log[Target]), then iteratively search through increasing $n$ (which is much faster and lower space complexity than calculating factorials). Once you get an estimate of $n$ based on the Stirling approximation, re-start a true factorial search starting at a safe lower limit, say $1/10$ the approximation result.

There are cleverer methods based on number theory, but I sense you don't need such sophistication here.

The Maximize[{x!, x! <= Target}, x, Integers] from @Kirma works quite well to large Target.

$\endgroup$
  • 6
    $\begingroup$ One can also use relation of Factorial and Gamma functions for something like: Floor[InverseFunction[Gamma][10^100] - 1] (* 69 *) $\endgroup$ – kirma Apr 9 '15 at 16:38
  • $\begingroup$ @kirma Ah... that solution is the best, InverseFunction---Mathematica style. +1 $\endgroup$ – David G. Stork Apr 9 '15 at 16:39
  • $\begingroup$ Also, you can do things like Floor[InverseFunction[LogGamma][Log[10] (10^7)] - 1] (* 1723507 *) for numbers up to at least 10^(10^7), like in this case. $\endgroup$ – kirma Apr 9 '15 at 16:49
1
$\begingroup$

This will give the <= factorial result result pretty quickly:

invfactorialbound[n_] :=
 Module[{bound = Ceiling[1 + Log[0.3989 (0.03653 + n)]/
                 ProductLog[0.3678 Log[0.3989 (0.03653 + n)]]]},
  While[bound! > n, bound--]; bound];

k=10000!+1*^10
invfactorialbound[k] // Timing

(* {0.031200,10000} *)

That's on an old netbook. No idea how long ArgMax et. al. would take - they bomb out unevaluated, but on smaller k (~5000!) this was below timer resolution, ArgMax took 7 seconds...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy