Numeric sequences

Leonardo is named after Leonardo Pisano, so the Fibonacci numbers had better work.

import it.grypho.scala.leonardo.core.*
import it.grypho.scala.leonardo.scalar.*

val env = new Environment()
val k   = _Variable("k")

Why “numeric” and not “integer”

A linear recurrence needs only addition and multiplication, so it is closed over whatever its seeds are. fib(5, 1.5, -pi) is as meaningful as fib(5), and with exact seeds the exact tier carries the result through unrounded. Restricting these to integers would be a choice with nothing to recommend it — hence numeric sequences.

The word series is deliberately avoided here: in this library it already means the analytic expansions (Taylor, Fourier, Laurent) described under Calculus.

Fibonacci and its relatives

_Sequence(SeqKind.Fibonacci, _Number(10.0)).eval(env)
// res0: Either[_Expression, _Value] = Right(_Number(55.0))

Indexing is the standard one — x(0) = 0, x(1) = 1, so fib(10) = 55, agreeing with OEIS A000045 and every published table. The “classic rabbit” pair is written explicitly as fib(n, 1, 1), which is this same sequence shifted by one: fib(n, 1, 1) = fib(n+1).

All four named sequences are one node over x(k) = p·x(k-1) + q·x(k-2), differing only in their seeds and coefficients — so each keeps its own name when printed or saved, while the recurrence has a single definition:

Function Sequence Seeds (a, b) (p, q) First terms
fib(n) Fibonacci (0, 1) (1, 1) 0, 1, 1, 2, 3, 5, 8
lucas(n) Lucas (2, 1) (1, 1) 2, 1, 3, 4, 7, 11
pell(n) Pell (0, 1) (2, 1) 0, 1, 2, 5, 12, 29
jacobsthal(n) Jacobsthal (0, 1) (1, 2) 0, 1, 1, 3, 5, 11

So lucas(n) and fib(n, 2, 1) are the same number by construction, and fib(n, a, b) covers any other pair of seeds you care to supply.

Exactness

A Double holds Fibonacci numbers exactly only up to F(78); F(79) = 14472334024676221 exceeds 253. In exact mode the computation runs over arbitrary-precision integers instead, so the answer is right rather than merely close:

exact on
fib(100)        -> 354224848179261915075

Binet’s formula φⁿ/√5 is deliberately not used: it is elegant, inexact, and drifts from the true value around n = 70.

Combinatorial functions

Function Meaning Reference
binom(n, k) binomial coefficient, generalised to a real upper index Binomial coefficient
catalan(n) binom(2n, n)/(n+1) Catalan number
harmonic(n) 1 + 1/2 + … + 1/n Harmonic number

harmonic is rational-valued, which makes it a natural showcase for the exact tier — harmonic(4) is 25/12, not 2.0833… — and it agrees with the digamma function already in the library by H(n) = ψ(n+1) + γ.

binom uses the falling factorial, so a real upper index works: binom(-1, 3) = -1.

tabulate — a row of terms

tabulate(e, k, lo, hi) evaluates e at each integer k in [lo, hi] and returns a 1×n matrix. It is not specific to the sequences: every function in the library gains a tabulated form from it.

_Tabulate(_Sequence(SeqKind.Fibonacci, k), k, _Number(0.0), _Number(10.0)).eval(env).toExpression.toString
// res1: String = "[[0.0, 1.0, 1.0, 2.0, 3.0, 5.0, 8.0, 13.0, 21.0, 34.0, 55.0]]"
tabulate(binom(4, k), k, 0, 4)   -> [[1, 4, 6, 4, 1]]     a Pascal row
tabulate(k^2, k, 1, 5)           -> [[1, 4, 9, 16, 25]]
at(tabulate(fib(k), k, 0, 10), 1, 11)  -> 55              rows are 1-based

The result is an ordinary matrix, so indexing with at, tuple assignment, the matrix operations and :save all work on it unchanged. k is a binder — it belongs to the tabulate and is never substituted from outside. The number of terms is capped at 1000, so a mistyped bound declines rather than building an unbounded row, and the REPL says so in a note (note: tabulate declined: 1001 terms exceed the limit of 1000) rather than echoing the call back silently.

sum and product — the terms folded

The same shape, folding the terms rather than listing them:

_Reduction(ReduceKind.Sum, Power(k, _Number(2.0)), k, _Number(1.0), _Number(4.0)).eval(env)
// res2: Either[_Expression, _Value] = Right(_Number(30.0))
sum(k, k, 1, 100)           -> 5050.0
product(k, k, 1, 5)         -> 120.0
sum(binom(4, k), k, 0, 4)   -> 16.0            a Pascal row, added up

Three things follow the library’s usual conventions rather than needing to be remembered separately. An exact term stays exact — under exact on, sum(1/k, k, 1, 3) is 11/6, not a decimal. Symbolic terms expand: sum(k*x, k, 1, 3) becomes x + 2x + 3x, which simplify then collects to 6x. And an empty range is the identity — sum(…, k, 1, 0) is 0 and the empty product is 1 — so a base case reads correctly instead of declining.

The same 1000-term cap applies, with the same note. Symbolic terms are held to a tighter bound: an expanded sum is as deep as it has terms, and the library accepts no expression deeper than 200 levels — the browser’s simplify cannot walk much past 250 — so sum(k*x, k, 1, 300) declines with note: sum declined: a symbolic sum of 300 terms would be deeper than the limit of 200, while the numeric sum(k, k, 1, 1000), which builds no such tree, still answers. A product that overflows is a different matter: product(k, k, 1, 171) answers inf, the floating-point arithmetic’s own answer (1e308 * 10 is inf too), while fact(171) declines, because the factorial kernel knows 171! is beyond a Double and says so rather than computing it. Under exact on both give the exact integer.


This site uses Just the Docs, a documentation theme for Jekyll.