# 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.

# 4 Is The Magic Number – Riddle

So fishes56 alerted me to this riddle in a comment here, and if you didn’t see it I wanted to share it here in a separate post cause its a little fun thing to think about.

12 is 6, 6 is 3, 3 is 5, 5 is 4, 4 is 4.

4 is the magic number, why?

68 is 10, 10 is 3, 3 is 5, 5 is 4, 4 is 4.

4 is the magic number, why?

26 is 9, 9 is 4, 4 is 4. 4 is the magic number, why?

Give it a try. ðŸ™‚

# 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?

# Adding Primes to Produce a Prime

Inspiration for this problem comes from my good friend Johnny Aceti.

Consider numbers $x,y \in \mathcal{P}$ where $\mathcal{P}$ is the set of all prime numbers $\in \mathbb{N}$.

Conjecture 1. There exist consecutive $x,y \in \mathcal{P}$ such that $x+y \in \mathcal{P}$.

Is this true? Well lets see.

Every prime except 2 is odd. Let’s first look at adding together 2 odd primes. Odd numbers are equivalent to $1 \mod 2$, and if one adds together two numbers that are $1 \mod 2$, you get a sum that is $0 \mod 2$. This means the sum is even, and since we can’t add two primes to get 2, this means that you cannot add an even number of odd primes to produce a prime. This takes out just about every possibility for this conjecture to be true, but we haven’t considered 2 yet, since before we were only working with odd primes.

Let’s try the case where we use 2 as $x$.

$2 \equiv 0 \mod 2$ and every other odd prime is $1 \mod 2$. Therefore, if we added them, we could get a sum that is $1\mod 2$. So far so good, this means our sum is odd. But is it prime? The only instance involving 2 if $x, y$ have to be consecutive is $2+3=5$. 5 is prime, and that becomes the only $x,y$ that satisfy Conjecture 1.

But what if $x,y$ didn’t have to be consecutive? Does the use of 2 still work?

Well, the short answer is sometimes.

$\boldsymbol{2+3=5}$
$\boldsymbol{2+5=7}$
$2+7=9$

Uh oh. 9 isn’t prime. Therefore, the use of 2 as $x$ or $y$ only works sometimes. This problem isn’t very interesting with only two variables though. Let’s add more…

$***************************$

Consider consecutive numbers $x,y,z \in \mathcal{P}$ where $\mathcal{P}$ is the setÂ  of all prime numbers $\in \mathbb{N}$.

$2+3+5=10$
$3+5+7=15$
$\boldsymbol{5+7+11=23}$
$\boldsymbol{7+11+13=31}$
$\boldsymbol{11+13+17=41}$
$13+17+19=49$
$\boldsymbol{17+19+23=59}$
$\vdots$

If we continue adding numbers in this way, how many times will the resulting sum be a prime? Is there any way to predict what triples of numbers produce primes and which do not?

Here are some more examples (all of which have prime sums):

$19 + 23 + 29 = 71$
$23 + 29 + 31 = 83$
$29 + 31 + 37 = 97$
$31 + 37 + 41 = 109$
$41 + 43 + 47 = 131$
$53 + 59 + 61 = 173$
$61 + 67 + 71 = 199$
$67 + 71 + 73 = 211$
$71 + 73 + 79 = 223$
$79 + 83 + 89 = 251$
$83 + 89 + 97 = 269$
$101 + 103 + 107 = 311$
$109 + 113 + 127 = 349$
$139 + 149 + 151 = 439$
$149 + 151 + 157 = 457$
$157 + 163 + 167 = 487$
$163 + 167 + 173 = 503$
$197 + 199 + 211 = 607$

Can we derive a pattern or a formula such that $x, y, z \in \mathcal{P}$ always holds?

# 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 is$p_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.

# Numbers, Reverses, and Sums Divisible by 11 (Part 2)

Update: As you can see in my previous post A Two Digit Number and Its Reverse Sums to a Multiple of 11, if you have a two digit number, you can

• use the reverse of that number to sum together to a multiple of 11.
• sum the digits to find a factor of the sum.

For example, if one chooses 43 + 34 = 77, one can see that 4+3=7 and 7*11 is 77.

Upon further investigation, I have found that one can use any number whose length is a power of two. This means that not only do 2 digit numbers work in this way, but so do 4 digit numbers, 8 digit numbers, 16 digit numbers, and so on…

However, when one gets to digits larger than 2 (4,8,16), the part about summing the digits to get a factor no longer works. Strangely, that only seems to work on 2 digits.