Concept

Fibonacci numbers

The sequence 1, 1, 2, 3, 5, 8, 13, in which each term is the sum of the two before. Their ratios approach the golden ratio, and reduced modulo any whole number they repeat with a period called the Pisano period.

Named by 11 essays across 5 fields — each of them below, with the objects they name alongside it.

Writing 0.3 in base φ. The graph of x ↦ βx mod 1 for the golden ratio φ, the diagonal, and the cobweb staircase of the orbit of 0.3, beside the 8 digits it writes.

Counting in a base that is not a whole number

Multiply by β and keep the fractional part, over and over, and the whole parts you throw away are the digits of the starting number in base β — even when β is the golden ratio. Which digit strings can ever appear is decided by one string alone: the way the number 1 is written in that base. In base φ it is .11, so 11 is the only thing forbidden; in base 1.8 it never ends, and no finite list of rules describes what is allowed.

dynamics · Symbolic dynamics

Five random Fibonacci sequences growing at one rate. Five jagged lines of log|tₖ| rising with k to a thousand, around a straight line of slope log 1.132, beneath a steeper dashed line of slope log 1.618.

A growth rate no step contains

Start with 1, 1 and at every step either add the last two numbers or subtract them, choosing by a coin. The sequence wanders, shrinks, even returns near zero — and grows, almost surely, like 1.13198824 to the power of the step. That number is a Lyapunov exponent of a product of random matrices, and it cannot be found by averaging anything about a single step: the two steps do not commute, and the rate depends on which way the vector is pointing when each one is applied.

dynamics · Sensitive dependence $Base-φ digits of two fractions and two irrational numbers. Four rows of 72 base-φ digits each, for 1/3, 2/7, √2 − 1 and 1/π; the two fractions repeat with periods 8 and 16, the two irrational numbers show no period.$

Fractions repeat and roots look random

Almost every number between 0 and 1 has base-φ digits with the frequencies Parry's measure predicts. Which particular numbers do? Every fraction, provably, does not: its expansion repeats from the first digit, with a period equal to the period of the Fibonacci numbers modulo its denominator. And √2 − 1 and 1/π, computed exactly to twelve thousand digits, match every predicted frequency to within sampling error — which proves nothing about them at all.

dynamics · Symbolic dynamics

Where 3003 appears eight times. 3003 = C(3003,1) = C(78,2) = C(15,5) = C(14,6) and their mirror images; N(3003) = 8.

How often a number can appear in Pascal's triangle

Every number bigger than one appears in Pascal's triangle at least twice, next to the 1 at each end of its own row. A few appear more often: 120 appears six times, and 3003 eight — as C(3003, 1), C(78, 2), C(15, 5) and C(14, 6), each twice. Counting every entry up to a million million finds seven numbers that appear more than four times and none that appear five, seven or more than eight. Whether any number appears ten times, or whether there is any limit at all, is unknown.

discrete · Pascals triangle

Scrambled in three steps, restored in thirty. Cat map on 61×61: period 30; frames at steps 0, 1, 2, 3, 7, 22, 30; lit pixels 693.

A chaotic map that always comes back

Arnold's cat map stretches a square by the golden ratio squared and wraps it round, and any two nearby points fly apart: a difference of a million-millionth fills the square in twenty-seven steps. Apply the same map to a picture made of pixels and it dissolves into noise within a few steps — and then, after exactly thirty steps on a 61 × 61 grid, every pixel is back where it started. Chaos and exact return are both true, and the Fibonacci numbers decide how long the return takes.

dynamics · Sensitive dependence

Two constants at the flat point

Turn up the circle map until its graph goes flat at one point, then hunt for the setting at which an orbit turns by the golden ratio. The settings that lock to 1/2, 2/3, 3/5, 5/8 close in on it, each gap 2.8336 times smaller than the last, and the orbit's returns to its start close in by 1.2886 at every step. Below the flat line the same two numbers are the golden ratio's own. Change the map to a different one with the same kind of flat point and both numbers come back unchanged: they belong to flatness, not to the sine.

dynamics · Mode locking

Rounding to the nearest saves three steps in ten. N=10^2: 3.981 / 3.155; N=10^3: 5.893 / 4.483; N=10^4: 7.826 / 5.832; N=10^5: 9.772 / 7.182; N=10^6: 11.702 / 8.520; N=10^7: 13.654 / 9.874; N=10^8: 15.587 / 11.214

Rounding to the nearest remainder

Euclid's algorithm divides and keeps the remainder, and the remainder it keeps is the one left after rounding the quotient down. Rounding to the nearest instead — allowing a remainder to be taken from above — never takes more steps, and Kronecker proved that no mixture of rounding up and down does better. On average it saves three steps in ten, the ratio of the logarithms of the golden ratio and of two. And its slowest inputs are not Fibonacci numbers but Pell numbers, because the worst case of each algorithm is the number its own kind of continued fraction expands most slowly: the golden ratio for one, the square root of two for the other.

geometry · Euclidean algorithm

Where the secant method goes, from every starting pair. x^3−x, 180×180 on [−2,2]²: to −1 10164, to 0 11954, to 1 10164, none 118.

Newton's method without a derivative

Replace Newton's tangent by the chord through the last two guesses and the method no longer needs a derivative — but it needs two starting values, so its basins live in a plane of pairs instead of on a line. The errors multiply instead of squaring, their logarithms add like Fibonacci numbers, and the digits gained grow by the golden ratio: 1, 3, 5, 9, 15, 25, 41, 67, 109.

dynamics · Newton basins

A bracket that shrinks by the golden ratio. 2: [0.00000, 1.00000]; 3: [0.00000, 0.61803]; 4: [0.23607, 0.61803]; 5: [0.23607, 0.47214]; 6: [0.32624, 0.47214]; 7: [0.32624, 0.41641]; 8: [0.36068, 0.41641]; 9: [0.36068, 0.39512]; peak 0.374750.

The search that reuses a point

To find the peak of a function that rises and then falls, evaluate it at two points and throw away the part beyond the lower one. Place the points so that the survivor can be used again, and there is exactly one way to do it: at the golden ratio. Each new evaluation then shrinks the bracket to 0.618 of its width, and with a fixed number of evaluations nothing does better than Fibonacci's numbers.

geometry · Golden ratio

Amounts arranged by remainder. Payable and unpayable amounts for coins 5 and 7, in columns modulo 5: largest unpayable 23, 12 unpayable amounts.

The largest amount two coins cannot pay

With coins of 5 and 7, the amounts 1, 2, 3, 4, 6, 8, 9, 11, 13, 16, 18 and 23 cannot be paid, and everything else can. Two lines of argument give the formula ab − a − b for the last gap, and half the rest of the board is gaps. For three coins no such formula exists, in a sense that can be proved. And the sets that coins can make have a count that climbs at the golden ratio, a conjecture settled from a table of 67, 118, 204.

number · Euclidean algorithm

Every prime's Fibonacci period lies on one of two lines or below. The period of the Fibonacci numbers modulo each prime p up to 1,000: for p ≡ ±1 mod 5 it divides p − 1, for p ≡ ±2 mod 5 it divides 2(p + 1); 116 of the 165 primes from 7 to 997 lie on their line.

The period the golden ratio sets

The Fibonacci numbers, taken modulo any whole number, eventually repeat — the last digits every sixty terms. At a prime the period is not arbitrary: it divides p − 1 when the prime ends in 1 or 9, and 2(p + 1) when it ends in 3 or 7. The reason is where the golden ratio lives. Modulo the first kind of prime it is an ordinary remainder; modulo the second it has to be adjoined, as √5 is adjoined to the rationals, and in that larger field the p-th power swaps φ with its conjugate.

algebra · Field extensions

Named alongside it

The objects these essays reach for when they reach for this one.

Golden ratio Euclidean algorithm Exhaustive search Lyapunov exponent Sensitive dependence Basin of attraction Beta expansion Binomial coefficient Circle map Congruence Conjecture Continued fractions

All concepts