4
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Apparently, the "pisano period" of a number $m$ is the period of the Fibonacci sequence modulo $m$. $\endgroup$ – Gerry Myerson Oct 8 '13 at 22:31
  • 3
    $\begingroup$ Not sure what exactly you're looking for. Presumably you've looked already at en.wikipedia.org/wiki/Pisano_period $\endgroup$ – Lucia Oct 9 '13 at 0:03
  • $\begingroup$ Could you clarify what you mean by "alternative for solving this problem"? As it stands, this question may get closed with the reason "unclear what you're asking". $\endgroup$ – S. Carnahan Oct 9 '13 at 0:10
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I don't think it's accurate to say that the discrete logarithm problem is the same as finding the order of $a$ modulo $m$. $\endgroup$ – Greg Martin Oct 9 '13 at 1:56
  • 2
    $\begingroup$ @GregMartin - Could you elaborate on that? $\endgroup$ – graduate student Oct 9 '13 at 2:10
  • 1
    $\begingroup$ @GregMartin: I see your point: if $g$ is a primitive root modulo $m$ and $a\equiv g^k\bmod m$, then $\mathrm{ord}_m(a)=\dfrac{\varphi(m)}{\gcd(k,\varphi(m))}$, which is strictly less information than $k$. Is there a separate name for the problem of finding a multiplicative order, though? $\endgroup$ – Zev Chonoles Oct 9 '13 at 2:16
  • $\begingroup$ I don't know of one, other than "finding the order".... $\endgroup$ – Greg Martin Oct 9 '13 at 16:50
  • $\begingroup$ The difficulty with finding the period modulo a large prime $p$ is that it can be as hard as factoring $p-1$ or $p+1$ (depending on whether $(5/p)=+1$ or $-1$). $\endgroup$ – Noam D. Elkies Oct 18 '16 at 0:56
3
$\begingroup$

Here's a bit of C++ code I found. It calculates the length of the Pisano Period for (almost) any modulus.

Source: https://medium.com/competitive/huge-fibonacci-number-modulo-m-6b4926a5c836#.8n3hmh3el

long long get_pisano_period(long long m) {
    long long a = 0, b = 1, c = a + b;
    for (int i = 0; i < m * m; i++) {
        c = (a + b) % m;
        a = b;
        b = c;
        if (a == 0 && b == 1) return i + 1;
    }
}
$\endgroup$
2
$\begingroup$

Here is a bit of Haskell code from my utility library that calculates the Pisano period for any given modulus with reasonable efficiency. All the intelligence is in the pisano* functions. The rest are just my common utility functions I had to throw in to make it work. Math.NumberTheory.Primes.Factorisation is from the excellent arithmoi package available from hackage at [https://hackage.haskell.org/package/arithmoi] and easily installed via cabal.

import qualified Data.Array.Unboxed as ArrayUnboxed
import qualified Data.Set as Set

import qualified Math.NumberTheory.Primes.Factorisation as MNPF

factorise :: Integral a => a -> [(a,Int)]
{-# INLINE factorise #-}
factorise n = map (\(a,b) -> (fromIntegral a,b)) $ MNPF.factorise $ fromIntegral n

divisors :: Integral a => a -> [a]
{-# INLINE divisors #-}
divisors n = map fromIntegral $ Set.toList $ MNPF.divisors $ fromIntegral n

modFibonacciPair :: (Bits b, Num b, Integral b, Integral a) => a -> b -> (a,a)
{-# SPECIALIZE modFibonacciPair :: Int -> Integer -> (Int,Int) #-}
{-# SPECIALIZE modFibonacciPair :: Integer -> Integer -> (Integer,Integer) #-}
{-# SPECIALIZE modFibonacciPair :: Int -> Int -> (Int,Int) #-}
{-# SPECIALIZE modFibonacciPair :: Integer -> Int -> (Integer,Integer) #-}
modFibonacciPair m n
  | n==0      = (0,1)
  | even n    = (rm1,r0)
  | otherwise = (r0,rp1)
    where
      (fk,fkp1) = modFibonacciPair m (quot n 2)
      rm1 = (fk*(2*fkp1-fk))   `mod` m
      r0  = (fk*fk+fkp1*fkp1)  `mod` m
      rp1 = (fkp1*(2*fk+fkp1)) `mod` m


pisanoSmall :: ArrayUnboxed.Array Int Word8
pisanoSmall = ArrayUnboxed.listArray (1,47) [1,3,8,6,20,24,16,12,24,60,10,24,28,48,40,24,36,24,18,60,16,30,48,24,100,84,72,48,14,120,30,48,40,36,80,24,76,18,56,60,40,48,88,30,120,48,32,24,112]

pisanoPrimePeriod :: Integral a => a -> a
{-# SPECIALIZE pisanoPrimePeriod :: Int -> Int #-}
{-# SPECIALIZE pisanoPrimePeriod :: Integer -> Integer #-}
pisanoPrimePeriod p
  | fromIntegral p<pb  = error "pisanoPrimePeriod:: undefined for non-positive arguments"
  | fromIntegral p<=pe = fromIntegral $ (ArrayUnboxed.!) pisanoSmall $ fromIntegral p
  | otherwise          = fromIntegral $ head $ filter (\ d -> modFibonacciPair (fromIntegral p) d==(0,1)) $ sort $ ds
  where
    (pb,pe) = ArrayUnboxed.bounds $ pisanoSmall
        p5    = p `mod` 5
        ds    = if p5==1 || p5==4
                then            divisors $ toInteger (p-1)
            else map (2*) $ divisors $ toInteger (p+1)

pisanoPeriod :: Integral a => a -> a
{-# SPECIALIZE pisanoPeriod :: Int -> Int #-}
{-# SPECIALIZE pisanoPeriod :: Integer -> Integer #-}
pisanoPeriod n
  | fromIntegral n<pb  = error "pisanoPeriod:: undefined for non-positive arguments"
  | fromIntegral n<=pe = fromIntegral $ (ArrayUnboxed.!) pisanoSmall $ fromIntegral n
  | otherwise          = fromIntegral $ foldl' lcm 1 [(if a>1 then p^(a-1) else 1)*pisanoPrimePeriod p|(p,a)<-factorise $ fromIntegral n]
  where
    (pb,pe) = ArrayUnboxed.bounds $ pisanoSmall
$\endgroup$
0
$\begingroup$

Below are two implementations of the same iterative algorithm that generates the Pisano periodic sequence for any given modulo n under the following contraints:

\begin{equation} 1 \leqslant n \leqslant CR \end{equation}

Where CR stands for your computing resources. In my case, \begin{equation} CR \approx10,000,000,000 \end{equation}

The algorithm is constructed around the ideas that a Pisano sequence always starts with 0 and 1, and that this sequence of Fibonacci numbers taken modulo n can be constructed for each number by adding the previous remainders and taking into account the modulo n.

C#

public static IEnumerable<int> PisanoPeriodicSequence(int n)
{
    int current = 0, next = 1;

    yield return current;

    if (n < 2) yield break;
    next = current + (current = next);

    while (current != 0 || next != 1)
    {
        yield return current;
        next = current + next >= n ? current - n + (current = next) : current + (current = next);
    }
}

C++

std::vector<int> pisano_periodic_sequence(int n)
{
    std::vector<int> v;
    int current = 0, next = 1;

    v.push_back(current);

    if (n < 2) return v;
    current = (next += current) - current;

    while (current != 0 || next != 1)
    {
        v.push_back(current);
        current = current + next >= n ? (next += current - n) + (n - current) : (next += current) - current;
    }

    return v;
}
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.