[HN Gopher] The Fibonacci Sequence as a Functor
___________________________________________________________________
The Fibonacci Sequence as a Functor
Author : poetically
Score : 35 points
Date : 2021-11-28 05:48 UTC (2 days ago)
(HTM) web link (www.math3ma.com)
(TXT) w3m dump (www.math3ma.com)
| OscarCunningham wrote:
| Since the Fibonacci sequence preserves limits, the adjoint
| functor theorem says there must be some function G such that n
| divides F(m) if and only if G(n) divides m. This is called the
| sequence of entry points for the Fibonacci sequence, because G(n)
| is given by the first m such that n divides F(m)
| [https://oeis.org/A001177].
|
| 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?
| ogogmad wrote:
| I was thinking about finding a left adjoint G. I see you've
| proven its existence using a sledgehammer: the adjoint functor
| theorem. Your explicit construction for G(n) as the _smallest_
| m such that n divides F(m) is very informative. It goes well
| with the idea that an adjoint is somehow an optimiser. Thanks.
|
| That entry point sequence is weird.
| adamgordonbell wrote:
| A fib sequence can be defined corecursively using unfold and its
| actually a nice way to write it in some languages.
|
| Here is the next fib in a sequence (in psuedocode):
| (a, b) -> (a, (b, a+b))
|
| And then you can get a sequence with unfold by giving it some
| starting numbers: val fibonacci: Iterator[Int]
| = Iterator.unfold((1, 1)) { case (x, y) =>
| Some((x, (y, x + y))) }
|
| (That is Scala. But lots of languages have an unfold method)
| > fibonacci.take(8).toList 1, 1, 2, 3, 5, 8, 13, 21
| agumonkey wrote:
| (a, b) -> (a, (b, a+b))
|
| funny it's almost graphically equivalent to the geometric ratio
| zuminator wrote:
| It's not _almost_ equivalent to the geometric ratio, it _is_
| the geometric (aka golden) ratio, at the limit, as first
| observed by none other than Johannes Kepler [0]. You are in
| heavenly company!
|
| [0]https://en.wikipedia.org/wiki/Fibonacci_number#Limit_of_co
| ns...
| dbt00 wrote:
| I think the point was that the physical representation of
| the RHS looks like it's a golden ratio bigger than the LHS.
| autokad wrote:
| there's a closed form solution: ((golden ratio)* * N - (1 /
| golden ratio)* * N) / * *.5
| Jtsummers wrote:
| Finally realized what was missing: n
| n ph - (1/ph) F(n) = -----------
| [?]5
|
| There's a missing 5 in your presentation of the equation.
| spekcular wrote:
| As the author admits at the end, nothing is gained by introducing
| category-theoretic language here.
|
| 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.
| ABeeSea wrote:
| Most of the article is about semi-lattices and posets which are
| often most usefully described in a categorical framework.
| Fibonacci sequence is just a toy example to demonstrate the
| general concept. I have a ton of graduate level math books that
| torture a toy example to death because they're concrete.
| agumonkey wrote:
| Do you know good articles about semi-lattices ?
___________________________________________________________________
(page generated 2021-11-30 23:01 UTC)