6
$\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
  • 4
    $\begingroup$ Apparently, the "pisano period" of a number $m$ is the period of the Fibonacci sequence modulo $m$. $\endgroup$ Oct 8, 2013 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, 2013 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, 2013 at 0:10

6 Answers 6

11
$\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$
6
  • 2
    $\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$ Oct 9, 2013 at 1:56
  • 2
    $\begingroup$ @GregMartin - Could you elaborate on that? $\endgroup$ Oct 9, 2013 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$ Oct 9, 2013 at 2:16
  • 1
    $\begingroup$ I don't know of one, other than "finding the order".... $\endgroup$ Oct 9, 2013 at 16:50
  • 3
    $\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$ Oct 18, 2016 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$
1
  • $\begingroup$ There is a great answer above that speaks about factorisation. Factorisation can be solved in O(n^(1/4)) complexity as far as I know. Why don't you use it in your answer. Looks like that your solution is O(n^2). The Haskell code below does use factorisation $\endgroup$ Feb 9, 2023 at 14:48
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$
0
$\begingroup$

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.

$\endgroup$
1
0
$\begingroup$

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))
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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