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?

score 1 · Accepted Answer · answered Sep 14 '20 at 05:38

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.

score 0 · Answer 2 · answered Apr 26 '16 at 20:17

0

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!

answered Apr 26 '16 at 20:17

Brent Washburne

12,904
4
60
82

This ended up not working for me. I changed the code like you suggested but still got a None response on the period. – Tupperward Apr 26 '16 at 20:49
It doesn't work on any number of terms. Did you try 9 and 99? – Brent Washburne Apr 26 '16 at 20:54
This did work with 9 and 99, but it's not working for all lengths of terms. I was also able to find the len(principal_period(modlist)) to get the number of terms in modlist before the pattern repeats. This was the period I was looking for. However, when I use a term like 12 it provides me with a None, giving a TraceBack for len(None). Additionally, this solution only seems to work when modx = 2. – Tupperward Apr 26 '16 at 21:17
Yes to everything in your comment, except that 90 terms, modulo 4, returns a pattern of 112310. The pattern must be repeated fully (89 or 91 terms is too few/many). This is a requirement of the `principal_period` code. – Brent Washburne Apr 26 '16 at 21:34
Well, it's more functional than what I had. But I was still hoping to be able to find the period of the pattern for each case. I mean, I'm able to find it visually for all of these cases. Say I pick term = 20 and modulo = 3 the period should come out to 8 because modlist = [1,1,2,0,2,2,1,0,1,1,2,0,2,2,1,0,1,1,2,0]. – Tupperward Apr 26 '16 at 23:03
Change the last line to `return [] if i == -1 else a[:i]`, then you can use `len(principal_period(modlist))` – Brent Washburne Apr 27 '16 at 00:09

Finding the Period of a Pattern in a List

2 Answers2