Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

closed as too localized by Felipe Voloch, Jon Bannon, Steven Landsburg, Andres Caicedo, Gjergji Zaimi Jun 1 '12 at 3:19

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

add comment

2 Answers

up vote 6 down vote accepted

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

share|improve this answer
    
Ah yes, I had a sneaking suspicion that might have something to do with it. Thanks again for the help Rob. –  Vincent Russo May 31 '12 at 17:47
add comment

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!

share|improve this answer
    
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! –  Vincent Russo May 31 '12 at 20:49
    
@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. –  Jyrki Lahtonen May 31 '12 at 22:28
add comment

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