Index

* (operator), mathematical convention for, 115

+ (plus sign), mathematical convention for, 115

α. See Aliquot sum

ϕ. See Euler totient function

σ (sum of divisors) formula, 31

A

Abelian group, 86, 108, 153

Abstract algebra

birth of, 85, 140–145

Euclidean domains, 150–151, 153

fields, 151–153

groups, 85–88, 92–95, 108, 152

ideals, 226–228

modules, 151, 154

monoids, 89, 108–109, 152, 154

and programming, 2, 141, 249

principal ideals, 227–228

rings, 142–145, 153

semigroups, 90–91, 108–109, 152

semirings, 145–149, 153

vector spaces, 152, 154

Abstraction

Aristotle, 177, 180, 196

in mathematics, 84, 85–109

and programming, 2, 5, 249

Academy (Plato’s), 41–44, 178

Addition

associativity of, 9, 156, 174

commutativity of, 155–156, 174–175

definition, 173

Addition chains, 11

Additive groups, 86

Additive monoids, 89, 109

Additive semigroups, 90, 109

Address, 181

Adleman, Len, 239

advance, 190

Agrawal, Manindra, 244

Ahmes, 8–9, 57

Ahmes algorithm. See Egyptian multiplication, Egyptian division

AKS primality test, 244–245

Alexander the Great, 43, 178–179

Alexandria, 43–44

Algebraic integers, 140

Algebraic structures, 85. See also Abstract algebra

Algorithms

in ancient Egypt, 7–11

definition, 7

domain or setting, 150

first recorded, 8

generalizing, 111, 119–123, 126–127, 151

history of, 7–11

in-place, 215–216

memory adaptive, 216–217

polylog space, 215–216

space complexity, 215–216

performance in practice, 211

Aliases, 272

Aliquot sum, 31

Amicable numbers, 63–64

Analytical Mechanics, 99

APL, 124

Apology, 43

Archimedes

on acquiring mathematical knowledge, 176

axiom of, 47

place in history, 50

Aristophanes, 42

Aristotle, 17, 177–180

Aristoxenus, 17

Arithmétique, 132

The Art of Computer Programming, 9

Aryabhata, 51

Aryabhatiya, 51

Assertions, 269

Associative binary operation (), 108

in groups, 85–86

in monoids, 89

in semigroups, 90

Associativity axiom, semigroups, 91

Associativity of addition, 9, 113

definition, 174

visual proof, 156

Associativity of multiplication, visual proof, 157

Asymmetric keys, 238

Athens, 41–43

Automorphism, 104

Averroes. See Ibn Rushd

Axiom of Archimedes, 47

Axiomatic method, 161–162

Axioms

definition, 163

Euclid’s, 162–163

Hilbert’s, 167

Peano’s, 170–171

B

Bachet de Méziriac, Claude Gaspar, 67, 235

profile, 225–226

Backus, John, 124

Bacon, Roger, 1, 249

Bartels, Martin, 165

Bernoulli, Johann, 69

Bézout’s identity, 225–229

Bidirectional iterators, 185

Binary search, 191–196. See also Partition points

Binary search lemma, 194–195

Bletchley Park, 238

Bolyai, Farkas, 166

Bolyai, János, 166

Bolzano-Cauchy Theorem. See IVT (Intermediate Value Theorem)

Boolean semirings, 148

Bounded ranges, 189, 203–204

bsearch, 192

C

C++, 3, 265–273

C++11, 57, 187, 195, 265, 272–273

The C++ Programming Language, 265, 270

C++ Standard Template Library. See STL

Caesar cipher, 237

Cancellation

Cancellation Law, 74–75

definition, 72–73

inverse numbers, 73

and modular arithmetic, 72–76

Self-Canceling Law, 75–76

Cancellation Law, 74–75

Carmichael numbers, 242

Cartesian coordinates, 131, 138

Cataldi, Peter, 64

Categorical theories

vs. STL, 104

definition, 104

examples of, 104–106

Category dispatch, 188, 190, 196, 213

Cayley’s Theorem, 198

Chinese mathematics, 51

Chrystal, George, 34

Cicero, 50

Ciphertext, 238

Closed ranges, 188

Clouds, 42

Cocks, Clifford, 240

Codes, definition, 237

Cogitata Physico Mathematica, 64

Colossus machine, 238

Common Lisp, 116, 124, 190

Common measure of segments, 33

Common notions, Euclid’s axiomatic method, 162

Commutative algebra, rings, 143–144

Commutativity of addition, 155–156, 174–175

Commutativity of multiplication, visual proof, 156

Commutativity of powers, semigroups, 91

Compile-time dispatch. See Category dispatch

Completeness, law of, 203–204

Completeness, theories, 102

Complex numbers, 137–138

Composite numbers. See also Prime numbers

definition, 21

distinguishing from prime, 240–245

Concepts

and abstract algebra, 141

definition, 181

choosing, 250

examples, 116–117, 181

naming conventions, 183

overview, 181–184, 266–267

Regular, 183–184

requirements on types, 24, 182

Semiregular, 184

type attributes, 182–183

type functions, 182–183

Consistency, theories, 102, 104

Constructivists, 229

Contradiction, proof by, 35, 261–262

Contrapositive, 259

Coprime, 31, 78, 80–81, 246–247

Cosets, 97. See also Lagrange’s Theorem

Counted ranges, 189, 203–204

Cryptanalysis, 237–238

Cryptography, 233–234, 237

Cryptology

asymmetric keys, 238

Bletchley Park, 238

Caesar cipher, 237

ciphertext, 238

codes, definition, 237

Colossus machine, 238

cryptanalysis, 237–238

cryptography, 237

cryptosystems, 238

Enigma machine, 238

keys, 238

Lorenz machine, 238

plaintext, 238

public-key cryptosystems, 239–240

RSA algorithm, 239–240, 245–247

symmetric keys, 238

trapdoor one-way functions, 239

Cryptosystems, 238

Cycles, of permutations, 200, 207–211

Cyclic groups, 96, 109

generator, 96

Cyclic subgroups, 96

D

Datum, 180

Decimal fractions, 129–131

Declaration syntax, 267

Dedekind, Richard, 140, 171

Degree of polynomials, 133

Dereferencing, iterators, 184–185

Descartes, René, 64, 131

Difference of powers formula, 30

Difference type, iterators, 187

difference_type iterator trait, 187

Differential Calculus, 70

Diffie, Whitfield, 239

Diophantus, 67, 225

Dirichlet, Peter Gustav Lejeune, 41, 139–140, 156

Dirichlet principle. See Pigeonhole principle

Disme: The Art of Tenths, 129–131

Disquisitiones Arithmeticae (“Investigations of Arithmetic”), 136–137

distance, 186-188

divides, 240

Dividing polynomials, 133

Domain of algorithm, 150

Domain of definition, 113

Doubly linked lists, 185

E

Egyptian division, 57

Egyptian multiplication, 8–11

requirements, 111–118

generalizing to power, 120

Elements (of Euclid), 2, 21, 43–45, 161–163

Proposition [VII, 30], 70

Proposition [VII, 32], 21

Proposition [IX, 36], 29, 31–32

Proposition [X, 2], 45

Proposition [X, 3], 45–46

Proposition [X, 117], 37

Elements of Programming, 3, 113–114, 183, 185, 208

Enigma machine, 238

Equational reasoning, 114

Equivalence, 114

Eratosthenes, 22

Euclid. See also Elements

the axiomatic method, 161–163

GCM (greatest common measure) algorithm, 45–49

incommensurable quantities, 45–49

on number theory, 21

profile, 44–45

Euclidean domains (ED), 150–151, 153

Euclidean geometry

alternatives to, 164–167

fifth postulate, 163–164

vs. hyperbolic geometry, 164–167

vs. non-Euclidean, 166–167

Euclidean rings. See Euclidean domains (ED)

Euclid’s algorithm, 45–47

Euler, Leonhard, 84, 85

Euler’s theorem, 79–83

and Lagrange, 99

perfect numbers, 32, 63–64

prime numbers, 63, 68

profile, 69–70

Euler totient function, 80, 245

Euler’s Theorem, 79–83, 246

proof using Lagrange’s Theorem, 101

Even and odd numbers, 9–10, 117

in GCD, 219–220, 224, 234

Existence of zero axiom, 172

Extended GCD algorithm, 229–235, 245, 247

extended_gcd, 233

F

Fast-multiplication algorithm. See Egyptian multiplication

Fermat, Pierre de, 63, 65–69

profile of, 67–68

proofs, 65–66, 68

Fermat primes, 63–68, 137

Fermat’s Last Theorem, 67

Fermat’s Little Theorem

converse of, 77–79

description, 69

non-invertibility lemma, 79

proof by Lagrange’s Theorem, 101

proof, 77

testing for prime numbers, 241–242

restatement using modular arithmetic, 84

Fermat test, 241–242

fermat_test, 242

Fibonacci. See Leonardo Pisano

Fibonacci numbers, computing, 124–127

Fibonacci sequence, 58–59

Fields

characteristic of, 151

definition, 151, 153

extensions, 151

prime, 151, 154

Fifth postulate of Euclidean geometry, 163–164

Figurate numbers

gnomons, 20

oblong numbers, 19

overview, 17, 19–20

triangular numbers, 19

square numbers, 20

find_if, 190–191

find_if_n, 191

Finite axiomatizability of theories, 102

Flowers, Tommy, 238

Floyd, Robert, 58

Formalist philosophy of mathematics, 167–169

Formulario Mathematico, 170–172

Forward iterators, 185

FP, 124

Function objects, 123–124, 268, 270

Functors. See Function objects

G

Galois, Évariste

discovery of groups, 85–88

profile of, 88–89

Gauss, Carl Friedrich, 31, 72, 136–140, 166, 240

profile of, 136–137

Gaussian integers, 138–139, 224

GCD (greatest common divisor)

applications of, 234

of polynomials, 134

description, 59

computing, 59

Euclid’s algorithm, 45–46

extended GCD, 229–235, 245, 247

historical milestones, 222

and rational arithmetic, 234

and ring structures, 225–229

rotation algorithms, 234

Stein’s algorithm, 219–225

symbolic integration, 234

validating, 59–60

gcd, 150, 230

GCM (greatest common measure) 33, 41

Euclid’s algorithm, 45–49

properties, 33

Generator elements in subgroups, 96

Generic programming

in C++, 265–266, 270

concepts, 181

essence, 127, 249–250

history, 124, 134, 141, 180

and mathematics, 84

overview, 1–2, 5

get_temporary_buffer, 217

Gnomons, 20

Gödel, Kurt, 169

Göttingen, University of

Carl Gauss, 136–140

David Hilbert, 168–169

Emmy Noether, 140–145

profile, 135–136

Granville, Andrew, 244

Grassman, Hermann, 171

Greatest common divisor (GCD). See GCD (greatest common divisor)

Greatest common measure (GCM). See GCM (greatest common measure)

Gries, David, 205

Gries-Mills algorithm, 204–208

Groups

abelian, 86, 108, 153

additive, 86

binary operations, 86

cyclic, 96, 109

definition, 85

discovery of, 85

examples of, 86–88

identity elements, 86

inverse operations, 86

Klein group, 106

order of elements, 94

summary description, 108, 152

symmetric, 198

theorems about, 92–95

H

half, 118

Heath, Thomas, 9, 45

Hegel, G.W.F., 111

Hellman, Martin, 239

Hilbert, David, 141, 167–169, 229

profile, 168–169

Hilbert spaces, 168–169

Hilbert’s problems, 169

Hilbert’s program, 169

History of Algebra, 129

Horner’s rule, 132

Hyperbolic geometry, 164–167

I

Ibn Rushd, 180

Ideals. See also Rings

definition, 226

ideals in Euclidean domains lemma, 227

linear combination ideal lemma, 227

PID (principal ideal domains), 228

principal ideals, 227–228

principal elements, 227

Ideals in Euclidean domains lemma, 227

Identity element, 108–109, 121

in groups, 86

in monoids, 89

in rings, 143

identity_element, 123, 241

Immutable objects, 181

Impossibility of infinite descent, 21

Inclusion-exclusion principle, 82–83

Incommensurable quantities, 45–49

Independence, theories, 102

Indian mathematics, 51

Induction, proof by, 262–263

Induction axiom, 21, 170, 172–173

Inman, Bobby Ray, 240

Inner product of two vectors, 145–146

In-place algorithms, 215–216

Input iterators, 185

Integral Calculus, 70

Integral domains, 145, 153

Interface refinement, law of, 215

Interfaces, designing, 215

Interlingua, 171

Intermediate Value Theorem (IVT), 131, 192

Introduction to Analysis of the Infinite, 70

Introduction to Arithmetic, 10, 19

Intuitionist philosophy of mathematics, 229

Inverse numbers, 73

inverse_operation, 123

Inverse operation, 86, 119, 121

in groups, 86

Invertibility lemma, 229

Invertibility of successor axiom, 173

Invertible elements. See Units

Irrational numbers, 38–39

is_prime, 241

Isomorphism, models, 103–104

Iterator categories

bidirectional, 185

forward, 185

input, 185

output, 186

random-access, 185

Iterator traits, 187

iterator_category iterator trait, 187

Iterators

in arrays, 185

bidirectional, 185

definition, 184

dereferencing, 184–185

difference type, 187

finding the distance between, 186–187

forward, 185

input, 185

in noncontiguous data segments, 186

linked, 186

output, 186

overview, 184–185

random access, 185

segmented, 186

successors, 184

Iverson, Kenneth, 124

IVT (Intermediate Value Theorem), 131, 192

J

Jefferson, Thomas, 44, 130

K

Kapur, Deepak, 124

Kayal, Neeraj, 244

Keys, cryptography, 238

Khayyam, Omar, 164

Kleene, Stephen, 115–116

Klein, Felix, 106–107, 141

Klein group, 106–107

Knuth, Donald E., 9, 58, 197

Kovalevskaya, Sofia, 141

L

Lagrange, Joseph-Louis, 99–100, 192

Lagrange’s Theorem, 97–99, 100–101

Lambda expressions, 195, 272–273

Laplace, Pierre-Simon, 70

largest_doubling, 54

Latine sine Flexione, 171

Law of completeness, 203–204

Law of interface refinement, 215

Law of separating types, 202–203

Law of useful return, 57–58, 201–202, 213

Lectures on Number Theory (Vorlesungen über Zahlentheorie), 140

Legendre, Adrien-Marie, 155

Lehmer, D. H., 192

Leonardo Pisano

Fibonacci sequence, 58–59

introduction of zero, 52

profile, 52–53

Letters to a German Princess, 70

Liber Abaci, 52

Liber Quadratorum, 52

Library of Alexandra, 43

Lincoln, Abraham, 44

Linear algebra

inner product, 145–146

matrix-matrix product, 146

matrix-vector product, 146

review, 145–147

Linear combination ideal lemma, 227

Linear recurrence functions, 127

Linear recurrence sequences, 127

Linear search, 190–191

Linked iterators, 186

Liu, Hui, 51

Lobachevsky, Nikolai, 164–166

Lorenz machine, 238

lower_bound, 195–196

Lyceum, 179

M

Magmas, 91, 108

mark_sieve, 24

Math notation in this book, 257–259

Matrix multiplication, 145–147

Matrix-matrix product, 146

Matrix-vector product, 146

Mauchly, John, 192

McJones, Paul, 3

Measure of a segment, 33

Memory-adaptive algorithms, 216–217

Meno, 43

Mersenne, Marin, 64–65

Mersenne primes, 63–68

Metaphysics, 179

Miller-Rabin test, 243–245

miller_rabin_test, 243

Mills, Harlan, 205

Models. See also Theories

definition, 103

isomorphism, 103–104

Modern Algebra, 142

Modular arithmetic, 72–74, 83–84

Fermat’s Little Theorem, 83–84

Wilson’s Theorem, 83

Modules, definition, 151, 154

modulo_multiply, 241

Monoids. See also Groups

additive, 89, 109, 154

definition, 89

examples of, 89

multiplicative, 89, 154

summary description, 108, 152

Mouseion, 43

Multiplication

definition, 8, 173–174

Egyptian, 8–11

Russian Peasant Algorithm. 9

Multiplicative functions, 31

multiplicative_inverse, 121, 247

multiplicative_inverse_fermat, 241

Multiplicative monoids, 89

Multiplicative semigroups, 90

Multiply-accumulate function, 11–14

Musser, David R., 124

Mutable objects, 181

N

Naming conventions, concepts, 183

Naming principle, 115–116

Natural numbers, 147, 170, 172, 175, 258

Nicomachean Ethics, 179

Nicomachus of Gerasa, 10, 19

Nine Chapters on the Mathematical Art, 51

Noether, Emmy, 129, 140–145

profile, 141–142

Non-categorical theories, 106–107

Noncommutative additive monoids, 119

Noncommutative additive semigroups, 115

Noncommutative algebra, rings, 143–144

Nonconstructive proofs, 229

Noncontiguous data segments, iterators, 186

Non-Euclidean geometry, 164–167

Non-invertibility lemma, 79

Notation in this book, 257–259

Number line, 131

Number of assignments theorem, 200–201

Number systems, ancient Egypt, 8

Number theory 2, 41, 43

in ancient Greece, 17–39

Bezout’s identity, 225–229

Euler’s Theorem, 79–83, 101

Fermat’s Little Theorem 69–78, 101

figurate numbers, 17–20, 33

Gauss, 136–137

and GCD, 140

Liber Quadratorum, 53

modular arithmetic, 72–74

perfect numbers, 28–32

primality testing 240–245

prime numbers, 21–28

17th and 18th century, 63–72, 74–84

sieve of Eratosthenes, 22–23

Wilson’s Theorem, 76, 83

O

Object types, definition, 181

Objects

definition, 180

immutable, 181

mutable, 181

remote parts, 181

unrestricted, 181

Oblong numbers, 19

Octonions, 151

odd, 118

Odd numbers. See Even and odd numbers

One-to-one correspondence, 92

Open ranges, 188

“Operators and Algebraic Structures,” 124

Order of group elements, 94

Organon, 180

Output iterators, 186

P

Palindromic primes, 28

Parallel postulate. See Fifth postulate of Euclidean geometry

Partition points, 193

partition_point, 194

partition_point_n, 193

Peano, Giuseppe, 169–175

profile, 171–172

Peano arithmetic, 170–171, 173–175

Peano axioms, 170–173

Peano curve, 171

Perfect numbers

in ancient Greece, 28–32, 38

definition, 28–29

mathematicians’ interest in, 63

Permutation of remainders lemma, 71–72

Permutations, 197–201

Phaedo, 43

Philo of Alexandria, 7

PID (principal ideal domains), 228

Pigeonhole principle, 95, 263

Pisano, Leonardo See Leonardo Pisano

Plaintext, 238

Plato, 41–43, 177–179

profile, 42–43

Platonic Questions, 20

Platonic solids, 41, 44

Playfair’s axiom, 163

Plus sign (+), mathematical convention for, 115

Plutarch, 20

Poincaré, Jules Henri, 85, 229–230, 248

profile, 229–230

pointer iterator trait, 187

Politics, 179

Polylog space, 215–216

Polynomials

computing GCD for, 134

degree of, definition, 133

division with remainder, 133

history of, 132–135

Horner’s rule, 132

treating as numbers, 133–135

polynomial_value, 132

Population count, 10

Postconditions, 269

Postulates, Euclid’s axiomatic method, 162, 163

Power algorithm, 119–123, 249

computing Fibonacci numbers, 126

computing linear recurrence, 127

use in cryptology, 241–243, 246

use in graph applications, 148–149

power_accumulate_semigroup, 121

power_group, 123

power_monoid, 122

power_semigroup, 122

Primality testing, 240–245

Prime factorization, 29, 31–32, 65, 136, 139–140

Prime fields, 151, 154

Prime numbers

in ancient Greece, 21–28

definition, 21

distinguishing from composite, 240–245

Fermat primes, 63–68

finding. See sieve of Eratosthenes

infinite number of, 21

Mersenne primes, 63–68

primality testing, 240–245

Principal element, 227

Principal ideal domains (PID), 228

Principal ideals, 227–228

Problèmes Plaisants, 225–226

Proof

by contradiction, 35, 261–262

definition, 158–159

by induction, 262–263

nonconstructive, 229

pigeonhole principle, 95, 263

visual, 155–159

Proper divisor, 32

Ptolemy, 164

Public-key cryptosystems, 239–240

Pythagoras, 17

profile, 18–19

Pythagorean program, 33–38

Pythagorean Theorem, 44

Pythagorean triples, 50–51

Q

Quadrivium, 18

Quaternions, 151

Quotient, 55–57, 150, 153, 202

for polynomials, 133

quotient_remainder, 57

R

Random-access iterators, 185

Ranges

bounded, 189, 203–204

closed, 188

counted, 189, 203–204

definition, 188

open, 188

overview, 188–189

partition points, 193

semi-open, 188

swapping, 201–204

Rational arithmetic, GCD applications, 234

Rational numbers, 151, 258

Real numbers, 131, 258

reciprocal, 124

Recreational mathematics, 225–226

Recursive remainder lemma, 48–49

Reduction algorithm, 124

reference iterator trait, 187

Regius, Hudalricus, 64

Regular concepts, 183–184

Regular functions, 183

Regular types, 114

Rejewski, Marian, 238

Remainder, 47–49, 53–55, 57–59, 150, 153, 222

Floyd-Knuth algorithm, 58

permutation of remainders, 71–72

in modular arithmetic, 73–75

of Gaussian integers, 138–139

of polynomials, 133–134

remainder, 54–55

remainder_fibonacci, 58

Remote parts of objects, 181

Requirements on algorithm, 111–119

reverse, 212–215

reverse_copy, 216

reverse_n, 214

reverse_n_adaptive, 217

reverse_n_with_buffer, 216

reverse_recursive, 214

Reverse permutation, 201, 212–215

Rewriting code, 14–15

Rhind Mathematical Papyrus, 8, 57

Rings. See also Ideals; Semirings

definition, 142–143

and the GCD, 225–229

integral domains, 145

summary description, 153

unitary, 143

units, 144

zero divisors, 145

Rivest, Ron, 239

Rotate algorithms, 204–213

rotate, 207, 210, 213

rotate_cycle_from, 208

rotate_transform, 210

rotate_unguarded, 206

Rotation, 204–207

Rotation algorithms, GCD applications, 234

RSA algorithm, 239–240, 245–247

Russell, Bertrand, 171

Russian Peasant Algorithm, 9. See also Egyptian multiplication

S

Saccheri, Giovanni Girolamo, 164

Saxena, Nitin, 244

Scheme, 116

The School of Athens, 177–178

Searches

binary, 191–196

linear, 190–191

Segmented iterators, 186

Self-Canceling Law, 75–76

Semantic requirements for generic algorithms, 113

Semigroups. See also Groups

additive, 90, 109

associativity axiom, 91

commutativity of powers, 91

definition, 90, 109

examples, 90

multiplication algorithm, 115

multiplicative, 90

summary description, 108, 152

Semi-open ranges, 188

Semiregular concepts, 184

Semirings. See also Rings

Boolean, 148

description, 145–147

matrix multiplication, 146

shortest path, 148–149

summary description, 153

tracing social networks, 147–148

transitive closures, 147–148

tropical, 149

weak, 147

Separating types, law of, 202–203

Setting of algorithm, 150

Shamir, Adi, 239

Shortest path, finding, 148–149

Sieve of Eratosthenes, 22–23

implementation 23–28

sift, 27

smallest_divisor, 240

Social network connections, tracing, 147–148

Socrates, 42

Socratic method, 42

Sophists, 42

Space complexity, 215–216

Square root of 2, an irrational number, 37–38

Standard Template Library. See STL

Stein, Josef, 219–222

Stein’s algorithm, 219–225

stein_gcd, 220

Stepanov, Alexander A., 3, 124

Stevin, Simon, 129–135, 192

profile, 130–131

STL (Standard Template Library)

algorithms, 195–196, 215, 217

application of generic programming, 1, 186

containers, 190–191

conventions, 24

non-categorical, 104

Strength reduction, 26

Stroustrup, Bjarne, 265

Subgroups. See also Groups

cyclic, 96

definition, 95, 109

generator elements, 96

trivial, 95

Successors, 170, 184

Sum of odd powers formula, 30

swap, 199

swap_ranges, 201–203

Symbolic integration, GCD applications, 234

Symmetric groups, 198

Symmetric keys, 238

Symposium, 43

Syntactic requirements for generic algorithms, 113

T

Tail-recursive functions, 12–14

Template functions, 265–266

Thales of Miletus, 18, 159–161

Thales’ Theorem, 160–161

Theories. See also Models

categorical, 104–106

characteristics of, 102

completeness, 102

consistency, 102, 104

definition, 102

determining truth of, 167

finite axiomatizability, 102

independence, 102

non-categorical, 106–107

univalent, 104

Totality of successor axiom, 172

Totient of an integer, 80

A Tour of C++, 265

Transfinite ordinals, 172–173

Transformation group, 92

Transitive closures, finding, 147–148

Transposition lemma, 199

Transpositions, 197, 199–201

Trapdoor one-way functions, 239

Triangular numbers, 19

Trichotomy Law, 34

Trip count, 204, 213

Trivial cycles, 200, 208

Trivial subgroups, 95

Tropical semirings, 149

Turing, Alan, 169, 238

Tusculan Disputations, 50

Type attributes, 182–183

Type dispatch. See Category dispatch

Type functions, 182–183

U

Unitary rings, 143

Units, rings, 144

Univalent theories, 104

Univariate polynomials. See Polynomials

University of Göttingen. See Göttingen, University of

Unreachable numbers, 172–173

Unrestricted objects, 181

upper_bound, 195

Useful return, law of, 57–58, 201–202, 213

V

Value types, definition, 180

Values, definition, 180

value_type iterator trait, 187

van der Waerden, Bartel, 129, 142

Veblen, Oswald, 104

vector container, 116,

Vector space, 152, 154

Visual proofs, 155–159

Vorlesungen über Zahlentheorie (Lectures on Number Theory), 140

W

Waring, Edward, 76

Weak semirings, 147

Weilert, Andre, 224

Well-ordering principle, 34

Whitehead, Alfred North, 43

Wiles, Andrew, 67

Wilson, John, 76

Wilson’s Theorem

description, 76

using modular arithmetic, 83

Witnesses, primality testing, 242

Z

Zero

in Egyptian number system, 8

introduction of, 52

origins of, 51–53

Zero divisors, rings, 145, 154