Timeline for Efficiently getting bits of N! ?
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Apr 5, 2011 at 7:29 | history | edited | dorkusmonkey | CC BY-SA 2.5 |
gave crosspost (to cstheory) link and link to relevant website in the answer there.
|
| Oct 16, 2010 at 20:41 | answer | added | Quadrescence | timeline score: 0 | |
| Oct 16, 2010 at 20:00 | answer | added | Kristoffer Arnsfelt Hansen | timeline score: 0 | |
| Oct 13, 2010 at 23:10 | answer | added | Gene S. Kopp | timeline score: 1 | |
| Oct 13, 2010 at 21:00 | comment | added | dorkusmonkey | @ohai: This site gets more traffic. If I don't get an answer in a reasonable amount of time I will cross post. | |
| Oct 13, 2010 at 20:34 | comment | added | ohai | there is also a theoretical computer science stackexchange | |
| Oct 13, 2010 at 19:43 | comment | added | Willie Wong | Some trivial observations: $\eta$ and $\mu$ should be related. If $\eta > 2^\mu$ (roughly, I may be missing a constant factor), then $N!$ has bit $M$ precisely 0. If $\mu > \eta 2^\eta$ then the bit is also 0. But the relationship doesn't seem to simplify the quesiton. | |
| Oct 13, 2010 at 19:28 | comment | added | AVS | This doesn't answer your question, which I believe assumes that the base n is fixed, i.e. n=O(1), but I note that if n is allowed to grow with N, say log n ~ c log N for some small constant c > 0, then the answer to your question is almost certainly no, since a positive answer would give a polynomial-time algorithm to factor n (even just using M=0). | |
| Oct 13, 2010 at 18:49 | history | asked | dorkusmonkey | CC BY-SA 2.5 |