A selection of algorithms for computing the nth Fibonacci Number

A selection of algorithms for computing the nth Fibonacci Number

One of these algorithms even gets as fast as O(\log n)! Very impressive.

Advertisements

The Collatz Conjecture and Hailstone Sequences: Deceptively Simple, Devilishly Difficult

Here is a very simple math problem:

If a number is even, divide the number by two. If a number is odd, multiply the number by three, and then add one. Do this over and over with your results. Will you always get down to the value 1 no matter what number you choose?

Go ahead and test this out for yourself. Plug a few numbers in. Try it out. I’ll wait.

Back? Good. Here’s my example: I start with the number 12.

12 is even, so I divide it by 2.

12/2=6.

6/2=3.

3 is odd, so we multiply it by 3 then add 1.

(3*3)+1=10.

10/2=5.

(5*3)+1=16.

16/2=8.

8/2=4.

4/2=2.

2/2=1.

And we have arrived at one, just like we thought we would. But is this ALWAYS the case, for ANY number I could possibly dream of?

This may sound easy, but in fact it is an unsolved mathematics problem, with some of the best minds in the field doing research on it. It’s easy enough to check low values, but numbers are infinite, and can get very, very, very large. How do we KNOW that it works for every single number that exists?

That is what is so difficult about this problem. While every single number we have checked (which is a LOT) ends up at 1 sooner or later (some numbers can bounce around for a very long time, hence why they are called “hailstone sequences”), we still have no method to prove that it works for every number. Mathematicians have been looking for some method to predict this, but despite getting into some pretty heavy mathematics in an attempt to attack this problem, we still do not know for sure.

This problem is known as the Collatz Conjecture and is very interesting to mathematicians young and old because it is so easy to explain and play with, yet so tough to exhaustively prove. What do you think? Will this problem ever be solved? And what would be the implications if it was?

Here is some simple Python code that can display the cycles for any number you type in:

#!/usr/bin/python
num = int(input("Enter a number: "))
while num!=1:
if num%2 == 0:
num = num/2
else:
num = (num*3)+1
    print num

Periodic Last Digits of Fibonacci Numbers

Here’s something I was playing around with the other day.

Consider the Fibonacci sequence: 0, 1, 1, 2,3,5,8,13,21, \dots. F(n) = F(n-1)+F(n-2). I wanted to see if there was a pattern regarding the values of the ones digit in the fibonacci sequence. This is what I found:

The ones digits of the Fibonacci numbers are periodic, with period 60. This means that if you continue the sequence and look only at the ones digits of the numbers, they begin to repeat the same pattern after the 60th number. In addition, every 15th number in the sequence has a ones digit of zero. I wonder why this is. I can’t seem to find any other patterns at the moment. It probably has something to do with mod.

Here is the list of the 60 digit period (ones digits only):

1
1
2
3
5
8
3
1
4
5
9
4
3
7
0
7
7
4
1
5
6
1
7
8
5
3
8
1
9
0
9
9
8
7
5
2
7
9
6
5
1
6
7
3
0
3
3
6
9
5
4
9
3
2
5
7
2
9
1
0
---this is where the cycle starts over
1
1
2
3
5
8
...

Can you find any other interesting properties?

Fibonacci Numbers mod n

Taking the fibonacci sequence mod 2 provides this pattern:

Sequence:              1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,…
Sequence mod 2:   1, 1, 0, 1, 1, 0,   1,   1,   0,   1,   1,      0,    1,     1,…

Taking the fibonacci sequence mod 3 also produces an interesting pattern:

Sequence:              1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,…
Sequence mod 3:   1, 1, 2, 0, 2, 2,   1,   0,   1,   1,   2,      0,    2,     2,…

Mod 4:

Sequence:              1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,…
Sequence mod 4:   1, 1, 2, 3, 1, 0,   1,   1,   2,   3,   1,      0,    1,     1,…

This can be continued for mod n.

Consider this table from Pisano Periods – Wikipedia :

(let p_n be the period of fibonacci numbers mod n)

n p_n cycle
1 1 0
2 3 011
3 8 0112 0221
4 6 011231
5 20 01123 03314 04432 02241
6 24 011235213415 055431453251
7 16 01123516 06654261
8 12 011235 055271
9 24 011235843718 088764156281
10 60 011235831459437 077415617853819 099875279651673 033695493257291

Note also:

  • 2*3=6 which isp_4
  • 4*6=24 which is p_6 and p_9
  • 3*8=24 which is p_6 and p_9
  • the period for n=5 is 20, while the period for n=10 is 60. p_{2n}=3p_n for n=1,2 , n=3,6 and n=5,10 , and n=7,14 (p_{14}=48 according to OEIS)

Can we say that p_{2n}=3p_n \forall n \mid n \equiv 1 \mod 2 ?

Answer: no. n=9 provides a counter example because p_9=24 and p_{18}=24 . Therefore, p_{2n} \neq3p_n where n=9 .

If we extend our table, we can also see that p_{10}=60 and p_{50}=300 . In this case, p_{5n}=5p_n . This also works for n=5,25 , n=9,45 and possibly more. However n=1,5 and n=2,10 do not work. Can we say that p_{5n}=5p_n \forall n>2 ?

Answer: no, n=4 and n=11 do not work. Why are these special cases?

I’ll write a program to test this stuff more when I get home today.

Fibonacci Square Updates

So as I noted back in this post, I’ve got more fun things to share about this curious sequence. I got the idea from this video here, and decided to test it out on my own sequences. My “fibonacci grids” are similar to what is shown in the video, but in mine, you can see that at the beginning of each line, I retain the first number in my sequence on each line.

The basic premise of the video was that if one picks out a space of 2×2 numbers on this Fibonacci Grid, (he proceeded to write the original sequence and carry over no numbers, however) the determinant of the resulting “matrix” can be predicted cleverly by simply looking at the last number on the first line. What I’ve noticed is interesting because mine seems to rely on the parity of the starting number. My conjectures are as follows. I have not completed proofs as yet, but wanted to get this idea out there.

Conjecture 1. For the first and second values in a Fibonacci-like sequence (denoted here as f, s. respectively) in a 4 by r fibonacci square (using Nelson’s modified rules as noted in the original post), where f \equiv 1 \mod 2, then the determinant of any 2 by 2 square is (s*f)*(s+f)*r, where r is the starting “row” of the fibonacci square.

Conjecture 2. For the first and second values in a Fibonacci-like sequence (denoted here as f, s respectively) in a 4 by r fibonacci square (using Nelson’s modified rules), where f \equiv 0 \mod 2, then the determinant of any 2 by 2 square is f*(s+f)*r, where r is the starting “row” of the fibonacci square.

Now if only I were better at proofs…all the same, thought this was neat! Need to extend it to include arbitrary row lengths.

Fibonacci Squares with Arbitrary Starting Numbers

Consider the Fibonacci Sequence

0,1,1,2,3,5,8,13…

Each number in the sequence is the sum of the two that precede it. The sequence is defined as have 0 and 1 as its first numbers. But what if we chose different numbers to start with?

We’re going to make something I call a Fibonacci Square. It is a little bit of Fibonacci, a little bit of Pascal’s Triangle, and a little bit of my own creativity.

Let’s choose two arbitrary numbers to begin with. Let’s say, 6 and 2. We’ll call 6 f (the first number), and 2 s (the second number). We will now write our “Fibonacci” sequence as normal, but using f and s as our starting numbers instead. For the purpose of our “square” we are constructing, we’ll only write the first four terms for now.

6, 2, 8, 10

Okay, so we’ve got that. Now to continue the pattern we will start a new line below the one we’ve just written, and replace s (the previous second number) with the fourth number generated in our sequence above. This just means that our starting numbers (f and s) are now 6 and 10, respectively. Let’s write a new 4 term line with them.

6, 10, 16, 26

So our “square” so far is:

6,   2,   8, 10
6, 10, 16, 26

We can make more lines as much as we want with this technique. Just take the fourth number and replace it as the second starting number in the next line. The third line in this sequence would be:

6, 26, 32, 58

What is interesting to note is that a formula can be derived to determine what the fourth number on any given line will be. In fact, the formula can be applied to any length lines greater than 4. That means that if we put 5 terms on each line instead of 4, our formula would still work.

Let’s check out the formula:

(F(t)^n * (s+\frac{F(t-1)}{F(t)-1}f))-\frac{F(t-1)}{F(t)-1}f

  • F(t) is the t’th term of the Fibonacci Sequence (defined as starting at 0)
  • t = the number of terms on each line (in our example there are 4)
  • f = the number we first start with
  • s = the number that we originally had as our “second number”
  • n = the line number, starting at one. So for the three lines we calculated, they would have been n = 1, 2, and 3, respectively.

So, for example, we wondered what the number would be on the end of the 20th line of the sequence we started above, but we don’t want to write all that out. We can plug the values into our equation to find the answer.

(F(4)^{20} * (2+\frac{F(4-1)}{F(4)-1}6))-\frac{F(4-1)}{F(4)-1}6

If we condense that down (remember that F(4) means find the 4th term of the Fibonacci Sequence, which is 2), we get that the value on the end of the twentieth line in this sequence is 8,388,602. Wow! As you can see, when one creates a sequence in this manner, there is exponential growth.

Anyway, this is one of my pet projects and I hope you will find it interesting. I will probably make another post on other things I have found with this sequence, but this post is getting a bit long for now.