[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)