CODEWITHSUNDEEP
pythonintervalsfibonacciperiod
Tupperward
Tupperward

Reputation: 63

Finding the Period of a Pattern in a List

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?

Upvotes: 6

Views: 4307

Answers (2)

jnnnnn
jnnnnn

Reputation: 4418

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.

Upvotes: 2

Brent Washburne
Brent Washburne

Reputation: 13158

It's failing because modlist is a list of integers, not strings. Change the second and fourth lines in principal_period like this:

def principal_period(modlist):
    a = ''.join(str(m) for m in modlist)
    i = (a+a).find(a, 1, -1)
    return None if i == -1 else a[:i]

Instead of str(modlist) you need to join the numbers into a long string, and you had a typo on the last line, n[:i] instead of a[:i].

Running this program now shows:

How many terms? 
> 9
[1, 1, 2, 3, 5, 8, 13, 21, 34]

Do you want to find the modulo?
1. Yes
2. No
> 1
What modulo do you want to use?
> 2
[1, 1, 0, 1, 1, 0, 1, 1, 0]
The period of the pattern is  110
Goodbye!

What's interesting about this output is that Fibonacci numbers follow the sequence odd, odd, even. Try it on 99 terms!

Upvotes: 0

Related Questions