Finding the Period of a Pattern in a List

Question

I'm relatively new to coding but I saw a great episode of Numberphile where they use a particular repeating pattern of the modulus of the Fibonacci sequence to assign tones to the resulting number. What a great little experiment to test my knowledge out on!

So I was able to create a simple loop to create a list of the Fibonacci sequence and another function to calculate the remainder of the generated sequence after dividing by n. But finding the period of the pattern in that modulus list is proving to be difficult.

Here's what I have so far:

#Fibonacci.py
#Basic terms
fiblist = list()
inp = "> "
n=None

#Calculates the FIbonacci sequence
def fib(n):
    a,b = 0,1
    while True:
        try:
            print "How many terms? "
            n = int(raw_input(inp))
            if n <= 0:
                print "Please enter a positive integer."
                continue
            else:
                for i in range(0,n):
                    a,b = b, a + b
                    fiblist.append(a)
                break
        except ValueError:
            print "Please enter a positive integer, not a letter or symbol"
            continue    
    return fiblist

#Calculates the modulo of each integer in fiblist
def modulo(n):  
    print """
Do you want to find the modulo?
1. Yes
2. No"""
    choice = raw_input(inp)
    if choice =="1":
        modlist = list()
        print "What modulo do you want to use?"
        modx = int(raw_input(inp))
        modlist = [x % modx for x in fiblist]
        print modlist
        print "The period of the pattern is ", principal_period(modlist)
        print "Goodbye!"
    else: 
        print "Goodbye!"

#Calculates the period of the modulo pattern of the Fibonacci sequence
def principal_period(modlist):
    a = str(modlist)
    i = (a+a).find(a, 1, -1)
    return None if i == -1 else n[:i]

print fib(n)
modulo(n)

The part that's failing me is

def principal_period(modlist):
    a = str(modlist)
    i = (a+a).find(a, 1, -1)
    return None if i == -1 else n[:i]

which always returns "None" I got this from the thread over here regarding the answer. I honestly do not understand this answer very well and it is not giving me the desired result.

Do you have any suggestions for calculating the period of a repeating pattern in a given list?

Answer 1

Here's a simple algorithm to find the period of a discrete function:

def findperiod(f, minlength=1, repetitions=2):
    """Find the period of a function f.

    Idea: assume length i = 1. Check that second copy is same as first (j
    iteration). If not, assume length 2. And so on. Once second copy matches
    first (no j breaks), return assumed length.

    The optional repetitions argument can be increased to check for more
    repetitions than the default 2 (two copies of the same sequence at the start
    of the list).

    Returns None if not enough repetitions are found in first billionish values.
    """
    for i in (range(minlength, 2**30)):
        for rep in range(1, repetitions):
            for j in range(i):
                if f(j) != f(i*rep+j): break
            else: return i

If your function is expensive to compute, then memoization is a good idea. I have not done so here because it can use a lot of memory if not necessary.