The Book of Numbers, Conway

A book about numbers. It really is about numbers

Chapter 1, “The Romance of Numbers”

Covers how numbers have influenced our language by, among other things, listing almost every word whose roots trace back to some number less than one hundred (e.g. “Sistine” in “Sistine Chapel” comes from the fact that the Pope who oversaw its construction was Pope Sixtus IV, who was the sixth successor of St. Peter). Also covers how to name numbers bigger than a trillion and various different writing systems for numbers throughout history.

Chapter 2, “Figures from Figures: Doing Arithmetic and Algebra by Geometry”

Casting out nines

To cast out nines from a number, just add its digits, subtracting 9 whenever you can. To check your additions, subtractions, and multiplications, repeatedly cast out nines: they should remain valid. For example, we get five by casting out nines from each of 239 and 4649, so for their product we should obtain $5 \times 5 = 25 = 2 + 5 = 7$, agreeing with $239 \times 4649 = 1111111 \equiv 7$.

Square numbers

There’s a neat geometrical proof that the squares are always congruent to $0$, $1$ or $4$ modulo $5$.

Triangular numbers

Useful mnemonic for sums of arithmetic progressions, sequences of $n$ equally spaced numbers

\[a, b, c, \ldots, x, y, z\]

The sum of $n$ equally spaced numbers with first term $a$ and last term $z$ is $n$ times their average:

\[n \times \frac{a + z}{2}\]

Chapter 3, “What Comes Next?”

About other famous sequences of numbers like the sequence of factorials, and also covers a general method for finding an $n$-th term formula of any sequence.

Chapter 4, “Famous Families of Numbers”

Bernoulli numbers and Faulhaber’s formula

There’s a general formula for the sum of the $k$-th powers of successive integers using Bernoulli numbers:

\[1^{k-1} + 2^{k-1} + \cdots + n^{k-1} = \frac{(n+B)^k) - B^k}{k}\]

“Say, Bud, Where Do You Think You Are Going?”

An explanation of why the petals of sunflowers and the spirals on pineapples naturally create Fibonacci spirals.

Chapter 5, “The Primacy of Primes”

Fractions $\text{mod } p$

What is

\[\frac 1 8 \pmod{101}\]

? This is the same as finding a multiplicative inverse of $8$. One easy procedure is to repeatedly multiply $8$ by something that makes it smaller mod $p$:

$8 \times 13 \equiv 3 \pmod{101}$
$3 \times 34 \equiv 1 \pmod{101}$

So it follows that $1/8 \equiv 13 \times 34 \pmod{101}$.

Chapter 6, “Further Fruitfulness of Fractions”

Farey fractions

If you write down all fractions with denominators up to $m \in \mathbb N$, you get the “Farey series”:

\[\frac 0 1, \frac 1 6, \frac 1 5, \frac 1 4, \frac 1 3, \frac 2 5, \frac 1 2, \frac 3 5, \frac 2 3, \frac 3 4, \frac 4 5, \frac 5 6, \frac 1 1\]

These have the property (among others) that if $a/b$ and $c/d$ are next to each other in a sequence, then $ad$ and $bc$ are consecutive integers.

Euler’s totient numbers

For how many of the fractions

\[\frac 0 n, \frac 1 n, \frac 2 n, \cdots, \frac{n-1} n\]

is $n$ the least possible denominator? The answer is $\phi(n)$, the number of integers less than $n$ which are coprime to $n$. The $n$-th Farey series then has length $1 + \sum^n _ {i = 1} \phi(i)$ (consider all the fractions you could write down, and then crossing out the ones that simplify).

Fractions cycle into decimals

Crossover with [[Decimal Expansions]]^N and the source for [[Number theory at the card table]]^B.

It’s possible to work out exactly any $n/7$th exactly since:

$1/7 = 0.\overline{142857}$
$3/7 = 0.\overline{428571}$
$2/7 = 0.\overline{285714}$
$6/7 = 0.\overline{857142}$
$4/7 = 0.\overline{571428}$
$5/7 = 0.\overline{714285}$

(there, each number in the sequence $1,3,2,6,4,5$ shuffles the cycle $142857$ along one place). However, it is not always the case that it is just one cycle:

For thirteenths, there are two cycles.
For thirds, there are also two cycles.
For elevenths, there are five cycles.

Why do cycles happen? Consider the case of sevenths:

\[\frac 1 7 = 0.\overline{142857}\]

Multiplying by 10:

\[1.\overline{428571} = \frac{10}{7} = 1 +\frac 3 7 = 1+0.\overline{428571}\]

so $3/7 = 0.\overline{428571}$. Similarly, doing this for $100, 1000, 10000, …$ shows the rest of the cycle. So really this happens because $10 \equiv 3 \text{ mod } 7$, $100 \equiv 2 \text{ mod } 7$, and so on. For thirteenths, there are two cycles because the powers of ten repeat with period 6 mod 13.

So the length of the first cycle is the smallest number $l$ with $10^l \equiv 1 \text{ mod } p$.

All these cycles are the same length.

You can define a “long prime” (to base 10) as a prime $p$ in which the decimal expansion of $1/p$ has the largest possible cycle length, $p - 1$.

Repeated shuffling

Riffle shuffles start by cutting $2n$ cards into two half decks of $n$ cards each, one for the left hand and one for the right hand
The “in” riffle shuffle: left, right, left, right (starting from the bottom)
The “out” riffle shuffle: right, left, right, left
In the out riffle shuffle, the top and bottom cards stay in the same place
If the cards were originally numbered $1, 2, 3, 4, 5,6,7,8$, then performing the in riffle shuffle moves all cards to places $5,1,6,2,7,3,8,4$. Alternatively, the cards end up in the positions originally occupied by the numbers $2,4,6,8,1,3,5,7$. (Why?)
The general rule is that card $k$ ends in the place originally occupied by $2k \text{ mod } 2n+1$.
After $s$ shuffles, card $k$ ends up in the place originally occupied by $2^s k$, mod $2n+1$.
Hence $s$ shuffles restore the original order when $2^s \equiv 1, \text{ mod } 2n+1$.
There are 52 cards in a normal deck of cards (minus jokers). Since $53$ is a long prime in base 2 (in the sense defined above), this means 52 shuffles are required to restore the original order.
For the out shuffle, things are slightly different. Instead you can number the cards from $0$ instead and $s$ shuffles will restore the order just when $2^s \equiv 1$ mod $2n - 1$, so if you out-shuffle $2n$ cards $2n-2$ times, where $2n - 1$ is prime, the cards will come back to their original order.
For out shuffles, the general rule is that card $k$ (indexed from $0$) moves to position $2k$, mod $2n - 1$.
- One way to see this is to consider that the first $n$ cards are mapped to positions $2k$ under the shuffle. For $k > n$, card $k$ is also card $n + (k - n)$, i.e. $k - n$ cards away from the separation of the packs. Then to find its new position, it becomes $2(k - n) + 1 = 2k - 2n + 1 = 2k - (2n - 1)$, and so by taking mod $2n - 1$, this is just $2k$.
- Another way is to visualise as a number line. First double all the points, to convert something that stretches goes $0$ to $2n-1$ into something that stretches $0$ to $4n-2$. Then taking mod $2n-1$ shifts everything back into the original range.
So the card originally is position $k$ will be in position $4k \text{ mod } 2n - 1$ after 2 shuffles, and more generally, in position $2^s k \text{ mod } 2n-1$ after $s$ shuffles
How many shuffles in order to restore all cards to their original positions? In this case, we need the smallest $s$ such that $2^s = 1 \text{ mod } 2n - 1$.
Because $2^8 = 256$ is congruent to $1$ mod $51$, only 8 shuffles are required to restore an ordinary deck of 52 cards with the out shuffle.
This gives a fun connection between the number of out shuffles to restore a pack of cards to their original order and the decimal expansion of $1/51$ in base 2.
$1/51 = 0.\overline{00000101} _ 2$, and the fact it repeats with period 8 is exactly the fact that $2^8 \times 1/51 = 256/51 = 5 + 1/51$, and $5$ in binary is $101 _ 2$.
Could you use shuffling to calculate the binary expansions of fractions with odd denominator?
- Yes, and this is all done in parallel!
- Say you want to calculate all $x/7$. Prepare a deck of 8 cards, to split into 4 piles each. Label all the cards from $0$ to $7$. Also prepare a table of $0/7$ up to $7/7$. Write “$0.$” in each row.
- Then, write a $0$ in the expansion of all the cards in the top pile, and a $1$ in all the cards in the bottom pile. Repeatedly do out-shuffles and note down the $0$s or $1$s, this will end up producing the expansions for all the fractions simultaneously.