Timeline for Fibonacci sequence inversion
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 18, 2010 at 6:28 | history | edited | Charles Matthews | CC BY-SA 2.5 |
typo
|
| Sep 18, 2010 at 5:59 | history | edited | Charles Matthews | CC BY-SA 2.5 |
sieving
|
| Sep 18, 2010 at 0:14 | comment | added | dvitek | In particular the sequence is periodic with period at most $n^2-1$ modulo any integer $n \ge 1$ (the proof is elementary and nearly obvious). So to do CRT you just need a bunch of primes (or maybe prime powers?). Shouldn't be much bigger than $n^2$? | |
| Sep 17, 2010 at 18:58 | comment | added | Michael Lugo | If you wanted to compute this quickly, logs are hard to compute exactly. | |
| Sep 17, 2010 at 18:49 | comment | added | Qiaochu Yuan | You shouldn't need much precomputation. Just knowing the number of digits of the Fibonacci number in question, you can compute n to within a constant factor, and after that it shouldn't be hard to use modular considerations to pin the index down precisely (if you really, really want to avoid using logarithms for some reason). | |
| Sep 17, 2010 at 18:13 | history | edited | Charles Matthews | CC BY-SA 2.5 |
exemplify
|
| Sep 17, 2010 at 18:08 | history | answered | Charles Matthews | CC BY-SA 2.5 |