2
$\begingroup$

What is the maximum number that can be used with the following command in mathematica?

Length[IntegerDigits[x!]]

where 'x' is replaced by some finite integer for which the above command reaches its max number.

Then, what is this number?

$\endgroup$
  • $\begingroup$ Depends upon the amount of memory your system has. $\endgroup$ – Andrew Aug 18 '17 at 12:13
  • $\begingroup$ @Andrew what is the dependence? i.e assume I have 'y' GB memory, then how would you answer my question? If there's an official answer even better. $\endgroup$ – Alan Aug 18 '17 at 12:16
  • $\begingroup$ Now you want a function :) I doubt there is an official one. $\endgroup$ – Andrew Aug 18 '17 at 12:20
  • 1
    $\begingroup$ Look, people are in general sceptic if such a question is asked without any effort from yourself. Don't you have an educated guess what happens if x grows larger and larger? When will x! be so large that it fills your RAM? Can you estimate the how many digits it will have without calling IntegerDigits? Would theoretically Length have any problems giving you the number? These are easy questions you can answer yourself when you think about how a number is represented in memory. $\endgroup$ – halirutan Aug 18 '17 at 12:34
  • $\begingroup$ @Andrew so how can I know what is the maximum number, surely I can compute it; why do you think there's not an official one? $\endgroup$ – Alan Aug 18 '17 at 12:35
8
$\begingroup$

Crude estimates of memory limitations in Length[IntegerDigits[n!]].

This is a game we can poke at empirically and draw lines that should hold up to some systematic breakdown invisible from low memory scales. Best to work from the inside out as long as the memory constraints are dominated by outer layers. This is reasonable as IntegerDigits will dominate n!.

I'll assume linear dependence but will fit with higher polynomial to verify small weights of higher orders.


facPlot = ListPlot[facData = Table[{x, ByteCount[x!]}, {x, 1, 10000}]]

facSol = FindFit[facData, facFunc = a + b x + c x^2, {a, b, c, d, e}, 
  x]

{a -> -227.075, b -> 1.37349, c -> 0.000020072, d -> 0., e -> 0.}


Show[Plot[{0, facFunc /. facSol}, {x, 1, 10000}], facPlot]

facFitPlot

From the $b$ parameter let's say 1.5 bytes for every $n$ to store $n!$. So if you have 15GB, can estimate $n_{\rm max}(15GB)\sim 10^{10}$.


OK, what about integer digits.

idPlot = ListPlot[
  idData = Table[{x, ByteCount[IntegerDigits[x!]]}, {x, 1, 1000}]]

idSol = FindFit[idData, 
  idFunc = a  + b x   + c x^2 + d x^3 + e x^4 + f x^5, {a, b, c, d, e,
    f}, x]

{a -> 151.424, b -> 6.97385, c -> 0.0667293, d -> -0.000152748, e -> 1.66995*10^-7, f -> -6.67819*10^-11}

Show[Plot[{0, idFunc /. idSol}, {x, 1, 1000}], idPlot]

idFitPlot

So let's say 8 bytes per IntegerDigits[n!], so if you had 16GB, $n_{\rm max}\sim 2\times 10^9$ .

Let's look at Length firmly believing that it offers no resource constraints relative to the other expenses.

lPlot = ListPlot[
  lData = Table[{x, ByteCount[Length[IntegerDigits[x!]]]}, {x, 1, 
     5000}]]

length plot

We see this isn't going to be the factor, it'll be the integerdigits that's expensive and the memory bound.


Update: I decided to use some sleepy cycles on a large memory machine to verify / see where this breaks down. So far ByteCount measurements remains the same, but I noticed top was fluctuating a fair bit higher.

Wrapping ByteCount with MaxMemoryUsed seems to be giving a more top-related factor (still more or less linear)

  • $\sim n\times (16 + 0.0154 \ln(n)^2) $ bytes for MaxMemoryUsed[ByteCount[n!]] through $n\sim 6\times 10^9$ . Data will be hosted and updated here if you want to play with it.

loglog Bytes Nfac vs N loglin Bytes/n Nfac vs N

  • $\sim n \times 30$ bytes for MaxMemoryUsed[ByteCount[IntegerDigits[n!]]]
| improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.