<p>Suresh's answer probably answers the question for you, but I thought I would point out a special case. You can always work out the result for the less significant digits for any base. Take $p$ as our base. </p>

<p>Clearly, every p<sup>th</sup> term in the factorial is a multiple of $p$. Every $(p^2)$<sup>th</sup> term is a multiple of $p^2$, etc. Thus the highest power of $p$ that is a factor of $N!$ is $X_p = \sum_{i=1}^{\lfloor \log_p(N!) \rfloor} \lfloor \frac{N}{p^i}\rfloor$. $\log_p(N!)$ is easy to approximate by Stirlings approximation: $\ln N! \approx N \ln N - N$. Further, $p^{N \lceil \log_p (N) \rceil} > N!$, so the sum can always be computed efficiently by summing instead for $1 \leq i \leq {N \lceil \log_p (N) \rceil}$ (since $\lfloor \frac{N}{p^i}\rfloor = 0$ for $i > {\lfloor \log_p(N!) \rfloor}$).</p>

<p>Thus the last $X_p$ digits of $N!$ are zero in base $p$.</p>

CC BY-SA 2.5
2010-10-15T12:42:10.963Z
2010-10-15T12:42:10.963Z
Joe Fitzsimons
<p>Dick Lipton has a <a href="http://rjlipton.wordpress.com/2009/02/23/factoring-and-factorials/" rel="nofollow">beautiful post from 2009</a> on the relationship between the factorial function and factoring. There's a lot there that is unrelated to this question, but one salient point is this theorem:</p>

<blockquote>
  <p>If $n!$ can be computed by a
  straight-line arithmetic computation
  in $O(\log^{c} n)$ steps, then
  factoring has polynomial size
  circuits.</p>
</blockquote>

<p>I suspect that this is evidence that your question, especially within the time bounds you mention, is going to be difficult to answer. </p>

CC BY-SA 2.5
2010-10-15T14:59:31.617Z
Thank you, this is exactly the type of answer I was looking for.  This doesn't directly answer my question and I don't see exactly how to connect the two, but it's close enough to put my mind at rest.
user834
CC BY-SA 2.5
2010-10-15T05:43:53.110Z
2010-10-15T05:43:53.110Z
Suresh Venkat
<p>Given $N$ and $M$, is it possible to get the $M$'th bit (or digit of any small base) of $N!$ in time/space of $O( p( ln(N), ln(M) ) )$, where $p(x, y)$ is some polynomial function in $x$ and $y$?</p>

<p>i.e. Given $N = 2^\eta$, $M = 2^\mu$ (with $N$, $M \in \mathbb{Z}$), find bit $2^\mu$ of $(2^\eta)!$ in $O( p(\eta, \mu) )$.</p>

<p>Note: I have asked this on mathoverflow.net <a href="https://mathoverflow.net/questions/42046/efficiently-getting-bits-of-n">here</a> and have not been getting any answers so I have cross-posted.</p>

<p>From the <a href="https://mathoverflow.net/questions/42046/efficiently-getting-bits-of-n/42081#42081">comment</a> on the other site, Gene Kopp points out that one can efficiently compute the lower order bits by doing modular arithmetic and higher order bits using Stirling's approximation, so this question is really 'how efficiently can one compute the middle order bits?'.</p>

<ds.algorithms><nt.number-theory>
Efficiently getting bits of N! ?
user834
# Efficiently getting bits of N! ?

(Asked by: username_0 on 2010-10-15)

Given $N$ and $M$, is it possible to get the $M$'th bit (or digit of any small base) of $N!$ in time/space of $O( p( ln(N), ln(M) ) )$, where $p(x, y)$ is some polynomial function in $x$ and $y$?

i.e. Given $N = 2^\eta$, $M = 2^\mu$ (with $N$, $M \in \mathbb{Z}$), find bit $2^\mu$ of $(2^\eta)!$ in $O( p(\eta, \mu) )$.

Note: I have asked this on mathoverflow.net [here](https://mathoverflow.net/questions/42046/efficiently-getting-bits-of-n) and have not been getting any answers so I have cross-posted.

From the [comment](https://mathoverflow.net/questions/42046/efficiently-getting-bits-of-n/42081#42081) on the other site, Gene Kopp points out that one can efficiently compute the lower order bits by doing modular arithmetic and higher order bits using Stirling's approximation, so this question is really 'how efficiently can one compute the middle order bits?'.

**Tags:** ds.algorithms, nt.number-theory


---

## 2 answers

### Answer by username_2 on 2010-10-15. Score: 13 | Accepted answer

Dick Lipton has a [beautiful post from 2009](http://rjlipton.wordpress.com/2009/02/23/factoring-and-factorials/) on the relationship between the factorial function and factoring. There's a lot there that is unrelated to this question, but one salient point is this theorem:

> If $n!$ can be computed by a
> straight-line arithmetic computation
> in $O(\log^{c} n)$ steps, then
> factoring has polynomial size
> circuits.

I suspect that this is evidence that your question, especially within the time bounds you mention, is going to be difficult to answer.

> **Comments:**
> **username_0**: Thank you, this is exactly the type of answer I was looking for.  This doesn't directly answer my question and I don't see exactly how to connect the two, but it's close enough to put my mind at rest.  

---

### Answer by username_1 on 2010-10-15. Score: 3

Suresh's answer probably answers the question for you, but I thought I would point out a special case. You can always work out the result for the less significant digits for any base. Take $p$ as our base.

Clearly, every pth term in the factorial is a multiple of $p$. Every $(p^2)$th term is a multiple of $p^2$, etc. Thus the highest power of $p$ that is a factor of $N!$ is $X\_p = \sum\_{i=1}^{\lfloor \log\_p(N!) \rfloor} \lfloor \frac{N}{p^i}\rfloor$. $\log\_p(N!)$ is easy to approximate by Stirlings approximation: $\ln N! \approx N \ln N - N$. Further, $p^{N \lceil \log\_p (N) \rceil} > N!$, so the sum can always be computed efficiently by summing instead for $1 \leq i \leq {N \lceil \log\_p (N) \rceil}$ (since $\lfloor \frac{N}{p^i}\rfloor = 0$ for $i > {\lfloor \log\_p(N!) \rfloor}$).

Thus the last $X\_p$ digits of $N!$ are zero in base $p$.


---

