Timeline for Closed formula for the factorial over naturals
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| 9 mins ago | comment | added | Emil Jeřábek | @domotorp Since you posted the version for $\mathbb R$ as a separate question, are you going to change this question so that it explicitly allows integer division? Right now you have basically two identical question except that one is written more clearly. | |
| 18 mins ago | comment | added | Anixx | @EmilJeřábek if it is not an elementary function, then it cannot be expressed even with logarithm. So without logarithm it cannot be expressed as well. | |
| 22 mins ago | comment | added | Emil Jeřábek | But the question is over the reals, not complex numbers. Also, the question does not allow logarithm. | |
| 28 mins ago | comment | added | Anixx | @EmilJeřábek of course, over the complex numbers. | |
| 29 mins ago | comment | added | Emil Jeřábek | @Anixx For example, en.wikipedia.org/wiki/Elementary_function also lists trigonometric functions and their inverses, which are not definable from field operations, exp, and log over the reals. | |
| 31 mins ago | comment | added | Anixx | @EmilJeřábek I think, elementary function is quite estrablished concept (a function that can be constructed using the field operations, exponentiation and logarithm). | |
| 33 mins ago | comment | added | Emil Jeřábek | @Anixx That just begs the question “what is an elementary function”, hence all the ambiguity. | |
| 35 mins ago | comment | added | Anixx | @domotorp your question can be formulated in shorter way: a proof that factorial is not an elementary function. | |
| 39 mins ago | vote | accept | domotorp | ||
| 39 mins ago | comment | added | domotorp | The ambiguity comes from the fact that when I originally posted the question, I explicitly wrote that only the four basic operations plus exponentials were allowed, having the reals in mind, but later it was edited by Martin Brandenburg, who rewrote the question to clarify it and added that it was about $\mathbb N \to \mathbb N$ functions. As I also didn't know the answer for this problem and I was late to notice the change, I thought I would leave it like that. I'll post a separate question about $\mathbb R\to \mathbb R$ functions. | |
| 43 mins ago | vote | accept | domotorp | ||
| 39 mins ago | |||||
| 43 mins ago | comment | added | David E Speyer | The idea is that the Euclidean algorithm to compute $\text{GCD}(M, N)$ runs in time $O(\min(\log M, \log N))$ in this model, and you can compute $k!$ in time polynomial in $\log k$ using the formulas in this answer, so you can do a binary search to find $k$ with $1< \text{GCD}(N, k!) <N$. | |
| 45 mins ago | comment | added | David E Speyer | There is a fun exercise in Knuth's Art of Computer Programming: Suppose you have a computer which can compute any arithmetic operation in time $O(1)$, no matter how large the inputs are. Show that it can factor $N$ in time polynomial in $\log N$. | |
| 54 mins ago | comment | added | Emil Jeřábek | The answer explicitly points out that this restriction was only added while I was finishing the answer. | |
| 1 hour ago | comment | added | Peter Mueller | The question explicitly forbids the floor (and ceiling) function. | |
| 1 hour ago | history | edited | Emil Jeřábek | CC BY-SA 4.0 |
added 91 characters in body
|
| 2 hours ago | history | edited | Emil Jeřábek | CC BY-SA 4.0 |
added 166 characters in body
|
| 4 hours ago | history | edited | Emil Jeřábek | CC BY-SA 4.0 |
added 53 characters in body
|
| 4 hours ago | history | answered | Emil Jeřábek | CC BY-SA 4.0 |