I recently stumbled across this SPOJ question:
http://www.spoj.com/problems/PISANO/ The question is simple. Calculate the Pisano period of a number. After I researched my way through the web, I found that a number's Pisano period can be calculated in terms of its prime factors. For prime numbers we have another method which uses Binet's formula. Is there any alternative for solving this problem?
Best Answer
It depends on what you mean by "calculate".
If you want a "closed-form" expression for $k(m)$, the period of the Fibonacci sequence modulo $m$: One should expect that there is no such thing, because finding the period of the Fibonacci sequence modulo $m$ is a very similar problem to that of finding the period of the sequence $1,a,a^2,\ldots$ modulo $m$, a.k.a. the discrete logarithm problem, which is widely believed to be "hard". (The Fibonacci sequence is a 2nd-order linear recurrence sequence, while the powers of $a$ are a 1st-order linear recurrence sequence.)
As it sounds like you know already, if $m=p_1^{a_1}\cdots p_k^{a_k}$, then the period of a sequence modulo $m$ is the $\mathrm{lcm}$ of the periods modulo $p_1^{a_1}$, modulo $p_2^{a_2}$, etc. (This is a trivial consequence of the Chinese remainder theorem.)
The next natural step would be to reduce the problem from computing the Pisano periods for prime powers to computing them only for primes. As far as we know, $k(p^n)=p^{n-1}\cdot k(p)$ for any $n$ and any prime $p$, but it's still conjectured that there are infinitely many primes $p$ for which this fails. I don't think there's been any significant progress other than higher and higher computer checks, but then again, I really haven't been keeping up with this problem. This formula fails for a prime $p$ if and only if the prime is a Wall-Sun-Sun prime. The analog of such primes for the 1st-order linear recurrence sequences are Wieferich primes and their generalizations.
As far as finding a formula for $k(p)$ in terms of $p$, that should be hopeless, for the reason I mentioned at the start of my post.
If you want an algorithm, i.e. a program your computer can run to find out the period experimentally, then I'm afraid that's something I know nothing about (beyond the obvious naive one, of course); it would probably be helpful to you to look at the research papers of those mathematicians who have carried out the computer searches.