This is a mathematics book, not a programming book. It is aimed at high school students and undergraduates with a strong interest in mathematics, and teachers looking for fresh ideas. It is full of diverse mathematical ideas requiring little background. It includes a large number of challenging problems, many of which illustrate how numerical computation leads to conjectures which can then be proved by mathematical reasoning. It is assumed that readers have a PC at their disposal.
Author(s): Arthur Engel
Series: Anneli Lax New Mathematical Library 35
Publisher: The Mathematical Association of America
Year: 1993
Language: English
Commentary: decrypted from FED368443331EDDBA69EBAE80B823FDC source file
Pages: 300
Contents
Cover
Preface
Chapter 1 Introductory Problems
1 The Factorial: First Encounter with Recursion
2 Fibonacci's Sequence: a Two-Term Recursion
3 Another Linear Recursion. Bisection Method
4 The Bold Gamble. Recursion at its Best
5 The Josephus Problem
Exercises for Section 1-5
Chapter 2 Algorithms in Number Theory
6 Greatest Common Divisor
Euclid's Algorithm
Extended Euclidean Algorithm
Visible Points in the Plane Lattice
Binary GCD Algorithm
Gill's GCD and LCM algorithm
Exercises for Section 6
7 All Representations of n in the form x 2 + y2
8 Pythagorean Triples
9 Counting the Lattice Points in a Ball
Exercises for Sections 7-9
10 Sieves
Square-free Integers
Sieve of Eratosthenes
A Formula for an Irregular Sequence
An Olympiad Problem
Ulam's Sequence
Exercises for Section 10
11 Rotation of an Array
12 Partitions
13 The Money Changing Problem
14 An Abstractly Defined Set
15 A Recursive Program with a Surprising Result
16 Sequence 56 in Sloane's Handbook of Integer Sequences
Exercises for Sections 11-16
17 Primes
How to Recognize a Prime
Empirical Study of the Goldbach Conjecture
Prime Twins, Triples, Quadruples
Factoring
18 Representation of n as a Sum of Four Squares
Exercises for Sections 17-18
Additional Exercises for Sections 1-18
19 The Best Rational Approximation
20 The Maximum of a Unimodal Function
Chapter 3 Probability
21 The Random Number Generator
22 Finding Geometric Probabilities by Simulation
Exercises for Section 22
23 Random Choice of an s-Subset from an n-Set
24 Coin Tosses for Poor People
25 Shift Registers: Another Source of Cheap Coin Tosses
26 Random Sequence Generation by Cellular Automata
27 The Period Finding Problem
Exercises for Sections 1-27
Chapter 4 Statistics
28 Matched Pairs
29 Permutation Test, P by Simulation
30 Permutation Test, P by Computation
Exercises for Sections 28-30
31 The Two Sample Problem of Wilcoxon
32 The General Two Sample Test
Exercises for Sections 31-32
33 Kendall's Rank Correlation
34 The Binomial Distribution
35 Hypergeometric Distribution
36 Fishing Laws
37 Estimation of a Probability
38 Runs
39 The Period of Random(2)
40 Waiting for a Complete Set. An Intractable Problem?
Additional Exercises for Sections 21-40
41 The Birthday Problem. An O{n1 / 4 )-Method of Factoring
Chapter 5 Combinatorial Algorithms
42 Sorting
Sorting by Selection
Sorting by Insertion
Shellsort
Quicksort
Bucket Sort
43 The kth Smallest Element of an n-Set
44 Binary Search
45 Binary Guessing (20 Questions)
46 The n-Queens Problem
47 Permutations
48 Games
49 The Subset Sum Problem. The Limits of Computation
Chapter 6 Numerical Algorithms
50 Powers with Integer and Real Exponents
51 Design of a Square Root Procedure
52 The Natural Logarithm
53 The Inverse Trigonometric Functions
54 The Function exp
55 The Cosine
56 Archimedes' Integration of the Parabola
57 Numerical Integration
58 Extrapolation to the Limit and Romberg Integration
59 One Thousand Decimals of e
Chapter 7 Miscellaneous Problems
60 A Problem from Geometry
61 Coupled Difference Equations. The Forward Declaration
62 Continued Fractions
63 Shrinking Squares: An Empirical Study
64 Self Avoiding Random Walks
65 A Very Difficult Problem
Appendix A Crash Course in Probability
Solutions of Some Exercises
Summary of Notation and Formulas
A Short Summary of TURBO PASCAL
For Users of other PASCAL compilers
References
Index
