Fibonacci Generator

The Fibonacci sequence is a series where each number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144... Named after Leonardo of Pisa (Fibonacci), who introduced it to European mathematics in 1202 through his book Liber Abaci. The sequence appears in nature: the spiral arrangement of sunflower seeds, pinecone scales, leaf phyllotaxis, nautilus shells, and the branching of trees.

The golden ratio (φ ≈ 1.6180339887...) is the limit of F(n+1)/F(n) as n approaches infinity. The exact value is (1 + √5) / 2. Two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger quantity: (a+b)/a = a/b = φ. The golden ratio appears in Euclidean geometry, art, architecture (Parthenon), and has long fascinated mathematicians. It is also related to the regular pentagon and icosahedron.

The number of spirals in sunflowers, pinecones, and pineapples are consecutive Fibonacci numbers (typically 21 and 34, or 34 and 55). The number of petals on many flowers is a Fibonacci number (3, 5, 8, 13). Leaf arrangements on stems follow Fibonacci fractions to maximize sun exposure. The rabbit population model that Fibonacci used to introduce the sequence: if a pair of rabbits produces a new pair each month, starting from the second month, the population grows following the Fibonacci sequence.

Naive recursion: O(2^n) — exponential time. Memoized recursion or iteration: O(n). Matrix exponentiation: O(log n). Closed-form Binet formula: F(n) = (φ^n − ψ^n) / √5 where ψ = (1−√5)/2 — theoretically O(1) but loses precision for large n due to floating-point errors. For exact large Fibonacci numbers, use arbitrary-precision integer arithmetic (Python's int, Java's BigInteger). F(100) has 21 digits; F(1000) has 209 digits.

Fibonacci heaps (used in Dijkstra's algorithm), Fibonacci search (an alternative to binary search), pseudorandom number generators, Zeckendorf's theorem (every positive integer is uniquely representable as a sum of non-consecutive Fibonacci numbers), Fibonacci coding (universal code for integer compression), skip list random level generation, and analysis of worst-case inputs for certain algorithms like Euclid's GCD algorithm.