## Programming for MathematiciansThe aim of this book is to teach mathematics students how to program using their knowledge of mathematics. For this they require only to know how to construct a proof. The entire book's emphasis is on "how to think" when programming. Three methods for constructing an algorithm or a program are used: a) manipulation and enrichment of existing code; b) use of recurrent sequences; c) deferral of code writing, in order to deal with one difficulty at a time. Many theorems are mathematically proved and programmed. The last chapter explains how a compiler works and shows how to compile "by hand" little (but not trivial--even recursive) programs. The book is intended for anyone who thinks mathematically and wants to program and play with mathematics. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 Programming Proverbs | 1 |

12 Do not chewing gum while climbing stairs | 2 |

15 Never execute an order before it is given | 3 |

2 Review of Arithmetic | 5 |

22 Numeration Systems | 6 |

23 Prime Numbers | 7 |

24 The Greatest Common Divisor | 9 |

25 Congruences | 11 |

862 Transforming the algorithm to a program | 172 |

87 The Function pix | 175 |

872 Implementation of Legendres formula | 178 |

873 Meissels formula | 179 |

88 Egyptian Fractions | 181 |

881 The program | 183 |

882 Numerical results | 186 |

89 Operations on Large Integers | 187 |

26 The Chinese Remainder Theorem | 12 |

27 The Euler phi Function | 14 |

28 The Theorems of Fermat and Euler | 15 |

29 Wilsons Theorem | 16 |

210 Quadratic Residues | 17 |

211 Prime Number and Sum of Two Squares | 18 |

212 The Moebius Function | 19 |

213 The Fibonacci Numbers | 21 |

214 Reasoning by Induction | 22 |

215 Solutions of the Exercises | 25 |

3 An Algorithmic Description Language | 29 |

31 Identifiers | 30 |

32 Arithmetic Expressions | 31 |

323 Arrays | 32 |

34 Statements and their Syntax | 33 |

341 Assignments | 34 |

343 For loops | 35 |

346 Sequences of statements | 36 |

348 Complex statements | 37 |

349 Layout on page and control of syntax | 38 |

3410 To what does the else belong? | 40 |

35 The Semantics of Statements | 42 |

353 First translations | 43 |

354 The boustrophedon order | 45 |

355 The for loop | 47 |

356 The while loop | 48 |

J 57 The repeat loop | 50 |

358 Embedded loops | 51 |

361 Choosing a for loop | 52 |

365 Loops with accidents | 54 |

366 Gaussian elimination | 55 |

367 How to grab data | 56 |

4 How to Create an Algorithm | 59 |

Recycling Known Code | 60 |

422 How to determine whether a postage is realizable | 61 |

423 Calculating the threshold value | 62 |

Using Sequences | 64 |

431 Creation of a simple algorithm | 66 |

432 The exponential series | 67 |

433 Decomposition into prime factors | 69 |

434 The least divisor function | 71 |

436 The CORDIC Algorithm | 74 |

Defered Writing | 78 |

441 Calculating two bizarre functions | 80 |

442 Storage of the first N prime numbers | 81 |

443 Last recommendations | 84 |

45 How to Prove an Algorithm | 85 |

453 Calculating the GCD of two numbers | 86 |

455 The validity of a result furnished by a loop | 87 |

46 Solutions of the Exercises | 88 |

5 Algorithms and Classical Constructions | 91 |

52 Diverse Sums | 92 |

522 Double sums | 93 |

523 Sums with exceptions | 94 |

53 Searching for a Maximum | 95 |

54 Solving a Triangular Cramer System | 96 |

55 Rapid Calculation of Powers | 97 |

56 Calculation of the Fibonacci Numbers | 98 |

57 The Notion of a Stack | 99 |

58 Linear Traversal of a Finite Set | 101 |

59 The Lexicographic Order | 102 |

592 Words of variable length | 104 |

510 Solutions to the Exercises | 105 |

6 The Pascal Language | 109 |

62 Integer Arithmetic in Pascal | 110 |

63 Arrays in Pascal | 113 |

64 Declaration of an Array | 114 |

65 Product Sets and Types | 115 |

652 Product of unequal sets | 116 |

66 The Role of Constants | 117 |

67 Litter | 119 |

681 The declarative part of a procedure | 120 |

682 Procedure calls | 121 |

683 Communication of a procedure with the exterior | 122 |

69 Visibility of the Variables in a Procedure | 124 |

610 Context Effects | 125 |

6101 Functions | 127 |

6102 Procedure or function? | 128 |

What the Program Seems To Do | 129 |

6111 Using the model | 133 |

612 Solutions of the Exercises | 134 |

7 How to Write a Program | 135 |

711 The problem | 136 |

713 Writing the program | 138 |

714 The function det | 140 |

715 How to type a program | 143 |

72 Characteristic Polynomial of a Matrix | 144 |

721 The program Leverrier | 147 |

73 How to Write a Program | 152 |

74 A Poorly Written Procedure | 156 |

8 The Integers | 159 |

811 Complexity of the Euclidean algorithm | 160 |

82 The Blankinship Algorithm | 161 |

83 Perfect Numbers | 163 |

84 The Lowest Divisor Function | 165 |

85 The Moebius Function | 167 |

86 The Sieve of Eratosthenes | 169 |

861 Formulation of the algorithm | 171 |

892 Subtraction | 188 |

893 Multiplication | 189 |

894 Declarations | 190 |

895 The program | 191 |

810 Division in Base b | 194 |

8102 Justification of the division algorithm | 196 |

8103 Effective estimates of integer parts | 197 |

8104 A good division algorithm | 200 |

812 Odd Primes as a Sum of Two Squares | 203 |

813 Sums of Four Squares | 207 |

814 Highly Composite Numbers | 208 |

8141 Several properties of highly composite numbers | 210 |

8142 Practical investigation of highly composite integers | 212 |

Johnsons Algorithm | 213 |

8151 The program Johnson | 215 |

816 The Count is Good | 218 |

8161 Syntactic trees | 219 |

9 The Complex Numbers | 225 |

911 Euclidean division | 226 |

913 The program | 231 |

92 Bases of Numeration in the Gaussian Integers | 234 |

922 How to find an exact system of representatives | 235 |

923 Numeration system in base beta | 236 |

93 Machin Formulas | 240 |

931 Uniqueness of a Machin formula | 242 |

932 Proof of Proposition 931 | 243 |

933 The Todd condition is necessary | 244 |

935 Kerns algorithm | 245 |

936 How to get rid of the Arctangent function | 249 |

937 Examples | 251 |

10 Polynomials | 253 |

102 Degree of a Polynomial | 254 |

104 The Conventions we Adopt | 256 |

105 Euclidean Division | 259 |

Horners Method | 261 |

107 Translation and Composition | 262 |

1072 Composing polynomials | 265 |

1081 First formula | 266 |

1082 Second formula | 268 |

109 Lagrange Interpolation | 269 |

1010 Basis Change | 273 |

1011 Differentiation and Discrete Taylor Formulas | 275 |

1012 NewtonGirard Formulas | 278 |

1013 Stable Polynomials | 280 |

1014 Factoring a Polynomial with Integral Coefficients | 286 |

10142 Kroneckers factorization algorithm | 288 |

10143 Use of stable polynomials | 290 |

10144 The program | 291 |

10145 Last remarks | 294 |

11 Matrices | 297 |

1111 The bordered matrix trick | 300 |

1112 Generators of a subgroup | 301 |

1114 Hermite matrices | 303 |

1115 The program Hermite | 305 |

1116 The incomplete basis theorem | 312 |

1117 Finding a basis of a subgroup | 316 |

112 Linear Systems with Integral Coefficients | 318 |

1123 General case | 320 |

1124 Case of a single equation | 321 |

Putzers Algorithm | 323 |

114 Jordan Reduction | 326 |

1142 Reduction of a nilpotent endomorphism | 327 |

1143 The PitttelkowRunckel algorithm | 329 |

1144 Justification of the PittelkowRunckel algorithm | 332 |

1145 A complete example | 333 |

1146 Programming | 336 |

12 Recursion | 337 |

1212 Mutual recursion | 339 |

1213 Arborescence of recursive calls | 340 |

122 The Ackermann function | 343 |

123 The Towers of Hanoi | 345 |

124 Baguenaudier | 348 |

125 The Hofstadter Function | 351 |

126 How to Write a Recursive Code | 352 |

1261 Sorting by dichotomy | 353 |

13 Elements of compiler theory | 359 |

1311 Description of pseudocode | 360 |

1312 How to compile a pseudocode program by hand | 365 |

1313 Translation of a conditional | 366 |

1314 Translation of a loop | 368 |

1315 Function calls | 369 |

1316 A very efficient technique | 372 |

1317 Procedure calls | 374 |

1318 The factorial function | 377 |

1319 The Fibonacci numbers | 379 |

13110 The Hofstadter function | 381 |

13111 The Towers of Hanoi | 382 |

132 A Pseudocode Interpreter | 385 |

133 How to Analyze an Arithmetic Expression | 400 |

1331 Arithmetic expressions | 401 |

1332 How to recognize an arithmetic expression | 404 |

134 How to Evaluate an Arithmetic Expression | 410 |

135 How to Compile an Arithmetic Expression | 415 |

1352 A Compiler for arithmetic expressions | 420 |

423 | |

425 | |

### Other editions - View all

### Common terms and phrases

algorithm Arctan Arctan(l arithmetic expression array baguenaudier binary tree boolean calculate choose column compiler Consider contains cyclotomic polynomials decomposition defined definition deg-max digit display divides divisor downto Egyptian fractions element end end equal equation Euclidean algorithm Euclidean division Euler phi function example execute Exercise exist factors false Fibonacci finish function Gaussian integers GCD(a gives goto highly composite induction integer coefficients invertible irreducible Lemma lexicographic order loop Machin formula mathematicians mathematics modify modulo Moebius function multiplication next-token obtain parameters parentheses Pascal permutation poly polynomial prime number Proof pseudocode push real number recursive calls relatively prime Remark repeat replace result sequence shows solution square stable polynomial stack statement string of characters stringSO suffices Suppose Theorem token toto(x translation unimodular matrix variable vector write writeln x-toto zero