Sequence Functions

This page documents library functions related to sequences.


Fibonacci

gfib( n )g_ ext{fib} left(, n , ight)

Generate the Fibonacci sequence up to its nn-th term.

Arguments

ArgumentDescriptionDomainConstraintsNotes
nnterms countZ\mathbb{Z}0<n0 < n

Return

ValueDescriptionCodomainConstraintsNotes
ω\omegaterms[N,...][\mathbb{N}, ...]Produces an empty list for invalid nn.

Instances

g_\text{fib}left(0\right)-left[\right]
g_\text{fib}left(1\right)-left[0\right]
g_\text{fib}left(2\right)-left[0, 1\right]
g_\text{fib}left(3\right)-left[0, 1, 1\right]
g_\text{fib}left(7\right)-left[0, 1, 1, 2, 3, 5, 8\right]
g_\text{fib}left(13\right)-left[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144\right]

Implementation

gfib(n)={ n≤0: [], n=1: [0], n=2: [0, 1], join⁡([0, 1], gfibo(1, n−2))  }gfibs(n, nmax)=join⁡([0, 1], gfibo(n+1, nmax))gfibo(n, nmax)={n>nmax: [], gfibs(n, nmax)+ftail(gfibs(n, nmax))}egin{align*} g_ ext{fib}left(n ight) &= { nle0: left[ ight], \ &quadquad n=1: left[0 ight], \ &quadquad n=2: left[0, 1 ight], \ &quadquad operatorname{join}left(left[0, 1 ight], g_ ext{fibo}left(1, n-2 ight) ight) \ &quad } \[1em] g_ ext{fibs}left(n, n_ ext{max} ight) &= operatorname{join}left(left[0, 1 ight], g_ ext{fibo}left(n+1, n_ ext{max} ight) ight) \ g_ ext{fibo}left(n, n_ ext{max} ight) &= left{n>n_ ext{max}: left[ ight], g_ ext{fibs}left(n, n_ ext{max} ight)+f_ ext{tail}left(g_ ext{fibs}left(n, n_ ext{max} ight) ight) ight} end{align*}

This uses a mutually recursive implementation with 2 helper functions. It could probably be optimised?

Dependencies

  • ftailf_\text{tail} (from Lists)