Calculating Pisano periods for any integer

Question

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?

Answer 1

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.

Answer 2

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;
    }
}

Answer 3

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

Answer 4

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;
}

Answer 5

I observed the following: For primes p with last digit 3 or 7 the pisano period length is 2(p+1)/m with m integer. These periods all include two our four zeros. For primes ending on 1 or 9 the pisano period length is m/n(p-1)/ with m, n integer. Example: length(521)= 1/20 * 520 = 26, a surprisingly short period.

Answer 6

A small hack to Jonathan's answer (although this is in JS):

function getPisanoPeriod(m) {
  let a = 0
  let b = 1
  let c = 1
  limit = 1
  for(let i = 0; i < limit; i++){
      c = (a + b) % m
      a = b
      b  = c
      if(a == 0 && b == 1) return i + 1
      limit = limit + 1
  }
}

console.log(getPisanoPeriod(4))