FibonacciNumbers

The Fibonacci numbers $0, 1, 1, 2, 3, 5, …$ as a lazy indexed collection.

WikipediaFibonacci sequence↗WikidataQ23835349↗OEISA000045↗Wolfram LanguageFibonacci↗SageMathsage.combinat.combinat.fibonacci(n)↗mathlib4Nat.fib↗

FibonacciNumbers$F_n = F_{n-1} + F_{n-2}$, $F_0 = 0$, $F_1 = 1$, an infinite indexed collection.

Domain: Collections

Details

• A lazy indexed collection: $Count(FibonacciNumbers) = +\infty$, and $At(FibonacciNumbers, k)$ unranks the term via a memoised linear recurrence -- $At(FibonacciNumbers, 1) = F_0 = 0$ (At is 1-indexed; rank 0 is $F_0$).
• The collection is indexed from 1, so $At(FibonacciNumbers, k) = Fibonacci(k - 1)$: $At(FibonacciNumbers, 11) = Fibonacci(10) = 55$. The function $Fibonacci(n)$ is also defined at negative $n$ (negafibonacci, $F_{-n} = (-1)^{n+1} F_n$; $Fibonacci(-5) = 5$), which the collection, starting at $F_0$, does not reach.
• OEIS A000045, starting exactly at its offset-0 term: $0, 1, 1, 2, 3, 5, 8, …$.
• Membership goes through Element: $Element(21, FibonacciNumbers)$ is true, $Element(10, FibonacciNumbers)$ is false. $F_1 = F_2 = 1$ repeats, so the sequence is non-decreasing rather than strictly increasing.

Definition

Epsil, as the implementation runs it.

count()

PositiveInfinity

unrank(_r)

Fold(
      Function([wk_w[2], wk_w[1] + wk_w[2]], wk_w, wk_n),
      [0, 1],
      Range(0, _r - 1, 1),
    )[1]

rank(_x)

Fold(
      Function(
                wk_w if wk_n >= 0 && wk_w[1] > _x else [
                                                         wk_w[2],
                                                         wk_w[1] + wk_w[2],
                                                         wk_n if wk_w[3] < 0 &&
                                                                 wk_w[1] == _x else wk_w[3],
                                                       ],
                wk_w,
                wk_n,
              ),
      [0, 1, -1],
      Range(
             0,
             2 * (Apply(
                         (fl_r: list<integer>) => fl_r[2],
                         Fold(Function(
                                        [
                                          (fl_s[1] - fl_s[1] % 2 ^ fl_k) / 2 ^
                                                                           fl_k,
                                          fl_s[2] + fl_k,
                                        ] if fl_s[1] >= 2 ^ fl_k else fl_s,
                                        fl_s,
                                        fl_k,
                                      ), [_x + 2, 0], [
                                                       8_192,
                                                       4_096,
                                                       2_048,
                                                       1_024,
                                                       512,
                                                       256,
                                                       128,
                                                       64,
                                                       32,
                                                       16,
                                                       8,
                                                       4,
                                                       2,
                                                       1,
                                                     ]),
                       ) + 1) + 12,
             1,
           ),
    )[3] if _x >= 0 else -1

valid(_x)

Fold(
      Function(
                wk_w if wk_n >= 0 && wk_w[1] > _x else [
                                                         wk_w[2],
                                                         wk_w[1] + wk_w[2],
                                                         wk_n if wk_w[3] < 0 &&
                                                                 wk_w[1] == _x else wk_w[3],
                                                       ],
                wk_w,
                wk_n,
              ),
      [0, 1, -1],
      Range(
             0,
             2 * (Apply(
                         (fl_r: list<integer>) => fl_r[2],
                         Fold(Function(
                                        [
                                          (fl_s[1] - fl_s[1] % 2 ^ fl_k) / 2 ^
                                                                           fl_k,
                                          fl_s[2] + fl_k,
                                        ] if fl_s[1] >= 2 ^ fl_k else fl_s,
                                        fl_s,
                                        fl_k,
                                      ), [_x + 2, 0], [
                                                       8_192,
                                                       4_096,
                                                       2_048,
                                                       1_024,
                                                       512,
                                                       256,
                                                       128,
                                                       64,
                                                       32,
                                                       16,
                                                       8,
                                                       4,
                                                       2,
                                                       1,
                                                     ]),
                       ) + 1) + 12,
             1,
           ),
    )[3] >= 0 if _x >= 0 else False

Enumeration

Examples

1 more kept as data, checked against the oracles

Basic #

live ↗

In$\mathrm{FibonacciNumbers}[11]$Out$55$

Scope #

live ↗

In$\mathrm{FibonacciNumbers}[1]$Out$0$

Properties #

live ↗

In$21∈\mathrm{FibonacciNumbers}$Out$\mathrm{True}$

live ↗

In$10∈\mathrm{FibonacciNumbers}$Out$\mathrm{False}$

live ↗

In$\mathrm{Count}(\mathrm{FibonacciNumbers})$Out$∞$

About

Examples	6
Crosswalk	WikipediaWikidataOEISWolfram LanguageSageMathmathlib4

See also: Count, At, Element, LucasNumbers, PellNumbers, TribonacciNumbers