Well, that’s weird: Fibonacci edition

About six years ago, I read a puzzle about Fibonacci numbers in CACM and tried to understand the solution, so when I recently saw on quora the question “Is every Fibonacci number divisible by 31 also divisible by 61?” I was interested enough to figure out (to my surprise) that indeed every one is: every 15th Fibonacci number is divisible by 61, but only every 30th is divisible by 31.

This I found unusual and amazing, and I wondered, for what other primes is this true? Naturally I wrote some Python.

#!/usr/bin/python -utt
# vim:et:sw=4

'''
Let f(n) be the nth Fibonacci number (f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2))
For prime p, let ff(p) be the smallest n such that p|f(n),
e.g. ff(3)=4 because f(4)=3

Now, what primes (p, p2) satisfy p>p2 but ff(p)<ff(p2) and ff(p)|ff(p2)?
'''
import sys

def main(maxx):
    '''
    Get primes up to /maxx/, and the first /maxx/ Fibonacci numbers,
    then check for the criteria described above.
    '''
    plist = prime_list(maxx)
    flist = fib_list(maxx)
    ff = dict()
    for p in plist:
        for n, f in enumerate(flist):
            if f >= p and f % p == 0:
               ff[p] = n        # e.g. since f(4) == 3, ff[3] = 4
               break
        else:
            print "Couldn't find fib which %d divides" % (p)
    # Now ff[p] is idx of 1st fib that p divides
    for idx, p in enumerate(plist):
        f = ff[p]
        for j, p2 in enumerate(plist[:idx]):
            # for p2 < p
            f2 = ff[p2]
            if f2 > f and f2 % f == 0:
                print 'f(%d) = %d and f(%d) = %d' % (p, f, p2, f2)
            
    sys.exit(0)

def prime_list(pmax):
    '''
    Return a list of prime numbers up to pmax (sloppy criterion)
    '''
    # First two nontrivial primes
    plist = [2, 3]
    # Look for further primes by formula p = 6k +/- 1 for some k
    for cseed in range(6, pmax, 6):
        cand1, cand2 = cseed - 1, cseed + 1
        for p in plist[2:]:
            # Zero a cand if another prime p>3 divides it.
            # Need not check p≤3 because of construction.
            if cand1 == cand2:
                # must both be zero
                break
            if cand1 and cand1 % p == 0:
                cand1 = 0
            if cand2 and cand2 % p == 0:
                cand2 = 0
        else:
            append_t(plist, cand1)
            append_t(plist, cand2)
    return plist

def append_t(alist, athing):
    '''
    Helper: append /athing/ to /alist/ but only if /athing/ is "true"
    '''
    if athing:
        alist.append(athing)


def fib_list(fmax):
    '''
    Return a list of the first /fmax/ Fibonacci numbers
    '''
    bak1, cur = 0, 1            # f(0)=0, f(1)=1
    flist = [bak1, cur]
    for n in range(2, fmax):
        bak1, cur = cur, cur + bak1
        flist.append(cur)
    assert flist[5] == 5        #print 'DEBUG:', 5, flist[5]
    #print 'DEBUG:', flist
    return flist

if __name__ == '__main__':
    maxx = 99
    if len(sys.argv) > 1:
        maxx = int(sys.argv[1])
    main(maxx)

Running it produces:

Collins-MacBook-Pro:fib31 collin$ ./pfib.py 
f(61) = 15 and f(31) = 30
f(89) = 11 and f(43) = 44
Collins-MacBook-Pro:fib31 collin$ 

Whoa, really? Every 11th prime is divisible by 89, but only every 44th is divisible by 43? H'm.

f(11)=89, f(22)=17711, f(33)=3524578, f(44)=701408733

Every one of those guys is divisible by 89, but only the last is divisible by 43. How weird is that? And from looking at the pattern of what happens to f(n) mod 89 as n increases, it's clear that indeed every 11th Fibonacci number is divisible by 89, and every 44th is divisible by 43.

If instead of 99 we say 199 or 299, what do we get?

Collins-MacBook-Pro:fib31 collin$ ./pfib.py 199
f(61) = 15 and f(31) = 30
f(89) = 11 and f(43) = 44
f(199) = 22 and f(43) = 44
Collins-MacBook-Pro:fib31 collin$ 

OK, I examined that one, and everything is as it seems. What if we go another 100?

Collins-MacBook-Pro:fib31 collin$ ./pfib.py 299
f(61) = 15 and f(31) = 30
f(89) = 11 and f(43) = 44
f(199) = 22 and f(43) = 44
f(211) = 42 and f(83) = 84
f(211) = 42 and f(167) = 168
f(229) = 114 and f(227) = 228
f(233) = 13 and f(79) = 78
f(233) = 13 and f(103) = 104
f(233) = 13 and f(131) = 130
f(281) = 28 and f(83) = 84
f(281) = 28 and f(167) = 168
f(281) = 28 and f(223) = 224
Collins-MacBook-Pro:fib31 collin$ 

Well, that was fun if not exactly insightful. Why so many from 200–299, compared to the range 1–199? But the upshot is, we could ask a number of other questions, like

• Is every Fibonacci number that's divisible by 89 or 199 also divisible by 43? (Yes.)
• Is every Fibonacci number that's divisible by 79 or 103 or 131 also divisible by 233? (Yes.)

and so on. No idea why, but there it is.