Fibonacci Mystery - Numberphile

today I want to do a video response I response to one of our own numberphile videos because some time ago Brady made a video with our numberphile composer Alan Stuart's it was a video it was 40 minutes long this video which was a test to our loyalty I think but in that video have you made it through alan described composing one of his pieces about the Fibonacci sequence it involved the Fibonacci sequence and he came up with a question as a challenge I guess to the number files I'm not quite good enough in laughs to be able to explain why that is maybe a number file will be able to explain like this I'm going to answer his question today so what Alan was doing was he was trying to involve the Fibonacci sequence in a piece of music so first let's have a recap of the Fibonacci sequence very important sequence in mathematics it's quite easy it starts with 1 then it's 1 again and then you add the previous 2 value so you add these two and you get the next number so that's just 1 plus 1 equals 2 then you add these two values that's 1 plus 2 equals 3 then you add the previous 2 that's 2 plus 3 equals 5 and you keep going in this way 6760 5 and so on okay so there's the Fibonacci sequence and what Allan was doing was to turn this into a piece of music he was dividing by 7 he's going to divide all these Fibonacci numbers by 7 now you can't divide exactly by 7 most of the time and so he looked at the remainder what you get left over when you divide by 7 that's one that's two that's three that's 5 now 8 when you divide 8 by 7 that's one with one left over that's what he wrote down then 13 divided by 7 is 1 with 6 left over 21 divided by 7 is 3 exactly it has zero left over so you write zero and we're going to continue in that way we're going to do all the remainders so he wrote out all the remainders I need to make it a piece of music he turned to these remainders into musical notes so it corresponds to notes but he didn't notice a pattern when he did it curiously he found the pattern repeated it actually repeated every 16 numbers so here we go 1 1 2 3 5 1 6 0 6 6 5 4 - 6 1 0 1 1 2 3 and then the pattern repeated and he asked what is this about is this a thing and it is a thing it's actually called a Poisson Oh Pierre pisano period is named after Leonardo Pisano and if you think you haven't heard of him before are you wrong because that's just another name of Fibonacci so this is a pisano period now Allen chose seven to do this because that helps him make his musical notes if you'd pick any number though he would have got up here as well but the length of the period would have been different so he divided by 2/3 divided by 90 or 700 he would have got a cyclic pattern if we divide by 5 as an example this should be quite easy divided by 5 this is when I'll make a mistake 1 1 2 left over 3 divided by 3 5 plus 3 left over 5 divided by 5 is 0 0 left over 8 divided by 5 is a 1 a 3 left over would be a 3 4 left over that's one left over a 0 left over and I think that's actually the full pattern and the when you divide by 5 the period is 20 so this is the whole thing here at this point it will start to repeat again the zeros I want to point out are interesting the zeros are when you can divide by 5 exactly so there's a 0 here there's a 0 here this is 0 here as well oh look at this no look I just noticed that laser mistake I said that look I said this had a remainder of 5 but look I don't need this that has a remainder of 0 that just shows you doing it all alive I I'm doing it up now I noticed that that was a mistake I noticed there was a problem there because I knew that the period has only can only have one zero two zeros or four so that's another result in mathematics so because there was three I knew there was a problem there and I found it so that's another example of the Pisano period if you another thing I want to point out then it's actually every fifth number every fitnah but there is a there is a proper bit of it's behind this room actually do it there's another result about Fibonacci numbers it says a Fibonacci number let's call it the nth Fibonacci number exactly divided which I use a vertical line for another Fibonacci number which I'm going to call FM the result is if and only if n divides M so the little index at the bottom here if they divide then the Fibonacci numbers divide as well just to give you an example then we were doing if we look at the fifth Fibonacci number that is equal to 5 so so 5 divides Fibonacci numbers if and only if there's a little symbol there 5 divides the value of the index so every fifth number every 5th Fibonacci number is divisible by 5 that's what I chose let me just do one more example of that to make the point I took the next one look the 6th Fibonacci number is 8 so 8 will divide Fibonacci numbers exactly when 6 that's the index here divides M so every sixth number every sixth Fibonacci number is divisible by 8 so this Pisano period idea was first discovered by a mathematician called Lagrange in 1774 and he was actually looking at the patterns when you divide by 10 when he divide by 10 what you have left over it's just the last digit let's do a quick version of that what colors do I need now I have to use black 5 8 13 divided by 10 is 1 with 3 left over 21 divided by 10 has 1 left over and what he discovered was the they had 8 they did have a pattern and the pattern had a period of 60 so the last digits of the Fibonacci sequence have a pattern of length 60 if you divide by a hundred then you're actually looking at the last two digits of the Fibonacci sequence that has a pattern of 300 lengths 300 if you look at the last three digits that's dividing by a thousand that has a pattern of length 1,500 the other easy way to do this is you don't have to write out the Fibonacci sequence and do each calculation for each number actually there's a property of these remainders that you can just add up the previous two remainders let's have a look so if we look at an example like here this is when I was dividing by 7 for the remainder of 4 plus a remainder of 2 gives me the next remainder it's just like the Fibonacci sequence gives me a remainder of 6 remainder of 2 plus a remainder of 6 it actually wraps back because we're dividing by 7 when you go past 7 it wraps back to 0 so this will take me back to 1 then 6 plus 1 will give me 7 which wraps back to 0 so alack I can actually do these sequences by simply adding up the remainders so using this idea when you add the previous two remainders gives you the next one actually kind of explains what's going on when I had a 1 and a 0 here next to each other then when I add them together I get a 1 then I add 0 plus 1 and I get another one so I've got 2 ones in a row 1 and 1 and then that's the beginning of the Fibonacci sequence and then it just carries on so whenever you have a 0 next to a 1 you're going to end up back into the Fibonacci so you're going to end up back to the start of the Fibonacci sequence and it has been shown that this will always happen so that 0 1 is like a big trigger point yeah yeah that's going to send you back to the start again and that will happen in the other sequences that we had here as well look this is the dividing by 5 it has a period of 20 that's the end of it and there's the 0 and the 1 again and that's going to send you back to the start so you're always going to end up back to the start this period is always going to repeat however there is no general formula for the length of the period so that's something we don't know yet that two boxes of nine and a box of six there we go that makes 44

Channel: Numberphile

Views: 2,505,480

Rating: 4.9530668 out of 5

Keywords: Fibonacci Number (Literature Subject), numberphile, pisano, pattern

Id: Nu-lW-Ifyec

Length: 9min 48sec (588 seconds)

Published: Wed Sep 18 2013

Reddit Comments

[u/CoolHeadedLogician]

is there a given name for the problem of finding the length of period mentioned at the end?

[u/oldrinb]

One of my calculus professors asked me to prove that every Fibonacci sequence mod [;n;] is periodic. He didn't know he rediscovered Pisano periods but he found the pattern when he was bored as an undergraduate and said I reminded him of it.

[u/MatrixFrog]

If you already know what the Fibonacci sequence is, skip to 1:30 or so.

[u/TheSitarHero]

My jaw actually dropped when I realised he was about to show that the modulus Fibbonacci sequences had the same additive property as the normal Fibbonacci.

I love numberphile.

[u/flebron]

I've written something about finding the Pisano periods algorithmically here. There's a SPOJ problem on finding them, though my Haskell for that is not nearly as fast as some others, so there's likely way better solutions.

Essentially, the pisano period (mod m) is the multiplicative order of the matrix M = [[1, 1], [1, 0]] in the group (Z/mZ)^{2 x 2.} You then try to do magic to find this order.

[u/Youre_Government]

Question- At 4:50 he says there could only be 1,2, or 4 zeros. Now I'm assuming that taking the fibonacci sequence mod n creates a group (which I don't really feel like checking), and he's going on the theorem stating that the order of any element in a group must divide the order of the group. But wouldn't that mean there could also be five zeros, since the group has an order of 20?

[u/sharkmeister]

Some fooling around in excel suggest that using integer with modulo functions gives similar results dividing by non-integers. It looks like the pisano period of pi is 34; 1, 2, 3, 1, 1, 0, 2, 2, 1, 1, 2, 0, 0, 0, 0, 1, 1, 2, 1, 0, 1, 2, 1, 0, 1, 2, 1, 0, 1, 2, 0, 0, 0 -- it also looks like the zeroes rule does not apply for non-integers. =INT(MOD(Fibnum, non-int))

[u/man_after_midnight]

Fun fact, related to these periods:

The n^th Fibonacci number is divisible by exactly the same number of powers of 5 as n is.

[u/jr_flood]

Another cool property of the Fibonacci sequence:

Take the limit of Fn+1/Fn as n--> infinity and you get the golden ratio.