0
$\begingroup$

In the paper "Fibonacci Series Modulo m" by D.D. Wall (found here), there is a table in the Appendix listing values for the function $k(p)$. This function is defined as the period of the Fibonacci numbers mod p before any repeats occur. For instance, k(7) = 16 since

\begin{align} F(p) \mod 7 = \{0, 1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1\} \end{align}

where $F(p)$ is the $p^{th}$ Fibonacci number. Hence, the values in the sequence above are cyclic after 16 terms. My question is again in regard to the table at the end that lists various values for the function $k(p)$.

The first few terms check out fine, however, for some values for instance 113 or 181, the values of $k(p)$ do not appear to be correct. To check the values, I wrote a quick script in Python that you're more than welcome to use.

phi = (1+5**0.5)/2

def F(n):
    return int(round((phi_pos**n - (1-phi_pos)**n) / 5**0.5))

def FModM(n,m):
    return F(n) % m

def k(p, nums):
    run = 0
    for i in range(1, len(nums)):
        if nums[i] == 0 and nums[i+1] == 1 and nums[i+2] == 1 and nums[i+3] == 2:
           run = i
           break
    print p,":",run

nums = []
max = 200
m = 101
for i in range(max):
    nums.append(FModM(i,m))
k(m,nums)

Both values 113 and 181 for instance return 0 since even after generating 200 terms (what max is defined to be in the program) no cycle has shown itself.

I'm not sure if the values are actually incorrect in the table, or if my understanding is not 100% on the matter. Any feedback would be very much appreciated. Thanks again.

$\endgroup$
0

2 Answers 2

7
$\begingroup$

Your program, being based on floating-point approximations, may run into problems with roundoff error. It's much easier to calculate Fibonacci numbers mod $p$ directly, using the recurrence $a_{n+1} = a_n + a_{n-1} \mod p$.

The Fibonacci numbers mod $113$ have period $76$ and the Fibonacci numbers mod $181$ have period $90$.

See also http://oeis.org/A001175

$\endgroup$
1
  • $\begingroup$ Ah yes, I had a sneaking suspicion that might have something to do with it. Thanks again for the help Rob. $\endgroup$ May 31, 2012 at 17:47
1
$\begingroup$

Sorry, I couldn't get access to the paper you referred to. For a prime modulus $p>5$ it is easy to show that the period of the Fibonacci sequence is a factor of either $p-1$ or $2(p+1)$ depending on whether $5$ is a quadratic residue modulo $p$ or not (or by reciprocity, whether $p\equiv\pm1\pmod5$ or not). This is because the roots of $$ x^2-x-1=0 $$ over $F_p$ are either in $F_p^*$ (if that polynomial factors modulo $p$), or in $F_{p^2}^*$. In the former case they are roots of unity of order that is a factor of $p-1$. And in the latter case the roots $\tau_1,\tau_2$ are conjugates of each other, and hence satisfy both equations $$ \tau_1^p=\tau_2,\qquad \tau_1\tau_2=-1 $$ implying that they both are roots of unity of order dividing $2(p+1)$. The periodicity then follows from Binet's formula.

Oh. Your program is leaving the integer domain. Are you sure you are not getting any overflows/loss of accuracy? You would need accuracy of something like 20 significant digits to handle $F_{200}$. Why aren't you using the recursive code? Storing two last entries is enough!

$\endgroup$
2
  • $\begingroup$ Ah I think I may have been a bit vague by using $p$ as the variable. I was just attempting to maintain the same convention in the paper, but $p$ is not necessarily a prime number. Still, thank you very much for your response and for your help! $\endgroup$ May 31, 2012 at 20:49
  • $\begingroup$ @Vincent, I would think that anything I said was in that paper:-) Undoubtedly they follow the usual route: prime, prime power, then CRT to the general case. $\endgroup$ May 31, 2012 at 22:28

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