The Fibonacci Sequence as a Functor
math3ma.com
math3ma.com
Of course since G is a left adjoint it has the dual property that lcm(G(n),G(m)) = G(lcm(n,m)).
Can we do more advanced category theory here? What is the Kan extension of the Fibonacci sequence along the Mersenne numbers?
That entry point sequence is weird.
Here is the next fib in a sequence (in psuedocode):
(a, b) -> (a, (b, a+b))
val fibonacci: Iterator[Int] =
Iterator.unfold((1, 1)) {
case (x, y) => Some((x, (y, x + y)))
}
> fibonacci.take(8).toList
1, 1, 2, 3, 5, 8, 13, 21 (a, b) -> (a, (b, a+b))
[0]https://en.wikipedia.org/wiki/Fibonacci_number#Limit_of_cons...
Abstraction should be introduced only when it aids understanding or problem solving. Shoehorning functors into basic topics like the Fibonacci sequence leaves a bad taste in my mouth. It gives the impression that category theory is just some contentless linguistic gloss, instead of, for example, a useful tool for facilitating computations in algebraic topology.
I came across this "commutative square" involving GCD and fib myself a couple of years ago. I came at it from noticing that there was a similar structure in iterative fib to the recursive Euclidean algorithm.
Note the "a, b = b, a + b"
def f(n):
a, b = 0, 1
for i in range(0, n):
a, b = b, a + b
return a
def gcd(a,b):
if(b==0):
return a
else:
return gcd(b,a%b)
>Category Theory doesn’t deal with number theory all that much.
Not sure where you are drawing the line here since algebraic geometry (aka modern number theory) makes extensive and extremely deep use of category theory. Ravi Vakil’s Rising Sea being the best intro to this point of view.
This example is just a fun way to talk about posets.
- People who know some category theory can sharpen their knowledge of it. They can ask followup questions, like does the Fibonacci sequence have a left adjoint? The answer is yes, which is what the top comment on this HN page talks about.
- People who don't know category theory might use this to learn some. In which case, we have a case of number theory having applications to category theory rather than the expected converse, which would be category theory having applications to number theory.
n n
φ - (1/φ)
F(n) = -----------
√5