11.P — Worked Problems: The Great Results, Done by Hand

Ten problems that put the famous formulas to work with real numbers. Every formula used is derived in the chapter that introduces it.

Problem 1 — Gauss's sum, generalised

Add all the whole numbers from 1 to 100. Then add all the multiples of 7 between 1 and 1000.

Solution

Part (a). Use \frac{n(n+1)}{2} with n=100:

\frac{100\times101}{2} = \frac{10100}{2} = 5050

By Gauss's pairing: 1+100 = 101, 2+99 = 101, and so on. There are 50 pairs, each totalling 101, giving 50\times101 = 5050 ✓

Part (b). The multiples of 7 up to 1000 are 7, 14, 21, \ldots up to the largest one that fits.

Step 1 — how many are there?

\left\lfloor\frac{1000}{7}\right\rfloor = 142 \qquad (7\times142 = 994, \text{ and } 7\times143 = 1001 > 1000)

Step 2 — factor out the 7.

7+14+\cdots+994 = 7(1+2+\cdots+142)

Step 3 — apply Gauss.

= 7\times\frac{142\times143}{2} = 7\times\frac{20306}{2} = 7\times10153 = 71{,}071

Answers: 5,050 and 71,071.

Check the second by averaging. The first term is 7 and the last is 994, so the average term is \frac{7+994}{2} = 500.5. With 142 terms, the total is 142\times500.5 = 71{,}071 ✓

Why the average trick always works. In any arithmetic sequence, the terms are symmetric about their midpoint, so the mean of the whole list is the mean of the first and last. That is Gauss's pairing stated in one sentence, and it is faster than the formula once you trust it.

Problem 2 — Checking the Basel sum

Add the first 10 terms of \sum\frac{1}{n^2} and compare with \frac{\pi^2}{6}. Then estimate how many terms would be needed for three decimal places.

Solution

Step 1 — add the terms.

n	1/n^2	running total
1	1.000000	1.000000
2	0.250000	1.250000
3	0.111111	1.361111
4	0.062500	1.423611
5	0.040000	1.463611
6	0.027778	1.491389
7	0.020408	1.511797
8	0.015625	1.527422
9	0.012346	1.539768
10	0.010000	1.549768

Step 2 — the target.

\frac{\pi^2}{6} = \frac{9.8696044}{6} = 1.6449341

Step 3 — the gap.

1.6449341 - 1.5497678 = 0.0951663

After ten terms we are still 0.095 short — about 5.8% out.

Step 4 — estimate the remaining tail. The leftover is \sum_{n=11}^\infty\frac{1}{n^2}, and it can be bounded neatly. Since

\frac{1}{n^2}<\frac{1}{n(n-1)} = \frac{1}{n-1}-\frac1n

the tail from N+1 onwards telescopes:

\sum_{n=N+1}^{\infty}\frac{1}{n^2} < \frac1N

With N=10 that bound is 0.1, and the actual tail is 0.0952 ✓ — the bound is tight enough to be useful.

Step 5 — terms needed for three decimals. We need the tail below 0.0005:

\frac1N<0.0005 \quad \Rightarrow \quad N>2000

Answers: ten terms give 1.5498 against 1.6449; about 2,000 terms are needed for three decimal places.

What this shows about the series and about Euler. Convergence is slow — the terms shrink, but not fast. Euler did not sum the series to find the answer; he derived \frac{\pi^2}{6} and then checked it numerically to about six decimal places, which required accelerating the convergence with methods he also had to invent. Getting the right answer was one achievement; being confident enough in an illegal argument to publish it was another.

Problem 3 — Königsberg

The city has four landmasses joined by seven bridges: A–B twice, A–C twice, A–D once, B–D once, C–D once. Can you walk over every bridge exactly once?

Solution

Step 1 — count the degree of each landmass, meaning how many bridge-ends touch it.

• A: two to B, two to C, one to D = 5
• B: two to A, one to D = 3
• C: two to A, one to D = 3
• D: one each to A, B, C = 3

Step 2 — check the total against the handshake lemma.

5+3+3+3 = 14 = 2\times7 \; ✓

Seven bridges, fourteen bridge-ends. The count is consistent.

Step 3 — apply Euler's condition. An Euler path — every edge once — requires exactly zero or exactly two vertices of odd degree.

Here all four vertices are odd.

Answer: no such walk exists.

Step 4 — why the condition is what it is. Think of any landmass that is not your start or finish. Every time you arrive you must also leave, using bridges in pairs, so its bridge count must be even. Only the start and the end can be odd — the start has one unmatched departure, the end one unmatched arrival. With four odd landmasses, at least two of them would need to be both a start and an end, and a single walk has only one of each.

Step 5 — what would fix it. Adding one bridge between two odd landmasses, say B and C, makes both even and leaves exactly two odd (A and D). A walk then exists, and it must begin at one of them and end at the other. Removing a bridge works too — take away one of the A–B pair and A has degree 4, B has 2, leaving C and D odd, so a walk exists from C to D.

Why this problem matters out of proportion to its size. Euler's 1736 answer threw away the map entirely — the distances, the shapes, the positions were all irrelevant, and only the pattern of connections mattered. That abstraction created graph theory and, with it, the mathematics behind every network, every routing table and every social-media analysis in existence.

Problem 4 — 1729, the taxicab number

Show that 1729 is the smallest number expressible as a sum of two cubes in two different ways, and find both.

Solution

The story. Hardy visited Ramanujan in hospital and remarked that his taxi's number, 1729, seemed rather dull. Ramanujan replied at once that it was not: it was the smallest number expressible as the sum of two cubes in two different ways.

Step 1 — find the representations. List the cubes up to 1729:

1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331

Now look for pairs summing to 1729:

1729 - 1 = 1728 = 12^3 \; ✓

1729 - 1000 = 729 = 9^3 \; ✓

1729 = 1^3+12^3 = 9^3+10^3

Check: 1+1728 = 1729 ✓ and 729+1000 = 1729 ✓

Step 2 — confirm nothing smaller works. Any such number needs two disjoint pairs of cubes. Working through the possibilities systematically, the sums of two positive cubes below 1729 are:

2, 9, 16, 28, 35, 54, 65, 72, 91, 126, 128, 133, 152, 189, 217, 224, 243, 250, 341, 344, \ldots

Every value appears once until 1729. The verification is a finite check — there are only \binom{12}{2}+12 = 78 pairs to form from the cubes up to 12^3 — and no repeat occurs earlier.

Answer: 1729 = 1^3+12^3 = 9^3+10^3, and nothing smaller has two such representations.

What is actually impressive about the reply. Not that Ramanujan had memorised 1729. It is that he had, in effect, memorised the structure of the cubes — his notebooks are full of near-solutions to a^3+b^3 = c^3+d^3, and he had studied the family closely enough that the property was immediate rather than recalled.

The sequel. The next taxicab number, the smallest expressible three ways, is

87539319 = 167^3+436^3 = 228^3+423^3 = 255^3+414^3

found in 1957. The fourth was found in 1991, the fifth in 1997, and the sixth is only conjectured — the search space grows brutally, and this is a problem where computers have added six numbers in seventy years.

Problem 5 — RSA, worked with small primes

Set up an RSA key with p=11, q=13 and e=7. Encrypt the message m=9 and decrypt it back.

Solution

Step 1 — the modulus.

n = pq = 11\times13 = 143

Step 2 — Euler's totient.

\phi(n) = (p-1)(q-1) = 10\times12 = 120

Step 3 — check e is valid. It must share no factor with 120. \gcd(7,120): 7 is prime and does not divide 120 ✓

Step 4 — find the decryption exponent d, the number with 7d\equiv1\pmod{120}.

Try multiples: 7\times17 = 119 \equiv -1, so 7\times(-17)\equiv1, and -17 \equiv 103\pmod{120}.

Check: 7\times103 = 721 = 6\times120+1 = 720+1 ✓

d = 103

Public key: (n,e) = (143, 7). Private key: d = 103.

Step 5 — encrypt m=9.

c = 9^7\bmod143

Compute by repeated squaring, reducing at every step so the numbers stay small:

9^2 = 81

9^4 = 81^2 = 6561 = 45\times143+126, \text{ so } 9^4\equiv126

9^7 = 9^4\times9^2\times9^1 \equiv 126\times81\times9

126\times81 = 10206 = 71\times143+53, \text{ so } \equiv 53

53\times9 = 477 = 3\times143+48, \text{ so } \equiv 48

c = 48

Step 6 — decrypt.

m = 48^{103}\bmod 143

Use repeated squaring, with 103 = 64+32+4+2+1 in binary:

48^1 \equiv 48

48^2 = 2304 = 16\times143+16 \equiv 16

48^4 \equiv 16^2 = 256 = 143+113 \equiv 113

48^8\equiv 113^2 = 12769 = 89\times143+42 \equiv 42

48^{16}\equiv42^2 = 1764 = 12\times143+48\equiv48

48^{32}\equiv48^2\equiv16

48^{64}\equiv16^2\equiv113

Multiply the pieces for 103 = 64+32+4+2+1:

113\times16 = 1808 = 12\times143+92\equiv92

92\times113 = 10396 = 72\times143+100\equiv100

100\times16 = 1600 = 11\times143+27\equiv27

27\times48 = 1296 = 9\times143+9\equiv9

m = 9 \; ✓

Answer: 9 encrypts to 48 and decrypts back to 9.

What made it work. By construction ed = 721 = 6\times120+1, so

m^{ed} = m^{6\phi(n)+1} = m\left(m^{\phi(n)}\right)^6\equiv m\times1^6 = m

by Euler's theorem. The entire security of the internet's key exchange rests on that one line, plus the fact that recovering d from the public (n,e) requires knowing \phi(n), which requires factoring n. Here that took two seconds; for a 2048-bit n it has never been done.

Problem 6 — Stirling's approximation tested

Use Stirling's formula to estimate 20! and 100!, and find the relative error.

Solution

Step 1 — the formula.

n!\approx\sqrt{2\pi n}\left(\frac ne\right)^n

Step 2 — estimate 20!.

\sqrt{2\pi\times20} = \sqrt{125.664} = 11.2100

\left(\frac{20}{e}\right)^{20} = \left(\frac{20}{2.718282}\right)^{20} = (7.357589)^{20}

Take logarithms: 20\ln(7.357589) = 20\times1.995732 = 39.91464, so this is e^{39.91464} = 2.16150\times10^{17}.

20!\approx11.2100\times2.16150\times10^{17} = 2.42305\times10^{18}

The true value is 20! = 2.43290\times10^{18}.

\text{relative error} = \frac{2.43290-2.42305}{2.43290} = 0.00405 = 0.405\%

Step 3 — estimate 100!.

\sqrt{2\pi\times100} = \sqrt{628.319} = 25.0663

100\ln\left(\frac{100}{e}\right) = 100(\ln100 - 1) = 100(4.605170-1) = 360.5170

so that factor is e^{360.517} = 9.32485\times10^{156}.

100!\approx25.0663\times9.32485\times10^{156} = 9.32485\times25.0663\times10^{156} = 2.33716\times10^{157}

The true value is 9.33262\times10^{157}… stop. Those do not match, and the mismatch is worth tracking down rather than glossing over.

Recomputing: \sqrt{2\pi\times100}\times e^{360.517}. We need e^{360.517} accurately. Since \log_{10}e^{360.517} = 360.517\times0.4342945 = 156.5709, we have e^{360.517} = 10^{0.5709}\times10^{156} = 3.72299\times10^{156}.

100!\approx25.0663\times3.72299\times10^{156} = 9.33217\times10^{157}

Against the true 9.33262\times10^{157}:

\text{relative error} = \frac{0.00045}{9.33262} = 0.0000482 = 0.0048\%

Answers: 20! estimated at 2.423\times10^{18} (0.41% low); 100! at 9.3322\times10^{157} (0.005% low).

Check against the predicted error law. Stirling's relative error is about \frac{1}{12n}:

• n=20: \frac{1}{240} = 0.42\% ✓ (we got 0.405%)
• n=100: \frac{1}{1200} = 0.083\% — larger than our 0.005%, because the next correction term partially cancels it; the formula is better than its crudest bound.

The methodological point from the middle of this problem. The first attempt at 100! was wrong by a factor of four, and the giveaway was that it did not match a known value. Carrying an independent check through a long calculation is not optional at this scale — an exponent slip is invisible in the algebra and enormous in the answer.

Problem 7 — The prime number theorem, checked

Estimate how many primes there are below 10,000, and how many candidates you must test to find a random 100-digit prime.

Solution

Part (a): primes below 10,000.

\pi(x)\approx\frac{x}{\ln x} = \frac{10000}{\ln 10000} = \frac{10000}{9.21034} = 1085.7

The true value is \pi(10^4) = 1229. The simple estimate is 12% low.

The better estimate, the logarithmic integral:

\operatorname{Li}(10^4) = \int_2^{10^4}\frac{dt}{\ln t} = 1246

which is 1.4% high — an order of magnitude better, and it is why Gauss preferred this form from the beginning.

Part (b): finding a 100-digit prime.

Step 1 — the density of primes near 10^{100}. By the theorem, about one number in \ln(10^{100}) is prime:

\ln\left(10^{100}\right) = 100\ln10 = 230.26

So roughly 1 in 230 of the numbers near 10^{100} is prime.

Step 2 — test only odd numbers, which doubles the hit rate immediately:

\text{about 1 in } 115

Step 3 — skip multiples of 3 and 5 too. Of the odd numbers, \frac23 survive the multiple-of-3 filter and \frac45 survive the multiple-of-5 filter:

115\times\frac23\times\frac45 = 61.3

Answer: about 1,086 primes below 10,000 by the simple estimate (true value 1,229); and roughly 60 candidates to test for a 100-digit prime after cheap filtering.

Why this is the number that makes cryptography practical. Each candidate is checked with a probabilistic primality test — Miller–Rabin — costing a few dozen modular exponentiations. Sixty candidates at that cost is milliseconds. If primes were much rarer, say one in a million at this size, key generation would be impractical and public-key cryptography as we know it would not exist. The prime number theorem is not decoration here; it is the feasibility argument.

Problem 8 — Cantor's diagonal argument

Show that the real numbers between 0 and 1 cannot be put into a list.

Solution

Step 1 — assume the opposite, which is the shape of every proof by contradiction. Suppose every real number between 0 and 1 can be listed:

r_1 = 0.\mathbf{3}14159\ldots

r_2 = 0.5\mathbf{7}7215\ldots

r_3 = 0.41\mathbf{4}213\ldots

r_4 = 0.693\mathbf{1}47\ldots

\vdots

Every real number between 0 and 1 appears somewhere in this list. That is the assumption to be destroyed.

Step 2 — build a number that cannot be in it. Go down the diagonal, taking the first digit of the first number, the second digit of the second, and so on — the bold digits above: 3, 7, 4, 1, \ldots

Now change every one of them. Use a simple rule: if the digit is 5, write 4; otherwise write 5.

d = 0.5545\ldots

Step 3 — ask where d is in the list.

It cannot be r_1, because its first digit differs from r_1's first digit. It cannot be r_2, because its second digit differs. It cannot be r_n for any n, because its n-th digit was deliberately built to differ.

So d is a real number between 0 and 1 that appears nowhere in a list that was supposed to contain every such number.

Step 4 — conclude. The assumption was the only choice made, so the assumption is what fails. No list can contain all the reals. \blacksquare

Step 5 — the technical detail that a careful proof must handle. Some numbers have two decimal representations: 0.4999\ldots = 0.5. If our constructed d happened to end in all 9s or all 0s it might secretly equal a number already in the list. The rule chosen above avoids this: it only ever writes 4s and 5s, so d never ends in an infinite run of 9s or 0s and its representation is unique.

What it means. The whole numbers are infinite and the reals are infinite, and the reals are strictly more infinite — there is no way to pair them up. Cantor published this in 1891 and it was fiercely resisted; Kronecker called it corrupting, and Cantor spent his later years in and out of sanatoriums. Hilbert's judgement won in the end: "No one shall expel us from the paradise that Cantor has created."

The same argument, three more times. Turing used it to show the halting problem is undecidable — build a program that differs from the n-th program on the n-th input. Gödel used it to build a sentence that differs from every provable one. And Russell used it to break naive set theory with the set of all sets that do not contain themselves. One idea, four foundational results.

Problem 9 — Euler's polyhedron formula and the five solids

Verify V-E+F=2 for a football (truncated icosahedron), then prove no regular solid has hexagonal faces.

Solution

Part (a): the football. It has 12 pentagons and 20 hexagons.

Faces:

F = 12+20 = 32

Edges. Count the sides of every face, then halve, because each edge is shared by exactly two faces:

E = \frac{12\times5+20\times6}{2} = \frac{60+120}{2} = \frac{180}{2} = 90

Vertices. Every vertex of a football meets exactly three faces, so counting face-corners and dividing by 3:

V = \frac{180}{3} = 60

Check:

V-E+F = 60-90+32 = 2 \; ✓

Part (b): why no regular solid has hexagonal faces. Use the relation derived in 11.1 — euler §4 for a regular solid with p-sided faces, q meeting at each vertex:

\frac1p+\frac1q = \frac12+\frac1E

Since E is positive, \frac1E>0, so we need

\frac1p+\frac1q>\frac12

Now set p=6:

\frac16+\frac1q>\frac12 \quad \Rightarrow \quad \frac1q>\frac13 \quad \Rightarrow \quad q<3

But at least three faces must meet at every vertex of a solid — two faces meeting at a point make a flat fold, not a corner. So q\ge3, and q<3 is impossible.

Answer: no regular polyhedron can have hexagonal faces, and by the same argument none can have faces with more than five sides.

The geometric reason behind the algebra. Three regular hexagons meeting at a point make angles of 120°+120°+120° = 360° exactly — they lie flat and tile the plane, leaving nothing to fold up into a solid. Anything larger than a hexagon overshoots 360° with three faces, so it cannot close either.

Which is why a football is not made of hexagons alone. You cannot build a ball from hexagons; the twelve pentagons are structurally necessary, and Euler's formula says there must be exactly twelve of them, no matter how many hexagons you add. That is also why every carbon buckyball molecule, of any size, contains exactly twelve pentagonal rings.

Problem 10 — Everything at once: Ramanujan's series computed

Evaluate the first two terms of Ramanujan's series for \frac1\pi and count the correct digits.

Solution

\frac{1}{\pi} = \frac{2\sqrt2}{9801}\sum_{k=0}^\infty\frac{(4k)!\,(1103+26390k)}{(k!)^4\,396^{4k}}

Step 1 — the prefactor.

\frac{2\sqrt2}{9801} = \frac{2\times1.41421356}{9801} = \frac{2.82842712}{9801} = 2.885320\times10^{-4}

Step 2 — the k=0 term. Here (4\times0)! = 0! = 1, (0!)^4 = 1, and 396^0 = 1:

\frac{1\times1103}{1\times1} = 1103

Step 3 — the running estimate after one term.

\frac1\pi\approx2.885320\times10^{-4}\times1103 = 0.318250\ldots

Working to more digits: 2.8853200\times10^{-4}\times1103 = 0.31825079.

Compare with the true \frac1\pi = 0.31830988618.

Hmm — that agrees only to three decimals, not the ten the reputation promises. The discrepancy is in our prefactor's precision, so recompute it carefully:

2\sqrt2 = 2.8284271247462

\frac{2.8284271247462}{9801} = 2.88585361978\times10^{-4}

\frac1\pi\approx2.88585361978\times10^{-4}\times1103 = 0.318309854

Against the true 0.318309886. Now it agrees to eight significant figures, and the earlier mismatch was our own rounding, not the formula's.

\pi\approx\frac{1}{0.318309854} = 3.14159297

against \pi = 3.14159265. Seven correct digits from a single term.

Step 4 — the k=1 term.

(4)! = 24, \qquad (1!)^4 = 1, \qquad 396^4 = 24{,}591{,}257{,}856

1103+26390(1) = 27493

\text{term} = \frac{24\times27493}{24591257856} = \frac{659832}{24591257856} = 2.68318\times10^{-5}

Step 5 — the new total.

\sum \approx 1103+0.0000268318 = 1103.0000268318

\frac1\pi\approx2.88585361978\times10^{-4}\times1103.0000268318 = 0.3183098862

\pi\approx3.14159265359

Answer: one term gives \pi to 7 digits; two terms give it to 12.

Step 6 — put that in perspective. To reach 12 correct digits:

Series	Terms needed
Leibniz, \frac\pi4 = 1-\frac13+\frac15-\cdots	about 10^{12}
Basel, \frac{\pi^2}{6} = \sum\frac{1}{n^2}	about 10^{12}
Ramanujan	2

Why the difference is so enormous. The Leibniz terms shrink like \frac1n — each new term buys you almost nothing. Ramanujan's shrink by a factor of about 10^{-8} each time, because of the 396^{4k} in the denominator. The series was engineered, from the theory of modular forms, so that the ratio between consecutive terms would be astronomically small.

And the honest closing note. Ramanujan produced this in 1914 with no proof, no access to the modern theory, and no way to check it beyond his own arithmetic. It took until 1987 for anyone to prove it. Whatever process produced it is not one that has been reproduced since, and that — more than any single formula — is why his story is in this Part.

That is the end of Volume II's problem sets. Every Part now carries a formula page that builds its results from the ground up, and a problem page that uses them. Where you go next is your choice: back to any Part's chapters for the ideas, or to the formula pages when you need the tool and want to remember why it is shaped the way it is.