Intellect PlusDiscrete mathematics
148 cards. Each one is a 40-second story with a five-minute read behind it. Page 3 of 3.
A prime is any number of dots that refuses to form a rectangleLine up six dots and they fit neatly into two rows of three. Try the same with five or seven and nothing works except a single line. That is the essence of a prime: a whole number…
Primes thin out at a precise rate that a teenage Gauss first guessedAmong whole numbers up to 1000 digits long, roughly one in 2300 is prime; double the length to 2000 digits and the odds fall to about one in 4600. The prime number theorem pins do…
Nobody can say for certain who invented the truth tableThe truth table is among the most familiar tools in logic, yet its origin is murky. Ludwig Wittgenstein and Emil Post usually get credit for the grid layout, perhaps independently…
Jewish scribes invented error checking over a thousand years before computersBetween the seventh and tenth centuries, Jewish scribes counted every word and letter of the Hebrew Bible, even marking each book's middle verse, so copies could be checked. A sin…
Euclid's famous proof of infinite primes is not actually a proof by contradictionTextbooks often say Euclid assumed a largest prime and derived an absurdity. He did nothing of the sort. His argument in the Elements works directly on any finite list of primes, …
The language mathematicians use for foundations cannot pin down the ordinary counting numbersFirst-order logic became the standard language for writing mathematics as axioms by the 1940s. It is powerful enough that every statement true in all its models can be proved. Yet…
A notation for describing machines, drafted in 1907, anticipated programming languagesIn Vienna in 1907, Leonardo Torres Quevedo presented a system of symbols for describing machines. Heinz Zemanek later judged it equivalent to a programming language for controllin…- The reason 1 is not a prime number is a theorem about uniquenessEvery whole number above 1 breaks into primes in exactly one way, apart from the order. 1200 always contains four 2s, one 3 and two 5s. If 1 counted as prime, you could tack on as…
Arithmetic with addition alone is complete; add multiplication and Gödel's limits biteIn 1931 Kurt Gödel showed that any consistent, algorithmically listable set of axioms rich enough for ordinary arithmetic leaves some true statements unprovable, and cannot prove …
Handshakes and debts show the difference between two basic kinds of graphDraw dots for guests at a party and a line whenever two shake hands, and you have an undirected graph, since a handshake always goes both ways. Draw an arrow when one guest owes a…
Proving four colours suffice for any map took a century and a computerIn 1852 Francis Guthrie asked whether four colours are always enough to paint a map so that neighbouring regions differ. Mathematicians offered wrong proofs for over a hundred yea…
Why is approximately equal not a proper kind of sameness in mathematics?Nudge a number by a tiny amount, then again, then again, and each step looks almost equal to the last while the ends drift far apart. That failure of transitivity is exactly why m…
The mathematics of countable things grew up alongside the digital computerCalculus deals in smooth, unbroken change. Discrete mathematics deals in separate, countable things: whole numbers, networks, logical statements. It barely existed as a university…
The set with nothing in it has a Scandinavian symbol and odd powersThe familiar slashed-circle sign for the empty set was chosen in 1939 by André Weil of the Bourbaki group, borrowing the letter Ø from the Danish and Norwegian alphabets. That bor…
Class field theory: the century-long project that grew from Gauss's reciprocity lawDavid Hilbert usually gets credit for class fields, but Leopold Kronecker already knew the idea and Heinrich Weber coined the name before Hilbert's key papers appeared. What follo…
Why a scratched CD still plays: the mathematics of deliberate redundancyA music CD survives dust and scratches because its data is written twice over in a clever way. A Reed–Solomon code adds carefully chosen extra information, and the bits are shuffl…
Exactly 2,598,960 different poker hands, and how to count them fastDeal five cards from a standard 52-card deck and the odds of getting any one particular hand are 1 in 2,598,960. Nobody listed them all to find that out. The figure comes from a s…- An ancient Indian physician counted 63 ways to mix six tastesThe Sushruta Samhita, a classic of Indian medicine, notes that six basic tastes can be combined in 63 different ways, singly, in pairs, in threes and so on. That tally, every poss…
Almost every collection of numbers is beyond the reach of any computerThere are only countably many possible Turing machines, so only countably many sets of whole numbers can ever be computed. Cantor showed the sets of whole numbers themselves are u…- A function can be computable even if no real computer could ever finish itIn mathematical logic, computable does not mean practical. A function counts as computable if some finite set of instructions produces its answer eventually, with unlimited time a…
Complexity theory asks how hard a problem is for every possible algorithmAsking whether a tour of Germany's 14 biggest cities can be done in under 2,000 kilometres is one question. Asking how hard that kind of question is in general, no matter which me…
Predicting the next symbol well is the same skill as compressing dataA language model built for text, DeepMind's Chinchilla 70B, squeezed images to 43.4 percent and audio to 16.4 percent of their original size, beating the PNG and FLAC formats. Tha…
Rob Pike's rule: pick the right data layout and the algorithm writes itselfProgrammer Rob Pike has argued that how you arrange your data almost always matters more for speed than which algorithm you choose, because once the layout is right the method ten…- The imaginary computers that let programs run anywhereLong before Java promised write once, run anywhere, computer scientists in the late 1950s dreamed of a universal in-between language that every machine could understand. That drea…
The famous number theory book Dedekind wrote and credited to his teacherIn 1863 Richard Dedekind published Lectures on Number Theory under Peter Gustav Lejeune Dirichlet's name and called it Dirichlet's book for the rest of his life. Yet he wrote near…
A teenage Gauss scribbled the rule for primes in his logarithm tableAround 1792, aged 15 or 16, Carl Friedrich Gauss jotted a short note in his book of logarithms guessing how many primes lie below any large number. He never published it and only …
Mathematicians stopped asking whether axioms are true and started asking what followsFor Euclid, a starting assumption in geometry was a plain fact about the world, like the ability to draw a straight line between any two points. Modern mathematicians treat axioms…- You can tell two piles are equal without counting either oneLay out a heap of apples and a heap of oranges, then match them off one apple to one orange. If nothing is left over, the heaps are the same size, and you never needed a single nu…