Crc Standard Mathematical Tables And Formulas 33rd Edition Pdf
- 9,283,052 libros libros
- 84,837,646 artículos artículos
- Inicio de ZLibrary
- Inicio
Principal CRC Standard Mathematical Tables and Formulas, 33rd Edition
CRC Standard Mathematical Tables and Formulas, 33rd Edition
Daniel Zwillinger
¿Qué tanto le ha gustado este libro?
¿De qué calidad es el archivo descargado?
Descargue el libro para evaluar su calidad
¿Cuál es la calidad de los archivos descargados?
Containing more than 6,000 entries, CRC Standard Mathematical Tables and Formulas, 33rd Edition continues to provide essential formulas, tables, figures and detailed descriptions. The newest edition of this popular series also features many diagrams, group tables, and integrals that are not available online.
This edition also incorporates important topics such as max plus algebra, financial options, pseudospectra, and proof methods. Newly updated topics reflecting new results include coupled analogues, general relativity, radar, and significant equations of mathematics.
Editorial:
Chapman and Hall/CRC
Serie:
Advances in Applied Mathematics
El archivo se enviará a su dirección de correo electrónico durante el transcurso de 1-5 minutos.
El archivo se enviará a su cuenta de Kindle durante el transcurso de 1-5 minutos.
Nota: Ud. debe verificar cada libro que desea enviar a su Kindle. Revise su correo electrónico y encuentre un mensaje de verificación de Amazon Kindle.
También le puede interesar Powered by Rec2Me
Términos más frecuentes
"K29784_FM" — 2017/12/6 — 17:41 — page 2 — #2 CRC STANDARD MATHEMATICAL TABLES AND FORMULAS 33RD EDITION "K29784_FM" — 2017/12/6 — 17:41 — page 4 — #4 Advances in Applied Mathematics Series Editor: Daniel Zwillinger Published Titles Advanced Engineering Mathematics with MATLAB, Fourth Edition Dean G. Duffy CRC Standard Curves and Surfaces with Mathematica®, Third Edition David H. von Seggern CRC Standard Mathematical Tables and Formulas, 33rd Edition Dan Zwillinger Dynamical Systems for Biological Modeling: An Introduction Fred Brauer and Christopher Kribs Fast Solvers for Mesh-Based Computations Maciej Paszyński Green's Functions with Applications, Second Edition Dean G. Duffy Handbook of Peridynamic Modeling Floriin Bobaru, John T. Foster, Philippe H. Geubelle, and Stewart A. Silling Introduction to Financial Mathematics Kevin J. Hastings Linear and Complex Analysis for Applications John P. D'Angelo Linear and Integer Optimization: Theory and Practice, Third Edition Gerard Sierksma and Yori Zwols Markov Processes James R. Kirkwood Pocket Book of Integrals and Mathematical Formulas, 5th Edition Ronald J. Tallarida Stochastic Partial Differential Equations, Second Edition Pao-Liu Chow Quadratic Programming with Computer Programs Michael J. Best "K29784_FM" — 2017/12/6 — 17:41 — page 6 — #6 Advances in Applied Mathematics CRC STANDARD MATHEMATICAL TABLES AND FORMULAS 33RD EDITION Edited by Dan Zwillinger "K29784_FM" — 2017/12/6 — 17:41 — page 8 — #8 MATLAB• is a trademark of The MathWorks, Inc. and is used with permission. The MathWorks does not warrant the accuracy of the text or exercises in this book. This book's use or discussion of MATLAB• software or related products does not constitute endorsement or sponsorship by The MathWorks of a particular pedagogical approach or particular use of the MATLAB• software. CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2018 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & amp; Francis Group, an Informa business No claim to original U.S. Government works Printed on acid-free paper Version Date: 20171206 International Standard Book Number-13: 978-1-4987-7780-3 (Hardback) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com "smtf33" — 2017/12/6 — 19:00 — page v — #1 Table of Contents Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 1 Numbers and Elementary Mathematics . . . . . . . . . . . . . . . . . . . 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 Proofs without words . . . . . . Constants . . . . . . . . . . . . Special numbers . . . . . . . . Interval analysis . . . . . . . . Fractal Arithmetic . . . . . . . Max-Plus Algebra . . . . . . . Coupled-analogues of Functions Number theory . . . . . . . . . Series and products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi 1 3 5 13 24 25 26 27 28 47 Chapter 2 Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 2.1 2.2 2.3 2.4 2.5 Elementary algebra . . . . Polynomials . . . . . . . Vector algebra . . . . . . Linear and matrix algebra Abstract algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 . 73 . 78 . 83 . 106 Chapter 3 Discrete Mathematics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 3.1 3.2 3.3 3.4 3.5 Sets . . . . . . . . . . . . . Combinatorics . . . . . . . Graphs . . . . . . . . . . . Combinatorial design theory Difference equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 140 151 172 184 Chapter 4 Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 4.1 4.2 4.3 4.4 4.5 4.6 4.7 Euclidean geometry . . . . . . . Grades and Degrees . . . . . . . Coordinate systems in the plane . Plane symmetries or isometries . Other transformations of the plane Lines . . . . . . . . . . . . . . . Polygons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 193 194 200 207 209 211 "smtf33" — 2017/12/6 — 19:00 — page vi — #2 vi Table of Contents 4.8 4.9 4.10 4.11 4.12 4.13 4.14 4.15 4.16 4.17 4.18 4.19 4.20 4.21 4.22 Surfaces of revolution: the torus . . . Quadrics . . . . . . . . . . . . . . . Spherical geometry and trigonometry Conics . . . . . . . . . . . . . . . . Special plane curves . . . . . . . . . Coordinate systems in space . . . . . Space symmetries or isometries . . . Other transformations of space . . . . Direction angles and direction cosines Planes . . . . . . . . . . . . . . . . . Lines in space . . . . . . . . . . . . Polyhedra . . . . . . . . . . . . . . . Cylinders . . . . . . . . . . . . . . . Cones . . . . . . . . . . . . . . . . . Differential geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 219 224 229 240 249 252 255 257 257 259 261 265 265 267 Chapter 5 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10 5.11 5.12 5.13 5.14 Differential calculus . . . . . . . . Differential forms . . . . . . . . . Integration . . . . . . . . . . . . . Table of indefinite integrals . . . . Table of definite integrals . . . . . Ordinary differential equations . . . Partial differential equations . . . . Integral equations . . . . . . . . . . Tensor analysis . . . . . . . . . . . Orthogonal coordinate systems . . . Real analysis . . . . . . . . . . . . Generalized functions . . . . . . . Complex analysis . . . . . . . . . . Significant Mathematical Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 288 291 305 343 350 362 375 378 388 393 403 405 417 Chapter 6 Special Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 Ceiling and floor functions . . . . . . . Exponentiation . . . . . . . . . . . . . Exponential function . . . . . . . . . . Logarithmic functions . . . . . . . . . Trigonometric functions . . . . . . . . Circular functions and planar triangles . Tables of trigonometric functions . . . Angle conversion . . . . . . . . . . . . Inverse circular functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421 421 422 422 424 433 437 440 441 "smtf33" — 2017/12/6 — 19:00 — page vii — #3 Table of Contents 6.10 6.11 6.12 6.13 6.14 6.15 6.16 6.17 6.18 6.19 6.20 6.21 6.22 6.23 6.24 6.25 6.26 6.27 6.28 6.29 6.30 6.31 6.32 6.33 6.34 6.35 6.36 6.37 6.38 6.39 6.40 6.41 Hyperbolic functions . . . . . . . . . Inverse hyperbolic functions . . . . . Gudermannian function . . . . . . . Orthogonal polynomials . . . . . . . Clebsch–Gordan coefficients . . . . . Bessel functions . . . . . . . . . . . Beta function . . . . . . . . . . . . . Elliptic integrals . . . . . . . . . . . Jacobian elliptic functions . . . . . . Error functions . . . . . . . . . . . . Fresnel integrals . . . . . . . . . . . Gamma function . . . . . . . . . . . Hypergeometric functions . . . . . . Lambert Function . . . . . . . . . . . Legendre functions . . . . . . . . . . Polylogarithms . . . . . . . . . . . . Prolate Spheroidal Wave Functions . Sine, cosine, and exponential integrals Weierstrass Elliptic Function . . . . . Integral transforms: List . . . . . . . Integral transforms: Preliminaries . . Fourier integral transform . . . . . . Discrete Fourier transform (DFT) . . Fast Fourier transform (FFT) . . . . . Multidimensional Fourier transforms Hankel transform . . . . . . . . . . . Hartley transform . . . . . . . . . . . Hilbert transform . . . . . . . . . . . Laplace transform . . . . . . . . . . Mellin transform . . . . . . . . . . . Z-Transform . . . . . . . . . . . . . Tables of transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443 447 449 451 458 460 469 470 473 475 476 478 481 483 484 488 489 490 492 493 494 494 500 502 502 503 504 505 508 512 512 517 Chapter 7 Probability and Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . 533 7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9 Probability theory . . . . . . Classical probability problems Probability distributions . . . Queuing theory . . . . . . . . Markov chains . . . . . . . . Random number generation . Random matrices . . . . . . . Control charts and reliability . Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535 545 553 562 565 568 574 575 580 "smtf33" — 2017/12/6 — 19:00 — page viii — #4 viii Table of Contents 7.10 7.11 7.12 7.13 7.14 7.15 7.16 7.17 Confidence intervals . . . . . . Tests of hypotheses . . . . . . . Linear regression . . . . . . . . Analysis of variance (ANOVA) Sample size . . . . . . . . . . . Contingency tables . . . . . . . Acceptance sampling . . . . . . Probability tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588 595 609 613 620 623 626 628 Chapter 8 Scientific Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645 8.1 8.2 8.3 8.4 Basic numerical analysis . . . . . . . . . Numerical linear algebra . . . . . . . . . Numerical integration and differentiation Programming techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646 659 668 688 Chapter 9 Mathematical Formulas from the Sciences . . . . . . . . . . . . . . . . . 689 9.1 9.2 9.3 9.4 9.5 9.6 9.7 9.8 9.9 9.10 9.11 9.12 9.13 9.14 9.15 9.16 9.17 9.18 9.19 9.20 9.21 9.22 9.23 9.24 9.25 9.26 Acoustics . . . . . . . . . . . . . . Astrophysics . . . . . . . . . . . . Atmospheric physics . . . . . . . . Atomic Physics . . . . . . . . . . . Basic mechanics . . . . . . . . . . Beam dynamics . . . . . . . . . . . Biological Models . . . . . . . . . Chemistry . . . . . . . . . . . . . . Classical mechanics . . . . . . . . Coordinate systems – Astronomical Coordinate systems – Terrestrial . . Earthquake engineering . . . . . . Economics (Macro) . . . . . . . . Electromagnetic Transmission . . . Electrostatics and magnetism . . . Electromagnetic Field Equations . . Electronic circuits . . . . . . . . . Epidemiology . . . . . . . . . . . . Fluid mechanics . . . . . . . . . . Human body . . . . . . . . . . . . Modeling physical systems . . . . . Optics . . . . . . . . . . . . . . . . Population genetics . . . . . . . . . Quantum mechanics . . . . . . . . Quaternions . . . . . . . . . . . . . Radar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 691 692 694 695 696 698 699 700 701 702 703 704 705 707 708 709 710 711 712 713 714 715 716 717 719 720 "smtf33" — 2017/12/6 — 19:00 — page ix — #5 Table of Contents 9.27 9.28 9.29 9.30 Relativistic mechanics Solid mechanics . . . Statistical mechanics . Thermodynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix . . . . . . . . 721 722 723 724 Chapter 10 Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725 10.1 10.2 10.3 10.4 10.5 10.6 10.7 10.8 10.9 10.10 10.11 10.12 10.13 10.14 10.15 10.16 10.17 10.18 10.19 10.20 10.21 10.22 10.23 10.24 10.25 10.26 10.27 10.28 Calendar computations . . . . . . . . . Cellular automata . . . . . . . . . . . . Communication theory . . . . . . . . . Control theory . . . . . . . . . . . . . Computer languages . . . . . . . . . . Compressive Sensing . . . . . . . . . . Constrained Least Squares . . . . . . . Cryptography . . . . . . . . . . . . . . Discrete dynamical systems and chaos . Elliptic curves . . . . . . . . . . . . . Financial formulas . . . . . . . . . . . Game theory . . . . . . . . . . . . . . Knot theory . . . . . . . . . . . . . . . Lattices . . . . . . . . . . . . . . . . . Logic . . . . . . . . . . . . . . . . . . Moments of inertia . . . . . . . . . . . Music . . . . . . . . . . . . . . . . . . Operations research . . . . . . . . . . Proof Methods . . . . . . . . . . . . . Recreational mathematics . . . . . . . Risk analysis and decision rules . . . . Signal processing . . . . . . . . . . . . Units . . . . . . . . . . . . . . . . . . Voting power . . . . . . . . . . . . . . Greek alphabet . . . . . . . . . . . . . Braille code . . . . . . . . . . . . . . . Morse code . . . . . . . . . . . . . . . Bar Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 727 728 729 734 736 737 738 739 740 743 746 754 757 759 761 766 767 769 781 782 783 785 794 801 803 803 803 804 List of References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805 List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 809 List of Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 811 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 819 "smtf33" — 2017/12/6 — 19:00 — page x — #6 "smtf33" — 2017/12/6 — 19:00 — page xi — #7 Preface It has long been the established policy of CRC Press to publish, in handbook form, the most up-to-date, authoritative, logically arranged, and readily usable reference material available. Just as pocket calculators have replaced tables of square roots and trig functions; the internet has made printed tabulation of many tables and formulas unnecessary. As the content and capabilities of the internet continue to grow, the content of this book also evolves. For this edition of Standard Mathematical Tables and Formulae the content was reconsidered and reviewed. The criteria for inclusion in this edition includes: • information that is immediately useful as a reference (e.g., interpretation of powers of 10); • information that is useful and not commonly known (e.g., proof methods); • information that is more complete or concise than that which can be easily found on the internet (e.g., table of conformal mappings); • information difficult to find on the internet due to the challenges of entering an appropriate query (e.g., integral tables). Applying these criteria, practitioners from mathematics, engineering, and the sciences have made changes in several sections and have added new material. • The "Mathematical Formulas from the Sciences" chapter now includes topics from biology, chemistry, and radar. • Material has been augmented in many areas, including: acceptance sampling, card games, lattices, and set operations. • New material has been added on the following topics: continuous wavelet transform, contour integration, coupled analogues, financial options, fractal arithmetic, generating functions, linear temporal logic, matrix pseudospectra, max plus algebra, proof methods, and two dimensional integrals. • Descriptions of new functions have been added: Lambert, prolate spheroidal, and Weierstrass. Of course, the same successful format which has characterized earlier editions of the Handbook has been retained. Material is presented in a multi-sectional format, with each section containing a valuable collection of fundamental reference material— tabular and expository. xi "smtf33" — 2017/12/6 — 19:00 — page xii — #8 xii Preface In line with the established policy of CRC Press, the Handbook will be updated in as current and timely manner as is possible. Suggestions for the inclusion of new material in subsequent editions and comments regarding the present edition are welcomed. The home page for this book, which will include errata, will be maintained at http://www.mathtable.com/smtf. This new edition of the Handbook will continue to support the needs of practitioners of mathematics in the mathematical and scientific fields, as it has for almost 90 years. Even as the internet becomes more powerful, it is this editor's opinion that the new edition will continue to be a valued reference. MATLAB R is a registered trademark of The MathWorks, Inc. For product information please contact: The MathWorks, Inc. 3 Apple Hill Drive Natick, MA, 01760-2098 USA Tel: 508-647-7000 Fax: 508-647-7001 E-mail: info@mathworks.com Web: www.mathworks.com Every book takes time and care. This book would not have been possible without the loving support of my wife, Janet Taylor, and my son, Kent Zwillinger. May 2017 Daniel Zwillinger ZwillingerBooks@gmail.com "smtf33" — 2017/12/6 — 19:00 — page xiii — #9 Editor-in-Chief Daniel Zwillinger Rensselaer Polytechnic Institute Troy, New York Contributors George E. Andrews Evan Pugh University Professor in Mathematics The Pennsylvania State University University Park, Pennsylvania Lawrence Glasser Professor of Physics Emeritus Clarkson University Potsdam, New York Roger B. Nelsen Professor Emeritus of Mathematics Lewis & Clark College Portland, Oregon Dr. Joseph J. Rushanan MITRE Corporation Bedford, Massachusetts Dr. Les Servi MITRE Corporation Bedford, Massachusetts Michael Mascagni Professor of Computer Science Professor of Mathematics Professor of Scientific Computing Florida State University Tallahassee, Florida Dr. Michael T. Strauss President HME Newburyport, Massachusetts Ray McLenaghan Adjunct Professor in Department of Applied Mathematics University of Waterloo Waterloo, Ontario, Canada Ahmed I. Zayed Professor in Department of Mathematical Sciences DePaul University Chicago, Illinois Dr. Nico M. Temme Centrum Wiskunde & Informatica Amsterdam, The Netherlands xiii "smtf33" — 2017/12/6 — 19:00 — page x — #6 "smtf33" — 2017/12/6 — 19:00 — page 1 — #11 Chapter 1 Numbers and Elementary Mathematics 1.1 PROOFS WITHOUT WORDS . . . . . . . . . . . . . . . . . . . . 3 1.2 CONSTANTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 1.2.2 1.2.3 1.2.4 1.2.5 1.2.6 1.2.7 1.2.8 1.2.9 1.2.10 1.2.11 1.2.12 1.2.13 1.2.14 1.3 Divisibility tests . . . . . . . . . . . . . . . . . . . . . Decimal multiples and prefixes . . . . . . . . . . . . . Binary prefixes . . . . . . . . . . . . . . . . . . . . . Interpretations of powers of 10 . . . . . . . . . . . . . Numerals in different languages . . . . . . . . . . . . . Roman numerals . . . . . . . . . . . . . . . . . . . . Types of numbers . . . . . . . . . . . . . . . . . . . . Representation of numbers . . . . . . . . . . . . . . . Representation of complex numbers – DeMoivre's theorem Arrow notation . . . . . . . . . . . . . . . . . . . . . Ones and Twos Complement . . . . . . . . . . . . . . . Symmetric base three representation . . . . . . . . . . . Hexadecimal addition and subtraction table . . . . . . . Hexadecimal multiplication table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 6 6 7 8 8 9 10 10 11 11 11 12 12 SPECIAL NUMBERS . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3.1 1.3.2 1.3.3 1.3.4 1.3.5 1.3.6 1.3.7 1.3.8 1.3.9 1.3.10 1.3.11 1.3.12 Powers of 2 . . . . . . . . . . . . Powers of 10 in hexadecimal . . . . Special constants . . . . . . . . . Factorials . . . . . . . . . . . . Bernoulli polynomials and numbers Euler polynomials and numbers . . Fibonacci numbers . . . . . . . . Sums of powers of integers . . . . Negative integer powers . . . . . . Integer sequences . . . . . . . . . p-adic Numbers . . . . . . . . . . de Bruijn sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 13 14 16 17 18 18 19 20 21 23 23 1.4 INTERVAL ANALYSIS . . . . . . . . . . . . . . . . . . . . . . . . 24 1.5 FRACTAL ARITHMETIC . . . . . . . . . . . . . . . . . . . . . . 25 1 "smtf33" — 2017/12/6 — 19:00 — page 2 — #12 2 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 1.6 MAX-PLUS ALGEBRA . . . . . . . . . . . . . . . . . . . . . . . 26 1.7 COUPLED-ANALOGUES OF FUNCTIONS . . . . . . . . . . . . 27 1.7.1 1.8 27 NUMBER THEORY . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.8.1 1.8.2 1.8.3 1.8.4 1.8.5 1.8.6 1.8.7 1.8.8 1.8.9 1.8.10 1.8.11 1.8.12 1.9 Coupled-operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Congruences . . . . . . . . . Chinese remainder theorem . . Continued fractions . . . . . . Diophantine equations . . . . Greatest common divisor . . . Least common multiple . . . . Möbius function . . . . . . . . Prime numbers . . . . . . . . Prime numbers of special forms Prime numbers less than 7,000 Factorization table . . . . . . Euler totient function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 29 30 32 35 35 36 37 39 42 44 46 SERIES AND PRODUCTS . . . . . . . . . . . . . . . . . . . . . 47 1.9.1 1.9.2 1.9.3 1.9.4 1.9.5 1.9.6 1.9.7 1.9.8 1.9.9 1.9.10 1.9.11 1.9.12 1.9.13 Definitions . . . . . . . . . . . . . . . . General properties . . . . . . . . . . . . Convergence tests . . . . . . . . . . . . . Types of series . . . . . . . . . . . . . . Fourier series . . . . . . . . . . . . . . . Series expansions of special functions . . . Summation formulas . . . . . . . . . . . Faster convergence: Shanks transformation Summability methods . . . . . . . . . . . Operations with power series . . . . . . . Miscellaneous sums . . . . . . . . . . . . Infinite products . . . . . . . . . . . . . . Infinite products and infinite series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 47 49 50 54 59 63 63 64 64 64 65 65 "smtf33" — 2017/12/6 — 19:00 — page 3 — #13 1.1. PROOFS WITHOUT WORDS 1.1 3 PROOFS WITHOUT WORDS A Property of the Sequence of Odd Integers (Galileo, 1615) The Pythagorean Theorem —the Chou pei suan ching (author unknown, circa B.C. 200?) n(n+1) 1+2+ . . . + n = 2 1 1+3 1+3+5 = = =... 3 5+7 7+9+11 1 1+3+ . . . +(2n–1) = . . . (2n+1)+(2n+3)+ +(4n–1) 3 2 1 + 3 + 5 + . . . + (2n–1) = n 1 1 n(n+1) 1+2+ . . . +n = . n 2 + n . = 2 2 2 —Ian Richards 1+3+ . . . + (2n–1) = 1 (2n) 2 = n 2 4 "smtf33" — 2017/12/6 — 19:00 — page 4 — #14 4 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS Geometric Series Geometric Series ... r2 r2 r r 1–r 1 1 1 1 1 + 4 4 2 + 1 4 3 2 1 + r + r + ... = 1 1 1–r 1 3 + . .. = —Benjamin G. Klein and Irl C. Bivens —Rick Mabry Addition Formulae for the Sine and Cosine The Distance Between a Point and a Line y sinxsiny cosxsiny 2 y sin x (a,ma + c) 1+ m 1 y |ma + c – b| 1 sinxcosy sy co m d (a,b) x x cosxcosy sin(x + y) = sinxcosy + cosxsiny cos(x + y) = cosxcosy – sinxsiny y = mx + c d |ma + c – b| = 1 1 + m2 —R. L. Eisenman "smtf33" — 2017/12/6 — 19:00 — page 5 — #15 1.2. CONSTANTS The Arithmetic Mean-Geometric Mean Inequality a,b > 0 a+b 2 ab 5 The Mediant Property a c a +c < < b b +d d a c < b d c a+b 2 d ab a a b —Charles D. Gallant b a d —Richard A. Gibbs Reprinted from "Proofs Without Words: Exercises in Visual Thinking," by Roger B. Nelsen, 1997, MAA, pages: 3, 40, 49, 60, 70, 72, 115, 120. Copyright The Mathematical Association of America. All rights reserved. Reprinted from "Proofs Without Words II: More Exercises in Visual Thinking," by Roger B. Nelsen, 2001, MAA, pages 46, 111. Copyright The Mathematical Association of America. All rights reserved. 1.2 CONSTANTS 1.2.1 DIVISIBILITY TESTS 1. 2. 3. 4. 5. 6. 7. 8. Divisibility by 2: the last digit is divisible by 2 Divisibility by 3: the sum of the digits is divisible by 3 Divisibility by 4: the number formed from the last 2 digits is divisible by 4 Divisibility by 5: the last digit is either 0 or 5 Divisibility by 6: is divisible by both 2 and 3 Divisibility by 9: the sum of the digits is divisible by 9 Divisibility by 10: the last digit is 0 Divisibility by 11: the difference between the sum of the odd digits and the sum of the even digits is divisible by 11 EXAMPLE Consider the number N = 1036728. • The last digit is 8, so N is divisible by 2. • The last two digits are 28 which is divisible by 4, so N is divisible by 4. • The sum of the digits is 27 = 1 + 0 + 3 + 6 + 7 + 2 + 8. This is divisible by 3, so N is divisible by 3. This is also divisible by 9, so N is divisible by 9. • The sum of the odd digits is 19 = 1 + 3 + 7 + 8 and the sum of the even digits is 8 = 6 + 2; the difference is 19 − 8 = 11. This is divisible by 11, so N is divisible by 11. "smtf33" — 2017/12/6 — 19:00 — page 6 — #16 6 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 1.2.2 DECIMAL MULTIPLES AND PREFIXES The prefix names and symbols below are taken from Conference Générale des Poids et Mesures, 1991. The common names are for the United States. Factor 100 10(10 10100 1024 1021 1 000 000 000 000 000 000 = 1018 1 000 000 000 000 000 = 1015 1 000 000 000 000 = 1012 1 000 000 000 = 109 1 000 000 = 106 1 000 = 103 100 = 102 10 = 101 0.1 = 10−1 0.01 = 10−2 0.001 = 10−3 0.000 001 = 10−6 0.000 000 001 = 10−9 0.000 000 000 001 = 10−12 0.000 000 000 000 001 = 10−15 0.000 000 000 000 000 001 = 10−18 10−21 10−24 1.2.3 Prefix Symbol Common name Y Z E P T G M k H da d c m µ n p f a z y googolplex googol heptillion hexillion quintillion quadrillion trillion billion million thousand hundred ten tenth hundredth thousandth millionth billionth trillionth quadrillionth quintillionth hexillionth heptillionth ) yotta zetta exa peta tera giga mega kilo hecto deka deci centi milli micro nano pico femto atto zepto yocto BINARY PREFIXES A byte is 8 bits. A kibibyte is 210 = 1024 bytes. Other prefixes for power of 2 are: Factor Prefix Symbol 210 220 230 240 250 260 kibi mebi gibi tebi pebi exbi Ki Mi Gi Ti Pi Ei "smtf33" — 2017/12/6 — 19:00 — page 7 — #17 1.2. CONSTANTS 1.2.4 INTERPRETATIONS OF POWERS OF 10 10−43 10−35 10−30 10−27 10−15 10−11 10−10 10−9 10−6 100 101 102 104 105 106 107 108 109 1010 1011 1013 1014 1015 1016 1017 1018 1019 1021 1024 1025 1030 1050 1052 1054 1078 Planck time in seconds Planck length in meters mass of an electron in kilograms mass of a proton in kilograms the radius of the hydrogen nucleus (a proton) in meters the likelihood of being dealt 13 top honors in bridge the (Bohr) radius of a hydrogen atom in meters the number of seconds it takes light to travel one foot the likelihood of being dealt a royal flush in poker the density of water is 1 gram per milliliter the number of fingers that people have the number of stable elements in the periodic table the speed of the Earth around the sun in meters/second the number of hairs on a human scalp the number of words in the English language the number of seconds in a year the speed of light in meters per second the number of heartbeats in a lifetime for most mammals the number of people on the earth the distance from the Earth to the sun in meters diameter of the solar system in meters number of cells in the human body the surface area of the earth in square meters the number of meters light travels in one year the age of the universe in seconds the volume of water in the earth's oceans in cubic meters the number of possible positions of Rubik's cube the volume of the earth in cubic meters the number of grains of sand in the Sahara desert the mass of the earth in kilograms the mass of the sun in kilograms the number of atoms in the earth the mass of the observable universe in kilograms the number of elements in the monster group the volume of the universe in cubic meters (Note: these numbers have been rounded to the nearest power of ten.) 7 "smtf33" — 2017/12/6 — 19:00 — page 8 — #18 8 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 1.2.5 NUMERALS IN DIFFERENT LANGUAGES 1.2.6 ROMAN NUMERALS The major symbols in Roman numerals are I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, and M = 1,000. The rules for constructing Roman numerals are: 1. A symbol following one of equal or greater value adds its value. (For example, II = 2, XI = 11, and DV = 505.) 2. A symbol following one of lesser value has the lesser value subtracted from the larger value. An I is only allowed to precede a V or an X, an X is only allowed to precede an L or a C, and a C is only allowed to precede a D or an M. (For example IV = 4, IX = 9, and XL = 40.) 3. When a symbol stands between two of greater value, its value is subtracted from the second and the result is added to the first. (For example, XIV= 10+(5−1) = 14, CIX= 100+(10−1) = 109, DXL= 500+(50−10) = 540.) 4. When two ways exist for representing a number, the one in which the symbol of larger value occurs earlier in the string is preferred. (For example, 14 is represented as XIV, not as VIX.) Decimal number 1 2 3 4 5 6 7 8 9 Roman numeral I II III IV V VI VII VIII IX 10 14 50 200 400 500 600 999 1000 X XIV L CC CD D DC CMXCIX M 1995 1999 2000 2001 2017 2018 MCMXCV MCMXCIX MM MMI MMXVII MMXVIII "smtf33" — 2017/12/6 — 19:00 — page 9 — #19 1.2. CONSTANTS 1.2.7 9 TYPES OF NUMBERS 1. Natural numbers The set of natural numbers, {0, 1, 2, . . .}, is customarily denoted by N. Many authors do not consider 0 to be a natural number. 2. Integers The set of integers, {0, ±1, ±2, . . .}, is customarily denoted by Z. 3. Rational numbers The set of rational numbers, { pq | p, q ∈ Z, q 6= 0}, is customarily denoted by Q. (a) Two fractions pq and rs are equal if and only if ps = qr. (b) Addition of fractions is defined by pq + rs = ps+qr qs . (c) Multiplication of fractions is defined by pq · rs = pr qs . 4. Real numbers Real numbers are defined to be converging sequences of rational numbers or as decimals that might or might not repeat. The set of real numbers is customarily denoted by R. Real numbers can be divided into two subsets. One subset, the algebraic numbers, are real numbers which solve√a polynomial equation in one variable with integer coefficients. For example; 2 is an algebraic number because it solves the polynomial equation x2 − 2 = 0; and all rational numbers are algebraic. Real numbers that are not algebraic numbers are called transcendental numbers. Examples of transcendental numbers include π and e. 5. Definition of infinity The real numbers are extended to R by the inclusion of +∞ and −∞ with the following definitions (a) (b) (c) for x in R: −∞ < x < ∞ for x in R: x + ∞ = ∞ for x in R: x − ∞ = −∞ (d) for x in R: x x = =0 ∞ −∞ (e) (f) (g) (h) (i) (j) if x > 0 then x · ∞ = ∞ if x > 0 then x·(−∞) = −∞ ∞+∞= ∞ −∞ − ∞ = −∞ ∞·∞= ∞ −∞ · (−∞) = ∞ 6. Complex numbers The set of complex numbers is customarily denoted by C. They are numbers of the form a + bi, where i2 = −1, and a and b are real numbers. Operation addition multiplication computation (a + bi) + (c + di) (a + bi)(c + di) 1 reciprocal a + bi complex conjugate z = a + bi result (a + c) + i(b + d) (ac − bd) + (ad + bc)i a b − i 2 2 2 a +b a + b2 z = a − bi Properties include: z + w = z + w and zw = z w. "smtf33" — 2017/12/6 — 19:00 — page 10 — #20 10 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 1.2.8 REPRESENTATION OF NUMBERS Numerals as usually written have radix or base 10, so the numeral an an−1 . . . a1 a0 represents the number an 10n + an−1 10n−1 + · · · + a2 102 + a1 10 + a0 . However, other bases can be used, particularly bases 2, 8, and 16. When a number is written in base 2, the number is said to be in binary notation. The names of other bases are: 2 binary 6 senary 10 decimal 20 vigesimal 3 ternary 7 septenary 11 undenary 60 sexagesimal 4 quaternary 8 octal 12 duodecimal 5 quinary 9 nonary 16 hexadecimal When writing a number in base b, the digits used range from 0 to b − 1. If b > 10, then the digit A stands for 10, B for 11, etc. When a base other than 10 is used, it is indicated by a subscript: 101112 = 1 × 24 + 0 × 23 + 1 × 22 + 1 × 2 + 1 = 23, A316 = 10 × 16 + 3 = 163, (1.2.1) 2 5437 = 5 × 7 + 4 × 7 + 3 = 276. To convert a number from base 10 to base b, divide the number by b, and the remainder will be the last digit. Then divide the quotient by b, using the remainder as the previous digit. Continue this process until a quotient of 0 is obtained. EXAMPLE To convert 573 to base 12, divide 573 by 12, yielding a quotient of 47 and a remainder of 9; hence, "9" is the last digit. Divide 47 by 12, yielding a quotient of 3 and a remainder of 11 (which we represent with a "B"). Divide 3 by 12 yielding a quotient of 0 and a remainder of 3. Therefore, 57310 = 3B912 . Converting from base b to base r can be done by converting to and from base 10. However, it is simple to convert from base b to base bn . For example, to convert 1101111012 to base 16, group the digits in fours (because 16 is 24 ), yielding 1 1011 11012, and then convert each group of 4 to base 16 directly, yielding 1BD16 . 1.2.9 REPRESENTATION OF COMPLEX NUMBERS – DEMOIVRE'S THEOREM A complex number a + bi can be written in the form reiθ , where r2 = a2 + b2 and tan θ = b/a. Because eiθ = cos θ + i sin θ, (a + bi)n = rn (cos nθ + i sin nθ), √ 2kπ 2kπ n + i sin , 1 = cos n n √ (2k + 1)π (2k + 1)π n −1 = cos + i sin , n n k = 0, 1, . . . , n − 1. (1.2.2) k = 0, 1, . . . , n − 1. "smtf33" — 2017/12/6 — 19:00 — page 11 — #21 1.2. CONSTANTS 11 1.2.10 ARROW NOTATION Arrow notation is used to represent large numbers. Start with m ↑ n = |m · m {z· · · m}, then (evaluation proceeds from the right) m ↑↑ n = m ↑ m ↑ · · · ↑ m {z } | n n m ↑↑↑ n = m ↑↑ m ↑↑ · · · ↑↑ m | {z } n For example, m ↑ n = m , m ↑↑ 2 = m , and m ↑↑ 3 = m n m (mm ) . 1.2.11 ONES AND TWOS COMPLEMENT One's and two's complement are ways to represent numbers in a computer. For positive values the binary representation, the ones' complement representation, and the twos' complement representation are the same. • Ones' complement represents integers from − 2N −1 − 1 to 2N −1 − 1. For negative values, the binary representation of the absolute value is obtained, and then all of the bits are inverted (i.e., swapping 0's for 1's and vice versa). • Twos' complement represents integers from −2N −1 to 2N −1 − 1. For negative vales, the two's complement representation is the same as the value one added to the ones' complement representation. Number 7 6 5 4 3 2 1 0 −0 −1 −2 −3 −4 −5 −6 −7 −8 Ones' complement 0111 0110 0101 0100 0011 0010 0001 0000 1111 1110 1101 1100 1011 1010 1001 1000 Twos' complement 0111 0110 0101 0100 0011 0010 0001 0000 1111 1110 1101 1100 1011 1010 1001 1000 1.2.12 SYMMETRIC BASE THREE REPRESENTATION In the symmetric base three representation, powers of 3 are added and subtracted to represent numbers; the symbols {↓, 0, ↑} represent {−1, 0, 1}. For example, one writes ↑↓↓ for 5 since 5 = 9−3−1. To negate a number in symmetric base three, turn its symbol upside down, e.g., −5 =↓↑↑. Basic arithmetic operations are especially simple in this base. "smtf33" — 2017/12/6 — 19:00 — page 12 — #22 12 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 1.2.13 HEXADECIMAL ADDITION AND SUBTRACTION TABLE A = 10, B = 11, C = 12, D = 13, E = 14, F = 15. Example: 6 + 2 = 8; hence 8 − 6 = 2 and 8 − 2 = 6. Example: 4 + E = 12; hence 12 − 4 = E and 12 − E = 4. 1 2 3 4 5 6 7 8 9 A B C D E F 1 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 2 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11 3 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11 12 4 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 5 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 14 6 07 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 14 15 7 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 14 15 16 8 09 0A 0B 0C 0D 0E 0F 10 11 12 13 14 15 16 17 9 0A 0B 0C 0D 0E 0F 10 11 12 13 14 15 16 17 18 A 0B 0C 0D 0E 0F 10 11 12 13 14 15 16 17 18 19 B 0C 0D 0E 0F 10 11 12 13 14 15 16 17 18 19 1A C 0D 0E 0F 10 11 12 13 14 15 16 17 18 19 1A 1B D 0E 0F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C E 0F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E C 0C 18 24 30 3C 48 54 60 6C 78 84 90 9C A8 B4 D 0D 1A 27 34 41 4E 5B 68 75 82 8F 9C A9 B6 C3 E 0E 1C 2A 38 46 54 62 70 7E 8C 9A A8 B6 C4 D2 F 0F 1E 2D 3C 4B 5A 69 78 87 96 A5 B4 C3 D2 E1 1.2.14 HEXADECIMAL MULTIPLICATION TABLE Example: 2 × 4 = 8. Example: 2 × F = 1E. 1 2 3 4 5 6 7 8 9 A B C D E F 1 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 2 02 04 06 08 0A 0C 0E 10 12 14 16 18 1A 1C 1E 3 03 06 09 0C 0F 12 15 18 1B 1E 21 24 27 2A 2D 4 04 08 0C 10 14 18 1C 20 24 28 2C 30 34 38 3C 5 05 0A 0F 14 19 1E 23 28 2D 32 37 3C 41 46 4B 6 06 0C 12 18 1E 24 2A 30 36 3C 42 48 4E 54 5A 7 07 0E 15 1C 23 2A 31 38 3F 46 4D 54 5B 62 69 8 08 10 18 20 28 30 38 40 48 50 58 60 68 70 78 9 09 12 1B 24 2D 36 3F 48 51 5A 63 6C 75 7E 87 A 0A 14 1E 28 32 3C 46 50 5A 64 6E 78 82 8C 96 B 0B 16 21 2C 37 42 4D 58 63 6E 79 84 8F 9A A5 "smtf33" — 2017/12/6 — 19:00 — page 13 — #23 1.3. SPECIAL NUMBERS 1.3 SPECIAL NUMBERS 1.3.1 POWERS OF 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 1.3.2 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 0.5 0.25 0.125 0.0625 0.03125 0.015625 0.0078125 0.00390625 0.001953125 0.0009765625 0.00048828125 0.000244140625 0.0001220703125 0.00006103515625 0.000030517578125 0.0000152587890625 0.00000762939453125 0.000003814697265625 0.0000019073486328125 0.00000095367431640625 0.000000476837158203125 0.0000002384185791015625 0.00000011920928955078125 0.000000059604644775390625 0.0000000298023223876953125 POWERS OF 10 IN HEXADECIMAL n 0 1 2 3 4 5 6 7 8 9 10 10n 10−n 116 A 16 64 16 3E8 16 2710 16 186A0 16 F4240 16 989680 16 5F5E100 16 3B9ACA00 16 2540BE400 16 116 0.19999999999999999999. . .16 0.028F5C28F5C28F5C28F5. . .16 0.004189374BC6A7EF9DB2. . .16 0.00068DB8BAC710CB295E. . .16 0.0000A7C5AC471B478423. . .16 0.000010C6F7A0B5ED8D36. . .16 0.000001AD7F29ABCAF485. . .16 0.0000002AF31DC4611873. . .16 0.000000044B82FA09B5A5. . .16 0.000000006DF37F675EF6. . .16 13 "smtf33" — 2017/12/6 — 19:00 — page 14 — #24 14 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 1.3.3 SPECIAL CONSTANTS 1.3.3.1 The constant π The transcendental number π is defined as the ratio of the circumference of a circle to the diameter. It is also the ratio of the area of a circle to the square of the radius (r) and appears in several formulas in geometry and trigonometry circumference of a circle = 2πr, area of a circle = πr2 , 4 3 πr , 3 surface area of a sphere = 4πr2 . volume of a sphere = One method of computing π is to use the infinite series for the function tan−1 x and one of the identities 1 π = 4 tan−1 1 = 6 tan−1 √ 3 1 1 1 1 = 2 tan−1 + 2 tan−1 + 8 tan−1 − 2 tan−1 2 3 5 239 −1 1 −1 1 −1 1 + 8 tan + 4 tan = 24 tan 8 57 239 1 −1 1 −1 1 + 32 tan − 20 tan−1 = 48 tan 18 57 239 (1.3.1) There are many identities involving π. For example: ∞ X 4 2 1 1 1 − − − π= 16i 8i + 1 8i + 4 8i + 5 8i + 6 i=0 v v u v u u v u u s u u u r u u u q u u u t √ t t kt π = lim 2 2 − 2 + 2 + 2 + 2 + 2 + ···+ 2 + 2 k→∞ ∞ Y 2 = π k=1 ∞ X z s | 2+ {z k square roots k square roots { q √ 2 + ···+ 2 + 2 r }| } 2 (−1)n 1 1 1 π3 =1− = + − + ... 32 n=0 (2n + 1)3 27 125 343 To 100 decimal places: π ≈ 3. 14159 26535 89793 23846 26433 83279 50288 41971 69399 37510 58209 74944 59230 78164 06286 20899 86280 34825 34211 70679 "smtf33" — 2017/12/6 — 19:00 — page 15 — #25 1.3. SPECIAL NUMBERS 15 In different bases: π ≈ 11.00100100001111110110101010001000100001011010001. . . 2 π ≈ 3.11037552421026430215142306305056006701632112201. . . 8 π ≈ 3.243F6A8885A308D313198A2E03707344A4093822299F. . . 16 To 50 decimal places: π/8 ≈ 0.39269 90816 98724 15480 78304 22909 93786 05246 46174 92189 π/4 ≈ 0.78539 81633 97448 30961 56608 45819 87572 10492 92349 84378 π/3 ≈ 1.04719 75511 96597 74615 42144 61093 16762 80657 23133 12504 π/2 √ ≈ 1.57079 63267 94896 61923 13216 91639 75144 20985 84699 68755 π ≈ 1.77245 38509 05516 02729 81674 83341 14518 27975 49456 12239 In 2016 π was computed to 12.1 trillion decimal digits. The frequency counts of the digits for π − 3, using 1 trillion decimal places, are: digit 0: digit 1: digit 2: digit 3: digit 4: 1.3.3.2 99999485134 99999945664 100000480057 99999787805 100000357857 digit 5: digit 6: digit 7: digit 8: digit 9: 99999671008 99999807503 99999818723 100000791469 99999854780 The constant e The transcendental number e is the base of natural logarithms. It is given by n X ∞ 1 1 = . (1.3.2) e = lim 1 + n→∞ n n! n=0 e ≈ 2.71828 18284 59045 23536 02874 71352 66249 77572 47093 69995 95749 66967 62772 40766 30353 54759 45713 82178 52516 64274 . . . In different bases: e ≈ 10.10110111111000010101000101100010100010101110110. . . 2 e ≈ 2.55760521305053551246527734254200471723636166134. . . 8 e ≈ 2.B7E151628AED2A6ABF7158809CF4F3C762E7160F3. . . 16 ∞ X xn The exponential function is e = . Euler's formula relates e and π: eπi = −1 n! n=0 x 1.3.3.3 The constant γ Euler's constant γ is defined by γ = lim n→∞ ! n X 1 − log n . k (1.3.3) k=1 It is not known whether γ is rational or irrational. γ ≈ 0.57721 56649 01532 86060 65120 90082 40243 10421 59335 93992 35988 05767 23488 48677 26777 66467 09369 47063 29174 67495 . . . "smtf33" — 2017/12/6 — 19:00 — page 16 — #26 16 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 1.3.3.4 The constant φ φ 1 1+φ φ or φ = φ+1; that is φ = There is the continued faction representation φ = 1 and the representation in square roots s r q √ φ = 1+ 1 + 1 + 1 + ... The golden ratio, φ, is defined as the positive root of the equation √ 1+ 5 2 . 2 = φ ≈ 1.61803 39887 49894 84820 45868 34365 63811 77203 09179 80576 . . . 1.3.4 FACTORIALS The factorial of n, denoted n!, is the product of all positive integers less than or equal to n; n! = n · (n − 1) · (n − 2) · · · 2 · 1. By definition, 0! = 1. If n is a negative integer (n = −1, −2, . . . ) then n! = ±∞. The generalization of the factorial function to non-integer arguments is the gamma function (see page 478); when n is an integer, Γ(n) = (n − 1)!. The double factorial of n is denoted by n!! and is defined as n!! = n(n − 2)(n − 4) · · · , where the last term in the product is 2 or 1, depending on whether n is even or odd. The shifted factorial (also called Pochhammer's symbol) is denoted by (a)n and is defined as (a + n − 1)! Γ(a + n) (a)n = a · (a + 1) · (a + 2) · · · (a + n − 1) = = (1.3.4) {z } | (a − 1)! Γ(a) n terms Approximations to n! for large n include Stirling's formula (the first term of the following) n n+ 12 √ 1 1 n! ≈ 2πe 1+ + + ... (1.3.5) e 12n 288n2 and Burnside's formula n+ 12 √ n + 12 n! ≈ 2π (1.3.6) e n n! log10 n! n!! log10 n!! 0 1 2 3 4 5 6 7 8 9 10 1 1 2 6 24 120 720 5040 40320 3.6288 × 105 3.6288 × 106 0.00000 0.00000 0.30103 0.77815 1.38021 2.07918 2.85733 3.70243 4.60552 5.55976 6.55976 1 1 2 3 8 15 48 105 384 945 3840 0.00000 0.00000 0.30103 0.47712 0.90309 1.17609 1.68124 2.02119 2.58433 2.97543 3.58433 "smtf33" — 2017/12/6 — 19:00 — page 17 — #27 1.3. SPECIAL NUMBERS n 20 30 40 50 60 70 80 90 100 150 500 1000 1.3.5 n! log10 n! 18 2.4329 × 10 2.6525 × 1032 8.1592 × 1047 3.0414 × 1064 8.3210 × 1081 1.1979 × 10100 7.1569 × 10118 1.4857 × 10138 9.3326 × 10157 5.7134 × 10262 1.2201 × 101134 4.0239 × 102567 n!! log10 n!! 9 3.7159 × 10 4.2850 × 1016 2.5511 × 1024 5.2047 × 1032 2.8481 × 1041 3.5504 × 1050 8.9711 × 1059 4.2088 × 1069 3.4243 × 1079 9.3726 × 10131 5.8490 × 10567 3.9940 × 101284 18.38612 32.42366 47.91165 64.48307 81.92017 100.07841 118.85473 138.17194 157.97000 262.75689 1134.0864 2567.6046 17 9.57006 16.63195 24.40672 32.71640 41.45456 50.55028 59.95284 69.62416 79.53457 131.97186 567.76709 1284.6014 BERNOULLI POLYNOMIALS AND NUMBERS The Bernoulli polynomials Bn (x) are defined by the generating function ∞ X text tn = B (x) . n et − 1 n=0 n! (1.3.7) These polynomials can be defined recursively by B0 (x) = 1, Bn′ (x) = nBn−1 (x), R1 and 0 Bn (x) dx = 0 for n ≥ 1. The identity Bk+1 (x + 1) − Bk+1 (x) = (k + 1)xk means that sums of powers can be computed via Bernoulli polynomials 1 k + 2 k + · · · + nk = Bk+1 (n + 1) − Bk+1 (0) . k+1 (1.3.8) The Bernoulli numbers are the Bernoulli polynomials evaluated at 0: Bn = Bn (0). ∞ X t tn = t . In the A generating function for the Bernoulli numbers is Bn n! e − 1 n=0 following table each Bernoulli number is written as a fraction of integers: Bn = Nn /Dn . Note that B2m+1 = 0 for m ≥ 1. n 0 1 2 3 4 5 Bn (x) 1 (2x − 1)/2 (6x2 − 6x + 1)/6 (2x3 − 3x2 + x)/2 4 (30x − 60x3 + 30x2 − 1)/30 (6x5 − 15x4 + 10x3 − x)/6 n Nn Dn 0 1 2 4 6 8 10 1 −1 1 −1 1 −1 5 1 2 6 30 42 30 66 Bn 1.00000 × 100 −5.00000 × 10−1 1.66667 × 10−1 −3.33333 × 10−2 2.38095 × 10−2 −3.33333 × 10−2 7.57576 × 10−2 "smtf33" — 2017/12/6 — 19:00 — page 18 — #28 18 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 1.3.6 EULER POLYNOMIALS AND NUMBERS The Euler polynomials En (x) are defined by the generating function ∞ X 2ext tn = E (x) . n et + 1 n=0 n! (1.3.9) Alternating sums of powers can be computed in terms of Euler polynomials n X Ek (n + 1) + (−1)n Ek (0) . 2 i=1 (1.3.10) The Euler numbers are defined as En = 2n En ( 12 ). A generating function is (−1)n−i ik = nk − (n − 1)k + · · · ∓ 2k ± 1k = ∞ X En n=0 n 0 1 2 3 4 5 1.3.7 tn 2et = 2t n! e +1 En (x) 1 (2x − 1)/2 x2 − x 3 (4x − 6x2 + 1)/4 x4 − 2x3 + x 5 (2x − 5x4 + 5x2 − 1)/2 (1.3.11) n 2 4 6 8 10 12 En −1 5 −61 1385 −50521 2702765 FIBONACCI NUMBERS The Fibonacci numbers {Fn } are defined by the recurrence: F1 = 1, F2 = 1, Fn+2 = Fn + Fn+1 . (1.3.12) An exact formula is available (see page 186): " √ !n √ !n # 1+ 5 1− 5 1 Fn = √ − (1.3.13) 2 2 5 √ Note that Fn is the integer nearest to φn / 5 as n → ∞, where φ is the golden ratio. n 1 2 3 4 5 6 7 8 9 10 Fn 1 1 2 3 5 8 13 21 34 55 n 11 12 13 14 15 16 17 18 19 20 Fn 89 144 233 377 610 987 1597 2584 4181 6765 n 21 22 23 24 25 26 27 28 29 30 Fn 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 n 31 32 33 34 35 36 37 38 39 40 Fn 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 "smtf33" — 2017/12/6 — 19:00 — page 19 — #29 1.3. SPECIAL NUMBERS 1.3.8 19 SUMS OF POWERS OF INTEGERS 1. Define the sum of the first n k th -powers sk (n) = 1k + 2k + · · · + nk = n X mk . (1.3.14) m=1 (a) sk (n) = (k + 1)−1 [Bk+1 (n + 1) − Bk+1 (0)] (where the Bk are Bernoulli polynomials, see Section 1.3.5). Pk+1 (b) If sk (n) = m=1 am nk−m+2 , then k+1 k+1 k+2 a1 n + ··· + a3 nk sk+1 (n) = k+2 k " # k+1 X am k+1 2 ak+1 n + 1 − (k + 1) n. + ···+ 2 k+3−m m=1 (c) Note the specific values 1 n(n + 1) 2 1 s2 (n) = 12 + 22 + 32 + · · · + n2 = n(n + 1)(2n + 1) 6 1 s3 (n) = 13 + 23 + 33 + · · · + n3 = n2 (n + 1)2 = [s1 (n)]2 4 1 4 4 4 4 s4 (n) = 1 + 2 + 3 + · · · + n = (3n2 + 3n − 1)s2 (n) 5 1 2 5 5 5 5 s5 (n) = 1 + 2 + 3 + · · · + n = n (n + 1)2 (2n2 + 2n − 1) 12 s1 (n) = 1 + 2 + 3 + · · · + n = 2. 3. n X (km − 1) = k=1 n X (km − 1)2 = k=1 4. 5. 1 mn(n + 1) − n 2 n X n 2 m (n + 1)(2n + 1) − 6m(n + 1) + 6 6 (−1)k+1 (km − 1) = k=1 n X (−1)n m−2 [2 − (2n + 1)m] + 4 4 (−1)k+1 (km − 1)2 = (−1)n+1 2 k=1 n 1 2 3 4 5 n X k=1 k 1 3 6 10 15 n X k=1 k2 1 5 14 30 55 n(n + 1)m2 − (2n + 1)m + 1 + n X k=1 k3 1 9 36 100 225 n X k=1 k4 1 17 98 354 979 n X k=1 k5 1 33 276 1300 4425 1−m 2 "smtf33" — 2017/12/6 — 19:00 — page 20 — #30 20 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 1.3.9 NEGATIVE INTEGER POWERS Riemann's zeta function is defined to be ζ(n) = and extended to C). Related functions are α(n) = ∞ X (−1)k+1 k=1 kn , β(n) = ∞ X k=0 P∞ 1 k=1 kn (−1)k , (2k + 1)n (it is defined for Re n > 1 γ(n) = ∞ X k=0 1 . (2k + 1)n Properties include: 1. α(n) = (1 − 21−n )ζ(n) 2. ζ(2k) = 3. γ(n) = (1 − 2−n )ζ(n) (2π)2k |B2k | 2(2k)! 5. The series β(1) = 1 − 4. β(2k + 1) = 1 3 + 1 5 (π/2)2k+1 |E2k | 2(2k)! − · · · = π/4 is known as Gregory's series. 6. Catalan's constant is G = β(2) ≈ 0.915966. 7. Riemann hypothesis: The non-trivial zeros of the Riemann zeta function (i.e., the {zi } that satisfy ζ(zi ) = 0) lie on the critical line given by Re zi = 21 . (The trivial zeros are z = −2, −4, −6, . . . .) n ζ(n) = ∞ X 1 kn k=1 1 2 3 4 5 6 7 8 9 10 ∞ 1.6449340668 1.2020569032 1.0823232337 1.0369277551 1.0173430620 1.0083492774 1.0040773562 1.0020083928 1.0009945751 ∞ X (−1)k+1 k=1 kn 0.6931471805 0.8224670334 0.9015426773 0.9470328294 0.9721197705 0.9855510912 0.9925938199 0.9962330018 0.9980942975 0.9990395075 β(1) = π/4 β(3) = π 3 /32 β(5) = 5π 5 /1536 β(7) = 61π 7 /184320 β(9) = 277π 9 /8257536 ∞ X k=0 (−1)k (2k + 1)n 0.7853981633 0.9159655941 0.9689461463 0.9889445517 0.9961578281 0.9986852222 0.9995545079 0.9998499902 0.9999496842 0.9999831640 ∞ X k=0 1 (2k + 1)n ∞ 1.2337005501 1.0517997903 1.0146780316 1.0045237628 1.0014470766 1.0004715487 1.0001551790 1.0000513452 1.0000170414 ζ(2) = π 2 /6 ζ(4) = π 4 /90 ζ(6) = π 6 /945 ζ(8) = π 8 /9450 ζ(10) = π 10 /93555 "smtf33" — 2017/12/6 — 19:00 — page 21 — #31 1.3. SPECIAL NUMBERS 21 1.3.10 INTEGER SEQUENCES These sequences are in numerical order (disregarding leading zeros or ones). 1. 1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0, −1, 1, 1, 0, −1, 0, −1, 0, 1, 1, −1, 0, 0, 1, 0, 0, −1, −1, −1, 0, 1, 1, 1, 0, −1, 1, 1, 0, −1, −1, −1, 0, 0, 1, −1, 0, 0, 0, 1, 0, −1, 0, 1, 0 Möbius function µ(n), n ≥ 1 2. 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 2, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 2, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 0 Number of ways of writing n as a sum of 2 squares, n ≥ 0 3. 1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 5, 1, 2, 1, 2, 1, 1, 1, 3, 2, 1, 3, 2, 1, 1, 1, 7, 1, 1, 1, 4, 1, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 5, 2, 2, 1, 2, 1, 3, 1, 3, 1, 1, 1, 2, 1, 1, 2, 11, 1, 1, 1, 2 Number of Abelian groups of order n, n ≥ 1 4. 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51, 1, 2, 1, 14, 1, 2, 2, 14, 1, 6, 1, 4, 2, 2, 1, 52, 2, 5, 1, 5, 1, 15, 2, 13, 2, 2, 1, 13, 1, 2, 4, 267 Number of groups of order n, n ≥ 1 5. 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2 Number of 1's in binary expansion of n, n ≥ 0 6. 1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630, 1161, 2182, 4080, 7710, 14532, 27594, 52377, 99858, 190557, 364722, 698870, 1342176, 2580795, 4971008 Number of binary irreducible polynomials of degree n, or n-bead necklaces, n ≥ 0 7. 1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, 3, 4, 4, 6, 2, 8, 2, 6, 4, 4, 4, 9, 2, 4, 4, 8, 2, 8, 2, 6, 6, 4, 2, 10, 3, 6, 4, 6, 2, 8, 4, 8, 4, 4, 2, 12, 2, 4, 6, 7, 4, 8, 2, 6 d(n), the number of divisors of n, n ≥ 1 8. 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64, 76, 89, 104, 122, 142, 165, 192, 222, 256, 296, 340, 390, 448, 512, 585, 668, 760, 864, 982, 1113, 1260, 1426 Number of partitions of n into distinct parts, n ≥ 1 9. 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42 Euler totient function φ(n): count numbers ≤ n and prime to n, for n ≥ 1 10. 1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 121, 125, 127, 128, 131 Powers of prime numbers 11. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 60, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 168, 173 Orders of simple groups 12. 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883 Number of partitions of n, n ≥ 1 13. 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433 Mersenne primes: n such that 2n − 1 is prime 14. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269 Fibonacci numbers: F (n) = F (n − 1) + F (n − 2) "smtf33" — 2017/12/6 — 19:00 — page 22 — #32 22 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 15. 1, 2, 3, 6, 10, 20, 35, 70, 126, 252, 462, 924, 1716, 3432, 6435, 12870, 24310, 48620, 92378, 184756, 352716, 705432, 1352078, 2704156, 5200300, 10400600, 20058300 Central binomial coefficients: C(n, ⌊n/2⌋), n ≥ 1 16. 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, 7741, 19320, 48629, 123867, 317955, 823065, 2144505, 5623756, 14828074, 39299897, 104636890, 279793450 Number of trees with n unlabeled nodes, n ≥ 1 17. 0, 0, 1, 1, 2, 3, 7, 21, 49, 165, 552, 2176, 9988 Number of prime knots with n crossings, n ≥ 1 18. 0, 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, 29, 32, 34, 36, 37, 40, 41, 45, 49, 50, 52, 53, 58, 61, 64, 65, 68, 72, 73, 74, 80, 81, 82, 85, 89, 90, 97, 98, 100, 101, 104, 106 Numbers that are sums of 2 squares 19. 1, 2, 4, 6, 10, 14, 20, 26, 36, 46, 60, 74, 94, 114, 140, 166, 202, 238, 284, 330, 390, 450, 524, 598, 692, 786, 900, 1014, 1154, 1294, 1460, 1626, 1828, 2030, 2268, 2506 Binary partitions (partitions of 2n into powers of 2), n ≥ 0 20. 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864 Powers of 2 21. 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847, 1721159, 4688676, 12826228, 35221832, 97055181, 268282855, 743724984, 2067174645 Number of rooted trees with n unlabeled nodes, n ≥ 1 22. 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, 158808, 531469, 1799659, 6157068, 21258104, 73996100, 259451116, 951695102, 3251073303 Number of different scores in n-team round-robin tournament, n ≥ 1 23. 1, 1, 2, 5, 12, 35, 108, 369, 1285, 4655, 17073, 63600, 238591, 901971, 3426576, 13079255, 50107909, 192622052, 742624232, 2870671950, 11123060678, 43191857688 Polyominoes with n cells, n ≥ 1 24. 1, 1, 2, 5, 14, 38, 120, 353, 1148, 3527, 11622, 36627, 121622, 389560, 1301140, 4215748, 13976335, 46235800, 155741571, 512559185, 1732007938, 5732533570 Number of ways to fold a strip of n blank stamps, n ≥ 1 25. 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, 32071101049, 481066515734, 7697064251745, 130850092279664 Derangements: permutations of n elements with no fixed points 26. 1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20, 42, 32, 36, 24, 60, 31, 42, 40, 56, 30, 72, 32, 63, 48, 54, 48, 91, 38, 60, 56, 90, 42, 96, 44, 84, 78, 72, 48, 124 σ(n), sum of the divisors of n, n ≥ 1 27. 1, 3, 4, 7, 9, 12, 13, 16, 19, 21, 25, 27, 28, 31, 36, 37, 39, 43, 48, 49, 52, 57, 61, 63, 64, 67, 73, 75, 76, 79, 81, 84, 91, 93, 97, 100, 103, 108, 109, 111, 112, 117, 121, 124, 127 Numbers of the form x2 + xy + y 2 28. 1, 20, 400, 8902, 197281, 4865609, 119060324, 3195901860, 84998978956, 2439530234167 Number of possible chess games at the end of the nth ply. 29. 1, 362, 130683, 47046243, 16889859363, 6046709375131 Number of Go games with n moves. For information on these and hundreds of thousands of other sequences, see "The On-Line Encyclopedia of Integer Sequences," at oeis.org. "smtf33" — 2017/12/6 — 19:00 — page 23 — #33 1.3. SPECIAL NUMBERS 23 1.3.11 p-ADIC NUMBERS a n p where n b is an integer and p does not divide a or b. Define the p-adic norm of x as |x|p = p−n and also define |0|p = 0. The p-adic norm has the properties: Given a prime p, a non-zero rational number x can be written as x = 1. |x|p ≥ 0 for all non-negative rational numbers x 2. |x|p = 0 if and only if x = 0 3. For all non-negative rational numbers x and y (a) |xy|p = |x|p |y|p (b) |x + y|p ≤ max (|x|p , |y|p ) ≤ |x|p + |y|p Q Note the product formula: |x| p∈{2,3,5,7,11,... } |x|p = 1. Let Qp be the topological completion of Q with respect to | · |p . Then Qp is the field ofPp-adic numbers. The elements of Qp can be viewed as infinite series: the ∞ series n=0 an converges to a point in Qp if and only if limn→∞ |an |p = 0. EXAMPLE • 140 297 2 • 140 297 3 The number 140 297 = 22 · 3−3 · 5 · 7 · 11−1 has the different p-adic norms: 1 4 • 140 297 5 = 33 = 27 • 140 297 7 = 2−2 = = 5−1 = = 7−1 = 1 5 • 140 297 = 111 = 11 11 1 7 1.3.12 DE BRUIJN SEQUENCES A sequence of length q n over an alphabet of size q is a de Bruijn sequence if every possible n-tuple occurs in the sequence (allowing wraparound to the start of the sen−1 quence). There are de Bruijn sequences for any q and n. (In fact, there are q!q /q! distinct sequences.) The table below contains some small examples. q 2 2 2 2 3 3 4 n 1 2 3 4 2 3 2 Length 2 4 8 16 9 27 16 Sequence 01 0110 01110100 0101001101111000 001220211 000100201101202102211121222 0011310221203323 "smtf33" — 2017/12/6 — 19:00 — page 24 — #34 24 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 1.4 INTERVAL ANALYSIS 1. Definitions (a) An interval x is a subset of the real line: x = [x, x] = {z ∈ R | x ≤ z ≤ x}. (b) A thin interval is a real number: x is thin if x = x x+x (e) |x| = mag(x) = max |z| (c) mid(x) = z∈x 2 x−x (f) hxi = mig(x) = min |z| (d) rad(x) = z∈x 2 The MATLAB R package INTLAB performs interval computations. 2. Interval arithmetic rules Operation Rule x + y, x + y x+y x−y x − y, x − y xy min(xy, xy, xy, xy), max(xy, xy, xy, xy) x y h i min xy , xy , xy , xy , max xy , xy , xy , xy ) if 0 6∈ y 3. Interval arithmetic properties Property + and − ∗ and / commutative x+y =y+x xy = yx associative x + (y + z) = (x + y) + z x(yz) = (xy)z identity elements 0+x=x+0=x 1∗y =y∗1=y sub-distributivity x(y ± z) ⊆ xy ± xz sub-cancellation x − y ⊆ (x + z) − (y + z) 4. Examples 0∈x−x (a) [1, 2] + [−2, 1] = [−1, 3] (b) [1, 2] − [1, 2] = [−1, 1] (equality holds if x is thin) x y ⊆ 1∈ xz yz y y (c) [1, 2] ∗ [−2, 1] = [−4, 2] (d) [1, 2]/[1, 2] = 12 , 2 (e) If f (a, b; x) = ax + b then (when a = [1, 2], b = [5, 7], and x = [2, 3]); f ([1, 2], [5, 7]; [2, 3]) = [1, 2]·[2, 3]+[5, 7] = [1·2, 2·3]+[5, 7] = [7, 13] "smtf33" — 2017/12/6 — 19:00 — page 25 — #35 1.5. FRACTAL ARITHMETIC 1.5 25 FRACTAL ARITHMETIC Given a real-valued bijection f with f (0) = 0 and f (1) = 1 define x ⊕ y = f −1 (f (x) + f (y)) x ⊙ y = f −1 (f (x)f (y)) x ⊖ y = f −1 (f (x) − f (y)) (1.5.1) x ⊘ y = f −1 (f (x)/f (y)) 1/q For example, if f (x) = xq then x ⊙ y = xy and x ⊕ y = (xq + y q ) the following hold: . Note that • Associativity: (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z) and (x ⊙ y) ⊙ z = x ⊙ (y ⊙ z) • Commutativity: x ⊕ y = y ⊕ x and x ⊙ y = y ⊙ x • Distributivity: (x ⊕ y) ⊙ z = (x ⊙ z) ⊕ (y ⊙ z) The elements 0 and 1 satisfy 0 ⊕ x = x and 1 ⊙ x = x. 1. x ⊖ x = 0 and x ⊘ x = 1. 2. In general, x ⊕ x 6= 2 ⊙ x. 3. If 0 ⊖ x exists, it is denoted as ⊖x Define derivative and integration operations: df A(x) = lim (A(x ⊕ h) ⊖ A(x)) ⊘ h h→0 df x ! Z b Z f (b) −1 Ff (x) ⊙ df x = f F (y) dy a (1.5.2) f (a) so that df (A(x)) df (B(x)) df (A(x) ⊙ B(x)) = ⊙ B(x) ⊕ A(x) ⊙ 1. df x df x df x df (A(x) ⊕ B(x)) df (A(x)) df (B(x)) 2. = ⊕ df x df x df x df (A[B(x)]) df (B(x)) df (A[B(x)]) = ⊙ 3. d x df B(x) df x Z b f df A(x) 4. ⊙ df x = A(b) ⊖ A(a) d x a Z fb df 5. A(x′ ) ⊙ df x′ = A(x) df x a df Ff (x) = f −1 (F ′ (f (x))) 6. df x Special functions Given a function F define Ff as Ff (x) = f −1 (F (f (x))). 1. The expf function satisfies expf (x ⊕ y) = expf x ⊙ expf y and is the unique d A(x) solution to the differential equation fdf x = A(x) with A(0) = 1. 2. The lnf function satisfies lnf (x ⊙ y) = lnf x ⊕ lnf y "smtf33" — 2017/12/6 — 19:00 — page 26 — #36 26 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 1.6 MAX-PLUS ALGEBRA The max-plus algebra is an algebraic structure with real numbers and two operations (called "plus" and "times"); "plus" is the operation of taking a maximum, and "times" is the "standard addition" operation. Mathematically: The max-plus semiring Rmax is the set R ∪ {−∞} with two operations called "plus" (⊕) and "times" (⊗) defined as follows: • a ⊕ b = max(a, b) • a⊗b=a+b For a and b in Rmax the following laws apply: 1. Associativity 2. Commutativity • (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c) • (a ⊗ b) ⊗ c = a ⊗ (b ⊗ c) 3. Distributivity: 4. Idempotency of ⊕ : • a⊕b=b⊕a • a⊗b=b⊗a (a ⊕ b) ⊗ c = a ⊗ c ⊕ b ⊗ c a⊕a=a Special elements are the "zero element" ǫ = −∞ and and the "unit element" e = 0. These have the properties: • ǫ⊕a=a • ǫ⊗a=ǫ • e⊗a=a Let A and B be matrices and let [C]ij be the ij th element of matrix C. Then • [A ⊕ B]ij = [A]ij ⊕ [B]ij = max([A]ij , [B]ij ) when A and BLhave the same size p • [A ⊗ B]ij = k=1 ([A]ik ⊗ [B]kj ) = max([A]i1 + [B]1j , . . . , [A]ip + [B]pj ) when A has p columns and B has p rows. Notes 1. Rmax is not a group since not all elements have an additive inverse. (Only one element has an additive inverse, it is −∞.) 2. The equation a ⊕ x = b need not have a unique solution. • If a < b, then x = b • If a = b, then x can be any value with x ≤ b • If a > b, then there is no solution 3. In Rmax matrix multiplication is associative. 4. Defining exponential as an = a ⊗ a ⊗ · · · ⊗ a = a + a + · · · + a = na we {z } | {z } | n times n times find ax ⊗ ay = ax+y and (ax )y = axy , as in ordinary arithmetic. 5. The Kleene star of the matrix A is the matrix A∗ = I + A + A2 + · · · . 6. The completed max-plus semiring Rmax is the same as Rmax with the additional element +∞ and the convention (−∞) + (+∞) = (+∞) + (−∞) = −∞ "smtf33" — 2017/12/6 — 19:00 — page 27 — #37 1.7. COUPLED-ANALOGUES OF FUNCTIONS EXAMPLE Let A = 8 −∞ and B = 7 3 10 5 • Scalar multiplication of a matrix • Matrix addition • Matrix multiplication 2 . Then 0 15 −∞ 5 ⊗ 10 5 ⊗ (−∞) = 5⊗A = 10 8 5⊗5 5⊗3 10 2 10 ⊕ 8 −∞ ⊕ 2 = A⊕B = 7 3 5⊕7 3⊕0 10 ⊗ 8 ⊕ (−∞) ⊗ 7 10 ⊗ 2 ⊕ (−∞) ⊗ 0 A⊗B = 5⊗8⊕3⊗7 5⊗2⊕3⊗0 18 12 18 ⊕ (−∞) 12 ⊕ (−∞) = = 13 7 13 ⊕ 10 7⊕3 1.7 27 COUPLED-ANALOGUES OF FUNCTIONS 1. The coupled-logarithm, for x > 0, is Note that: lnκ (x) = xκ − 1 κ lnκ (xa ) = a lnaκ (x) lnκ (exκ ) = x (1.7.1) ( [1 + κx]1/κ when 1 + κx ≥ 0 x 2. The coupled-exponential is eκ = 0 otherwise Note that: lim lnκ (x) = ln x κ→0 lim exκ = ex κ→0 a (eκ ) = eax κ/a expκ (lnκ (x)) = x d ax κ [(1 − κ)ax] when κ 6= 1 eκ = a exp 1−κ dx Z 1 κ [(1 + κ)ax] + c1 exp 1+κ eax when κ 6= −1 κ dx = a(1 + κ) 1.7.1 (1.7.2) COUPLED-OPERATIONS 1. Coupled-addition is defined by: x ⊕κ y = x + y + κxy. Note that: κy exκ eyκ = ex⊕ κ lnκ (xy) = lnκ (x) ⊕ lnκ (y) (1.7.3) 2 x ⊕ y ⊕ z = x + y + z + κ(xy + xz + yz) + κ xyz 2. Coupled-subtraction is defined by: x ⊖κ y = (x − y)/(1 + κy) 1/κ 3. Coupled-division is defined by: x ⊘κ y = (xq − y q + 1) 1/κ 4. Coupled-multiplication is defined by: x ⊗κ y = (xκ + y κ − 1) . Note that: exκ ⊗κ eyκ = eκx+y lnκ (x ⊗κ y) = lnκ (x) + lnκ (y) n Y 1/κ κ κ κ x1 ⊗κ x1 ⊗κ · · · ⊗κ xn = κ xi = (x1 + x2 + · · · + xn − n + 1) i=1 "smtf33" — 2017/12/6 — 19:00 — page 28 — #38 28 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 1.8 NUMBER THEORY Divisibility The notation "a|b" means that the number a evenly divides the number b. That is, the ratio ab is an integer. 1.8.1 CONGRUENCES 1. If the integers a and b leave the same remainder when divided by the number n, then a and b are congruent modulo n. This is written a ≡ b (mod n). 2. If the congruence x2 ≡ a (mod p) has a solution, then a is a quadratic residue of p. Otherwise, a is a quadratic non-residue of p. (a) Let p be an odd prime. Legendre's symbol ap has the value +1 if a is a quadratic residue of p, and the value −1 if a is a quadratic non-residue of p. This can be written ap ≡ a(p−1)/2 (mod p). (b) The Jacobi symbol generalizes the Legendre symbol to non-prime modQk uli. If n = i=1 pbi i then the Jacobi symbol can be written in terms of the Legendre symbol as follows b k a Y a i . (1.8.1) = n pi i=1 3. An exact covering sequence is a set of non-negative ordered pairs {(ai , bi )}i=1,...,k such that every non-negative integer n satisfies n ≡ ai (mod bi ) for exactly one i. An exact covering sequence satisfies k X i=1 xai 1 = . b i 1−x 1−x (1.8.2) For example, every positive integer n is either congruent to 1 mod 2, or 0 mod 4, or 2 mod 4. Hence, the three pairs {(1, 2), (0, 4), (2, 4)} of residues and moduli exactly cover the positive integers. Note that 1 x2 1 x + + = . 2 4 1−x 1−x 1 − x4 1−x (1.8.3) 4. Carmichael numbers are composite numbers {n} that satisfy an−1 ≡ 1 (mod n) for every a (with 1 < a < n) that is relatively prime to n. There are infinitely many CarmichaelQnumbers. Every Carmichael number has at least three prime factors. If n = i pi is a Carmichael number, then (pi −1) divides (n − 1) for each i. There are 43 Carmichael numbers less than 106 and 105,212 less than 1015 . The Carmichael numbers less than ten thousand are 561, 1105, 1729, 2465, 2821, 6601, and 8911. "smtf33" — 2017/12/6 — 19:00 — page 29 — #39 1.8. NUMBER THEORY 1.8.1.1 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 29 Properties of congruences If a ≡ b (mod n), then b ≡ a (mod n). If a ≡ b (mod n), and b ≡ c (mod n), then a ≡ c (mod n). If a ≡ a′ (mod n), and b ≡ b′ (mod n), then a ± b ≡ a′ ± b′ (mod n). If a ≡ a′ (mod n), then a2 ≡ (a′ )2 (mod n), a3 ≡ (a′ )3 (mod n), etc. If GCD(k, m) = d, then the congruence kx ≡ n (mod m) is solvable if and only if d divides n. It then has d solutions. If p is a prime, then ap ≡ a (mod p). If p is a prime, and p does not divide a, then ap−1 ≡ 1 (mod p). If GCD(a, m) = 1, then aφ(m) ≡ 1 (mod m). (See Section 1.8.12 for φ(m).) If p is an odd prime and a is not a multiple of p, then Wilson's theorem states a (p − 1)! ≡ − p a(p−1)/2 (mod p). If p and qare odd primes, then Gauss' law of quadratic reciprocity states that q p = (−1)(p−1)(q−1)/4 . Therefore, if a and b are relatively prime odd q p a b (a−1)(b−1)/4 integers and b ≥ 3, then = (−1) . b a The number −1 is a quadratic residue of primes of the form 4k + 1 and a non-residue of primes of the form 4k + 3. That is ( −1 +1 when p ≡ 1 (mod 4) (p−1)/2 = (−1) = p −1 when p ≡ 3 (mod 4) 12. The number 2 is a quadratic residue of primes of the form 8k ± 1 and a nonresidue of primes of the form 8k ± 3. That is ( +1 when p ≡ ±1 (mod 8) 2 (p2 −1)/8 = (−1) = p −1 when p ≡ ±3 (mod 8) 1.8.2 CHINESE REMAINDER THEOREM Let m1 , m2 , . . . , mr be pairwise relatively prime integers. congruences x ≡ a1 x ≡ a2 .. . x ≡ ar (mod m1 ) (mod m2 ) The system of (1.8.4) (mod mr ) has a unique solution modulo M = m1 m2 · · · mr . This unique solution can be written as x = a1 M 1 y 1 + a2 M 2 y 2 + · · · + ar M r y r (1.8.5) where Mk = M/mk , and yk is the inverse of Mk (modulo mk ). "smtf33" — 2017/12/6 — 19:00 — page 30 — #40 30 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS EXAMPLE For the system of congruences x≡1 (mod 3) x≡3 (mod 7) x≡2 (mod 5) we have M = 3·5·7 = 105 with M1 = 35, M2 = 21, and M3 = 15. The equation for y1 is M1 y1 = 35y1 ≡ 1 (mod 3) with solution y1 ≡ 2 (mod 3). Likewise, y2 ≡ 1 (mod 5) and y3 ≡ 1 (mod 7). This results in x = 1 · 35 · 2 + 2 · 21 · 1 + 3 · 15 · 1 ≡ 52 (mod 105). 1.8.3 CONTINUED FRACTIONS The symbol [a0 , a1 , . . . , aN ], with ai > 0, represents the simple continued fraction, 1 [a0 , a1 , . . . , aN ] = a0 + (1.8.6) 1 a1 + 1 a2 + 1 a3 + ... a4 + ··· + 1 . aN The nth convergent (with 0 < n < N ) of [a0 , a1 , . . . , aN ] is defined to be [a0 , a1 , . . . , an ]. If {pn } and {qn } are defined by p0 = a0 , p1 = a1 a0 + 1, pn = an pn−1 + pn−2 q0 = 1, q1 = a1 , qn = an qn−1 + qn−2 (2 ≤ n ≤ N ) (2 ≤ n ≤ N ) then [a0 , a1 , . . . , aP n ] = pn /qn . The continued fraction is convergent if and only if ∞ the infinite series i ai is divergent. If the positive rational number x can be represented by a simple continued fraction with an odd (even) number of terms, then it is also representable by one with an even (odd) number of terms. (Specifically, if an = 1 then [a0 , a1 , . . . , an−1 , 1] = [a0 , a1 , . . . , an−1 + 1], and if an ≥ 2, then [a0 , a1 , . . . , an ] = [a0 , a1 , . . . , an − 1, 1].) Aside from this indeterminacy, the simple continued fraction of x is unique. The error in approximating by a convergent is bounded by pn 1 1 x− ≤ < 2. (1.8.7) qn qn qn+1 qn The algorithm for finding a continued fraction expansion of a number is to remove the integer part of the number (this becomes ai ), take the reciprocal, and repeat. "smtf33" — 2017/12/6 — 19:00 — page 31 — #41 1.8. NUMBER THEORY 31 For example, for the number π: β0 = π ≈ 3.14159 β1 = 1/(β0 − a0 ) ≈ 7.062 a0 = ⌊β0 ⌋ = 3 a1 = ⌊β1 ⌋ = 7 β4 = 1/(β3 − a3 ) ≈ 292.6 a4 = ⌊β4 ⌋ = 292 β2 = 1/(β1 − a1 ) ≈ 15.997 β3 = 1/(β2 − a2 ) ≈ 1.0034 a2 = ⌊β2 ⌋ = 15 a3 = ⌊β3 ⌋ = 1 Since π = [3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, . . .] approximations to π may be 333 355 found from the convergents: 22 7 ≈ 3.142, 106 ≈ 3.14150, 113 ≈ 3.1415929. Since e = [2, 1, 2, 1, 1, 4, 1, 1, 6, . . . , 1, 1, 2n, . . . ] approximations to e may be 19 87 found from the convergents: 38 ≈ 2.6, 11 4 ≈ 2.75, 7 ≈ 2.714, 32 ≈ 2.7187, . . .. A periodic continued fraction is an infinite continued fraction in which al = al+k for all l ≥ L. The set of partial quotients aL , aL+1 , . . . , aL+k−1 is the period. A periodic continued fraction may be written as (1.8.8) [a0 , a1 , . . . , aL−1 , aL , aL+1 , . . . , aL+k−1 ] . For example, √ √2 = [1, 2] √3 = [1, 1, 2] √4 = [2] 5 = [2, 4] √ √ √ √6 = [2, 2, 4] √10 = [3, 6] √14 = [3, 1, 2, 1, 6] 7 = [2, 1, 1, 1, 4] 11 = [3, 3, 6] √ √ √15 = [3, 1, 6] √8 = [2, 1, 4] √12 = [3, 2, 6] √16 = [4] 9 = [3] 13 = [3, 1, 1, 1, 1, 6] 17 = [4, 8] q √ If x = [b, a] then x = 12 (b+ b2 + 4b a ). For example, [1] = [1, 1] = (1+ 5)/2, √ √ [2] = [2, 2] = 1 + 2, and [2, 1] = 1 + 3. Functions can be represented as continued fractions. Using the notation a1 b0 + ≡ b0 + a2 b1 + a1 a2 a3 a4 ... b1 + b2 + b3 + b4 + a3 b2 + b3 + a4 b4 + . . . we have (allowable values of z may be restricted in the following) (a) ln(1 + z) = (b) ez = z z z 4z 4z 9z 1+ 2+ 3+ 4+ 5+ 6+ 1 z z z z z z 1− 1+ 2− 3+ 2− 5+ 2− (c) tan z = z z2 z2 z2 1− 3− 5− 7− (d) tanh z = ... z z2 z2 z2 1+ 3+ 5+ 7+ ... ... ··· = 1 + z z z z z z z 1− 2+ 3− 2+ 5− 2+ 7− ... (1.8.9) "smtf33" — 2017/12/6 — 19:00 — page 32 — #42 32 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 1.8.4 DIOPHANTINE EQUATIONS A diophantine equation is one whose solutions are integers. 1. Fermat's last theorem states that there are no integer solutions to xn +y n = z n , when n > 2. This was proved by Andrew Wiles in 1995. 2. The similar, but slightly different, equation xn + y n = z n+1 has parametric u u v solutions given by x = a (am + bm ) , y = b (am + bm ) , z = (am + bm ) where gcd(m, n) = 1 and nv − mu = 1. 3. The Hurwitz equation, x21 + x22 + · · · + x2n = ax1 x2 · · · xn , has no integer solutions for a > n. 4. Bachet's equation, y 2 = x3 + k, has no solutions when k is: −144, −105, −78, −69, −42, −34, −33, −31, −24, −14, −5, 7, 11, 23, 34, 45, 58, 70. 5. Ramanujan's "square equation," 2n = 7 + x2 , has solutions for n = 3, 4, 5, 7, and 15 corresponding to x = 1, 3, 5, 11, and 181. 6. For given k and m consider ak1 + ak2 + · · · + akm = bk1 + bk2 + · · · + bkn with a1 ≥ a2 ≥ · · · ≥ am , b1 ≥ b2 ≥ · · · ≥ bn , a1 > 1, and m ≤ n. For example: 52 = 42 + 32 123 + 13 = 103 + 93 1584 + 594 = 1344 + 1334 4224814 = 4145604 + 2175194 + 958004 1445 = 1335 + 1105 + 845 + 275 Given k and m the least value of n for which a solution is known is as follows: m=1 2 3 4 5 6 k=2 2 3 3 2 4 3 2 5 4 3 6 7 5 3 7 7 6 5 4 8 8 7 5 4 9 10 8 8 6 5 10 12 12 11 9 7 6 7. Cannonball problem: If n2 cannonballs can be stacked to form a square pyraP mid of height k, what are n and k? The Diophantine equation is ki=1 i2 = 1 2 6 k(k + 1)(2k + 1) = n with solutions (k, n) = (1, 1) and (k, n) = (24, 70). 8. The Euler equation 2n = 7x2 + y 2 has a unique solution, with x and y odd, for n ≥ 3: 2n/2+1 x= √ |sin αn | y = 2n/2+1 |cos αn | 7 √ where αn = [n − 2] tan−1 7 . The solutions are (n, x, y) = {(3, 1, 1), (4, 1, 3), (5, 1, 5), (6, 3, 1), . . . } "smtf33" — 2017/12/6 — 19:00 — page 33 — #43 1.8. NUMBER THEORY 33 9. Apart from the trivial solutions (with x = y = 0 or x = u), the general solution to the equation x3 + y 3 = u3 + v 3 is given parametrically by x = λ 1 − (a − 3b)(a2 + 3b2 ) y = λ (a + 3b)(a2 + 3b2 ) − 1 v = λ (a2 + 3b2 )2 − (a − 3b) u = λ (a + 3b) − (a2 + 3b2 )2 where {λ, a, b} are any rational numbers except that λ 6= 0. 10. A parametric solution to x4 + y 4 = u4 + v 4 is given by x = a7 + a5 b2 − 2a3 b4 + 3a2 b5 + ab6 y = a6 b − 3a5 b2 − 2a4 b3 + a2 b5 + b7 u = a7 + a5 b2 − 2a3 b4 − 3a2 b5 + ab6 v = a6 b + 3a5 b2 − 2a4 b3 + a2 b5 + b7 11. Parametric solutions to the equation (A2 +B 2 )(C 2 +D2 ) = E 2 +F 2 are given by the Fibonacci identity (a2 +b2 )(c2 +d2 ) = (ac±bd)2 +(bc∓ad)2 = e2 +f 2 . A similar identity is the Euler four-square identity (a21 + a22 + a23 + 2 2 2 2 2 2 a4 )(b1 + b2 + b3 + b4 ) = (a1 b1 − a2 b2 − a3 b3 − a4 b4 ) + (a1 b2 + a2 b1 + a3 b4 − a4 b3 )2 + (a1 b3 − a2 b4 + a3 b1 + a4 b2 )2 + (a1 b4 + a2 b3 − a3 b2 − a4 b1 )2 . 12. The only integer solutions to thenequation xy = y x are (2, 4) and x o= y. Nonu u+1 integral solutions are given by x = 1 + u1 , y = 1 + u1 . Setting 64 256 9 27 u = 2, 3, . . . yields the rational solutions 4 , 8 , 27 , 81 , . . . 1.8.4.1 Pythagorean triples If the positive integers A, B, and C satisfy A2 + B 2 = C 2 , then the triplet (A, B, C) is a Pythagorean triple. A right triangle can be constructed with sides of length A and B and a hypotenuse of C. There are infinitely many Pythagorean triples. A general solution to A2 + B 2 = C 2 , with GCD(A, B) = 1 and A even, is A = 2xy, B = x2 − y 2 , C = x2 + y 2 , (1.8.10) where x and y are relatively prime integers of opposite parity (i.e., one is even and the other is odd) with x > y > 0. The table below left shows some Pythagorean triples with the associated (x, y) values. x y A = 2xy B = x2 − y 2 C = x2 + y 2 2 4 6 8 10 3 5 1 1 1 1 1 2 2 4 8 12 16 20 12 20 3 15 35 63 99 5 21 5 17 37 65 101 13 29 n 6 6 6 p q 1 18 2 9 3 6 A B C 7 24 25 8 15 17 9 12 15 A different general solution is obtained by factoring even squares as n2 = 2pq. Here A = n+p, B = n+q, and C = n+p+q. The table above right shows the (p, q) and (A, B, C) values obtained from the factorizations 36 = 2 · 1 · 18 = 2 · 2 · 9 = 2 · 3 · 6. "smtf33" — 2017/12/6 — 19:00 — page 34 — #44 34 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 1.8.4.2 Pell's equation Pell's equation is x2 − dy 2 = 1. The √ solutions, integral values of (x, y), arise from continued fraction convergents of d. If (x, y) is the least positive solution to Pell's equation (with d square-free), then every positive solution (xk , yk ) is given by √ √ (1.8.11) xk + yk d = (x + y d)k The following tables contain the least positive solutions to Pell's equation with d square-free and d < 100. d 2 3 5 6 7 10 11 13 14 15 17 19 21 22 23 26 29 30 31 33 x 3 2 9 5 8 19 10 649 15 4 33 170 55 197 24 51 9,801 11 1,520 23 y 2 1 4 2 3 6 3 180 4 1 8 39 12 42 5 10 1,820 2 273 4 d 35 37 38 39 41 42 43 46 47 51 53 55 57 58 59 61 62 65 66 67 x 6 73 37 25 2,049 13 3,482 24,335 48 50 66,249 89 151 19,603 530 1,766,319,049 63 129 65 48,842 y 1 12 6 4 320 2 531 3,588 7 7 9,100 12 20 2,574 69 226,153,980 8 16 8 5,967 d 69 70 71 73 74 77 78 79 82 83 85 86 87 89 91 93 94 95 97 x 7,775 251 3,480 2,281,249 3,699 351 53 80 163 82 285,769 10,405 28 500,001 1,574 12,151 2,143,295 39 62,809,633 y 936 30 413 267,000 430 40 6 9 18 9 30,996 1,122 3 53,000 165 1,260 221,064 4 6,377,352 EXAMPLES √ 1. The number 2 has the continued fraction expansion [1, 2, 2, 2, 2, . . . ], with conver, 41 , 99 , . . . . In this case, every second convergent represents a solution: gents 32 , 57 , 17 12 29 70 32 − 2 · 22 = 1, 172 − 2 · 122 = 1, 992 − 2 · 702 = 1 √ 2. The least √ positive solution for d = 11 is (x, y) = (10, 3). Since (10 + 3 11)2 = 199 + 60 11, another solution is given by (x2 , y2 ) = (199, 60). "smtf33" — 2017/12/6 — 19:00 — page 35 — #45 1.8. NUMBER THEORY 1.8.4.3 35 Lagrange's theorem Lagrange's theorem states: "Every positive integer is the sum of four squares." After showing every prime can be written as the sum of four squares, the following identity can be used to show how products can be written as the sum of four squares: (x21 + x22 + x23 + x24 )(y12 + y22 + y32 + y42 ) = (x1 y1 + x2 y2 + x3 y3 + x4 y4 )2 + (x1 y2 − x2 y1 + x3 y4 − x4 y3 )2 + (x1 y3 − x3 y1 + x4 y2 − x2 y4 )2 + (x1 y4 − x4 y1 + x2 y3 − x3 y2 )2 (1.8.12) Note also the identity for sums of two squares: (x21 + x22 )(y12 + y22 ) = (x1 y2 + x2 y1 )2 + (x2 y2 − x1 y1 )2 1.8.5 (1.8.13) GREATEST COMMON DIVISOR The greatest common divisor of the integers n and m is the largest integer that evenly divides both n and m; this is written as GCD(n, m) or (n, m). The Euclidean algorithm is frequently used for computing the GCD of two numbers; it utilizes the fact that m = m n + p where 0 ≤ p < n. n Given the integers m and n, two integers a and b can always be found so that am + bn = GCD(n, m). Two numbers, m and n, are said to be relatively prime if they have no divisors in common; i.e., if GCD(a, b) = 1. The probability that two integers chosen randomly are relatively prime is π/6. EXAMPLE Consider 78 and 21. Since 78 = 3 · 21 + 15, the largest integer that evenly divides both 78 and 21 is also the largest integer that evenly divides both 21 and 15. Iterating results in: 78 = 3 · 21 + 15 21 = 1 · 15 + 6 15 = 2 · 6 + 3 6=2·3+0 Hence GCD(78, 21) = GCD(21, 15) = GCD(15, 6) = GCD(6, 3) = 3. Note that 78 · (−4) + 21 · 15 = 3. 1.8.6 LEAST COMMON MULTIPLE The least common multiple of the integers a and b (denoted LCM(a, b)) is the least integer r that is divisible by both a and b. The simplest way to find the LCM of a and b is via the formula LCM(a, b) = ab/GCD(a, b). For example, LCM(10, 4) = 10·4 10·4 GCD(10,4) = 2 = 20. "smtf33" — 2017/12/6 — 19:00 — page 36 — #46 36 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 1.8.7 MÖBIUS FUNCTION The Möbius function is defined by 1. µ(1) = 1 2. µ(n) = 0 if n has a squared factor 3. µ(p1 p2 . . . pk ) = (−1)k if all the primes {p1 , . . . , pk } are distinct Its properties include: 1. If GCD(m, n) ( = 1 then µ(mn) = µ(m) µ(n) X 1 if n = 1 µ(d) = 2. 0 if n > 1 d|n 3. Generating function: ∞ X µ(n)n−s = n=0 1 ζ(s) 4. The Möbius inversion formula states that, if g(n) = X f (d), then d|n f (n) = n X X n µ(d)g g(d) = . µ d d d|n For example, the Möbius inversion of n = (1.8.14) d|n X φ(d) is φ(n) = n d|n X µ(d) d|n d . The table below has the value of µ(10n + k) in row n_ and column _k. For example, µ(2) = −1, µ(4) = 0, and µ(6) = 1. _0 0_ 1_ 2_ 3_ 4_ 5_ 6_ 7_ 8_ 9_ 10_ 11_ 12_ 13_ 14_ 15_ 1 0 −1 0 0 0 −1 0 0 0 −1 0 −1 0 0 _1 _2 _3 _4 _5 _6 1 −1 −1 0 −1 1 −1 0 −1 1 1 0 1 1 −1 0 0 1 −1 0 1 1 1 0 −1 −1 −1 0 0 1 1 0 −1 0 1 0 −1 1 0 0 1 −1 −1 0 −1 1 0 0 0 1 −1 0 1 1 1 0 1 1 1 0 −1 −1 −1 0 −1 1 1 0 −1 −1 1 0 0 1 1 0 0 0 −1 0 1 1 0 0 1 1 1 0 1 1 −1 0 0 −1 1 0 _7 _8 _9 −1 0 0 −1 0 −1 0 0 −1 −1 1 1 −1 0 0 1 1 −1 −1 0 1 1 −1 −1 1 0 −1 −1 0 0 −1 0 −1 0 1 1 −1 0 1 −1 −1 −1 0 0 −1 −1 1 1 "smtf33" — 2017/12/6 — 19:00 — page 37 — #47 1.8. NUMBER THEORY 1.8.8 37 PRIME NUMBERS 1. A prime number is a positive integer greater than 1 with no positive, integral divisors other than 1 and itself. There are infinitely many prime numbers, 2, 3, 5, 7, . . . . The sum of the reciprocals of the prime numbers diverges: P 1 1 1 1 n pn = 3 + 5 + 7 + . . . = ∞. 2. Twin primes are prime numbers that differ by two: (3, 5), (5, 7), (11, 13), (17, 19), . . . . It is not known whether there are infinitely many twin primes. The sum of the reciprocals of the twin primes converges; the value 1 1 1 1 1 1 1 1 + + + ...+ + ... + + + + B= 3 5 5 7 11 13 p p+2 known as Brun's constant is approximately B ≈ 1.90216054. 3. For every integer n ≥ 2, the numbers {n! + 2, n! + 3, . . . , n! + n} are a sequence of n − 1 consecutive composite (i.e., not prime) numbers. 4. Dirichlet's theorem on primes in arithmetic progressions: Let a and b be relatively prime positive integers. Then the arithmetic progression an + b (for n = 1, 2, . . . ) contains infinitely many primes. 5. Goldbach conjecture: every even number is the sum of two prime numbers. 6. The function π(x) represents the number of primes less than x. The prime number theorem states that π(x) ∼ x/ log x as x → ∞. For x ≥ 17, we have x x log x ≤ π(x) ≤ 1.26 log x . The number of primes less than a given number is: x π(x) x π(x) 1.8.8.1 100 1000 10,000 105 106 107 108 25 168 1,229 9,592 78,498 664,579 5,761,455 1010 1015 1021 455,052,511 29,844,570,422,669 21,127,269,486,018,731,928 Prime formulas The polynomial x2 − x + 41 yields prime numbers for x = 0, 1, 2, . . . , 39. The set of prime numbers is identical with the set of positive values taken on by the polynomial of degree 25 in the 26 variables {a, b, . . . , z}: (k + 2){1 − [wz + h + j − q]2 − [(gk + 2g + k + 1)(h + j) + h − z]2 − [2n + p + q + z − e]2 −[16(k+1)3 (k+2)(n+1)2 +1−f 2 ]2 −[e3 (e+2)(a+1)2 +1−o2 ]2 −[(a2 −1)y 2 +1−x2 ]2 − [16r 2 y 4 (a2 − 1) + 1 − u2 ]2 − [((a + u2 (u2 − a))2 − 1)(n + 4dy)2 + 1 − (x + cu)2 ]2 − [n + l + v − y]2 − [(a2 − 1)l2 + 1 − m2 ]2 − [ai + k + 1 − l − i]2 − [p + l(a − n − 1) + b(2an + 2a − n2 − 2n − 2) − m]2 − [q + y(a − p − 1) + s(2ap + 2a − p2 − 2p − 2) − x]2 − [z + pl(a − p) + t(2ap − p2 − 1) − pm]2 } Although this polynomial appears to factor, the factors are improper, P = P ·1. Note that this formula will also take on negative values, such as −76. There also exists a prime representing polynomial with 12 variables of degree 13697, and one of 10 variables and degree about 1045 . "smtf33" — 2017/12/6 — 19:00 — page 38 — #48 38 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 1.8.8.2 Lucas–Lehmer primality test 2 Define the sequence rm+1 = rm − 2 with r1 = 3. If p is a prime of the form 4n + 3 p and Mp = 2 − 1, then Mp will be prime (called a Mersenne prime) if and only if Mp divides rp−1 . This simple test is the reason that the largest known prime numbers are Mersenne primes. For example, consider p = 7 and M7 = 127. The {rn } sequence is {3, 7, 47, 2207 ≡ 48, 2302 ≡ 16, 254 ≡ 0}; hence M7 is prime. 1.8.8.3 Primality test certificates A primality certificate is an easily verifiable statement (easier than it was to determine that a number is prime) that proves that a specific number is prime. There are several types of certificates. The Atkin–Morain certificate uses elliptic curves. To show that the number p is prime, Pratt's certificate consists of a number a and the factorization of the number p − 1. The number p will be prime if there exists a primitive root a in the field GF[p] that satisfies the conditions ap−1 = 1 (mod p) and a(p−1)/q 6= 1 (mod p) for any prime q that divides p − 1. EXAMPLE The number p = 31 has p − 1 = 30 = 2 · 3 · 5, and a primitive root is given by a = 3. Hence, to verify that p = 31 is prime, we compute 3(31−1)/2 = 315 ≡ 14348907 ≡ −1 6= 1 (mod 31), 3 (mod 31), (31−1)/3 (31−1)/5 3 (31−1) 3 1.8.8.4 10 =3 6 ≡ 59049 ≡ 25 6= 1 = 3 ≡ 729 ≡ 16 6= 1 2 = 3(31−1)/2 ≡ (−1)2 = 1 (mod 31), (mod 31). Probabilistic primality test Let n be a number whose primality is to be determined. Probabilistic primality tests can return one of two results: either a proof that the number n is composite or a statement of the form, "The probability that the number n is not prime is less than ǫ," where ǫ can be specified by the user. Typically, we take ǫ = 2−200 < 10−60 . From Fermat's theorem, if b 6= 0, then bn−1 = 1 (mod n) whenever n is prime. If this holds, then n is a probable prime to the base b. Given a value of n, if a value of b can be found such that this does not hold, then n cannot be prime. It can happen, however, that a probable prime is not prime. Let P (x) be the probability that n is composite under the hypotheses: 1. n is an odd integer chosen randomly from the range [2, x]; 2. b is an integer chosen randomly from the range [2, n − 2]; 3. n is a probable prime to the base b. Then P (x) ≤ (log x)−197 for x ≥ 1010000 . A different test can be obtained from the following theorem. Given the number n, find s and t with n − 1 = 2s t, with t odd. Then choose a random integer b from the range [2, n − 2]. If either bt = 1 (mod n) or i b2 t = −1 (mod n), for some i < s, "smtf33" — 2017/12/6 — 19:00 — page 39 — #49 1.8. NUMBER THEORY 39 then n is a strong probable prime to the base b. Every odd prime must pass this test. If n > 1 is an odd composite, then the probability that it is a strong probable prime to the base b, when b is chosen randomly, is less than 1/4. A stronger test can be obtained by choosing k independent values for b in the range [2, n − 2] and checking the above relation for each value of b. Let Pk (x) be the probability that n is found to be a strong probable prime to each base b. Then Pk (x) ≤ 4−(k−1) P (x)/(1 − P (x)). 1.8.9 PRIME NUMBERS OF SPECIAL FORMS 1. The largest known prime numbers, in descending order, are Prime number Number of digits (1) 274207281 − 1 22,338,618 (2) 257885161 − 1 17,425,170 (3) 243112609 − 1 12,978,189 (4) 242643801 − 1 12,837,064 (5) 237156667 − 1 11,185,272 (6) 232582657 − 1 9,808,358 (7) 10223 · 231172165 + 1 9,383,761 (8) 230402457 − 1 9,152,052 (9) 225964951 − 1 7,816,230 (10) 224036583 − 1 7,235,733 2. The largest known twin primes are 2996863034895 · 221290000 ± 1 (with 388,342 digits). n 3. There θ ≈ 1.30637788 and ω ≈ 1.9287800 such that θ3 exist constants ·2ω ·· and 2| 2{z } are prime for every n ≥ 1. n 4. Primes with special properties (a) A Sophie Germain prime p has the property that 2p + 1 is also prime. Sophie Germain primes include: 2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, . . . , 3714089895285 · 260000 − 1, . . . . (b) An odd prime p is called a Wieferich prime if 2p−1 ≡ 1 (mod p2 ). Wieferich primes include 1093 and 3511. (c) A Wilson prime satisfies (p − 1)! ≡ −1 (mod p2 ). Wilson primes include 5, 13, and 563. 5. For each n below {a + md | m = 0, 1, . . . , n − 1} is an arithmetic sequence of n prime numbers. (Note that 23# = 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23.) n a d 3 3 2 4 61 6 5 11 30 10 199 210 26 43142746595714191 23681770·23# "smtf33" — 2017/12/6 — 19:00 — page 40 — #50 40 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 6. Define p# to be the product of the prime numbers less than or equal to p. Form Values of n or p for which the form is prime 2n 0, 1, 2, 3, 4 . . . (Fermat primes) 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, . . . , 74207281, . . . (Mersenne primes) 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, 324, 379, 469, 546, 974, 1963, 3507, 3610, 6917, . . . (factorial primes) 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, 320, 340, 399, 427, 872, 1477, 6380, . . . (factorial primes) 3, 5, 11, 13, 41, 89, 317, 337, 991, 1873, 2053, 2377, 4093, 4297, 4583, 6569, 13033, 15877, . . . (primorial or Euclid primes) 2, 3, 5, 7, 11, 31, 379, 1019, 1021, 2657, 3229, 4547, 4787, 11549, 13649, 18523, 23801, 24029, 42209, . . . , 145823, 366439, 392113, . . . (primorial or Euclid primes) 1, 141, 4713, 5795, 6611, 18496, 32292, 32469, 59656, 90825, 262419, 361275, . . . , 481899, . . . (Cullen primes) 2, 3, 6, 30, 75, 81, 115, 123, 249, 362, 384, 462, 512, 751, 822, 5312, 7755, 9531, 12379, 15822, 18885, . . . 143018, 151023, 667071, . . . (Woodall primes) 2 +1 2n − 1 n! − 1 n! + 1 p# − 1 p# + 1 n2n + 1 n2n − 1 7. Prime numbers of the form Form 2n − 1 1 n 3 −1 2 5n − 1 4 an − 1 (called repunits). a−1 Values of n for which the form is prime These are Mersenne primes; see the previous table. 3, 7, 13, 71, 103, 541, 1091, 1367, 1627, 4177, 9011, 9551, . . . 3, 7, 11, 13, 47, 127, 149, 181, 619, 929, 3407, 10949, 13241, ... 6n − 1 5 2, 3, 7, 29, 71, 127, 271, 509, 1049, 6389, 6883, 10613, 19889, ... n 7 −1 6 10n − 1 9 5, 13, 131, 149, 1699, 14221, 35201, 126037, 371669, . . . 2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343, . . . "smtf33" — 2017/12/6 — 19:00 — page 41 — #51 1.8. NUMBER THEORY 41 8. Prime numbers of the forms 2n ± a, 10n ± b and 16n ± c In the following table, for a given value of n, the quantities a± , b± , and c± are the least values such that 2n + a± , 10n + b± , and 16n + c± are probably primes. (A probabilistic primality test was used.) For example, for n = 3, the numbers 23 − 1 = 7, 23 + 3 = 11, 103 − 3 = 997, 103 + 9 = 1009, 163 − 3 = 4093, and 163 + 3 = 4099 are all prime. 2n + a n 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 50 100 150 200 300 400 500 600 700 800 900 1000 10n + b a− −1 −1 −3 −1 −3 a+ 1 3 1 5 3 −3 −1 −3 −19 −15 3 17 27 3 1 −15 −3 −75 −153 −593 277 147 235 157 181 −1 −5 −3 −3 −9 −1 −5 −1 −3 −27 −863 −95 −1113 −105 −207 −1245 3 1 9 7 5 29 3 21 7 55 55 187 535 25 693 297 b− −3 −3 −27 −9 −17 16n + c b+ 1 9 7 3 3 −9 −11 −63 −33 −23 19 7 7 19 3 −3 −11 −39 −11 −57 3 3 51 39 151 −11 −29 −27 −11 −63 −797 −273 −189 −69 −513 39 37 31 37 61 267 67 357 331 69 −1037 961 −1791 543 −2313 7 −1007 1537 −773 1873 −1769 453 c− −5 −3 −15 −3 −3 c+ 1 3 1 7 43 −57 −5 −5 −87 −17 3 15 31 15 7 −23 −93 −15 −65 −75 33 15 15 13 235 −59 −47 −5 −93 −59 21 21 81 33 13 −593 181 −95 187 −105 25 −305 1515 −2273 895 −2217 841 −5 255 −909 2823 −1683 751 −1193 8767 −2303 63 "smtf33" — 2017/12/6 — 19:00 — page 42 — #52 42 CHAPTER 1. NUMBERS AND ELEMENTARY MATHEMATICS 1.8.10 PRIME NUMBERS LESS THAN 7,000 The prime number p10n+k is found by looking at row n_ and column _k. For example, the 9th prime number is 23 and the 18th prime number is 61. _0 _1 _2 _3 _4 _5 _6 _7 _8 _9 0_ 1_ 2_ 3_ 4_ 5_ 29 71 113 173 229 2 31 73 127 179 233 3 37 79 131 181 239 5 41 83 137 191 241 7 43 89 139 193 251 11 47 97 149 197 257 13 53 101 151 199 263 17 59 103 157 211 269 19 61 107 163 223 271 23 67 109 167 227 277 6_ 7_ 8_ 9_ 10_ 281 349 409 463 541 283 353 419 467 547 293 359 421 479 557 307 367 431 487 563 311 373 433 491 569 313 379 439 499 571 317 383 443 503 577 331 389 449 509 587 337 397 457 521 593 347 401 461 523 599 11_ 12_ 13_ 14_ 15_ 601 659 733 809 863 607 661 739 811 877 613 673 743 821 881 617 677 751 823 883 619 683 757 827 887 631 691 761 829 907 641 701 769 839 911 643 709 773 853 919 647 719 787 857 929 653 727 797 859 937 16_ 17_ 18_ 19_ 20_ 941 1013 1069 1151 1223 947 1019 1087 1153 1229 953 1021 1091 1163 1231 967 1031 1093 1171 1237 971 1033 1097 1181 1249 977 1039 1103 1187 1259 983 1049 1109 1193 1277 991 1051 1117 1201 1279 997 1061 1123 1213 1283 1009 1063 1129 1217 1289 21_ 22_ 23_ 24_ 25_ 1291 1373 1451 1511 1583 1297 1381 1453 1523 1597 1301 1399 1459 1531 1601 1303 1409 1471 1543 1607 1307 1423 1481 1549 1609 1319 1427 1483 1553 1613 1321 1429 1487 1559 1619 1327 1433 1489 1567 1621 1361 1439 1493 1571 1627 1367 1447 1499 1579 1637 26_ 27_ 28_ 29_ 30_ 1657 1733 1811 1889 1987 1663 1741 1823 1901 1993 1667 1747 1831 1907 1997 1669 1753 1847 1913 1999 1693 1759 1861 1931 2003 1697 1777 1867 1933 2011 1699 1783 1871 1949 2017 1709 1787 1873 1951 2027 1721 1789 1877 1973 2029 1723 1801 1879 1979 2039 31_ 32_ 33_ 34_ 35_ 2053 2129 2213 2287 2357 2063 2131 2221 2293 2371 2069 2137 2237 2297 2377 2081 2141 2239 2309 2381 2083 2143 2243 2311 2383 2087 2153 2251 2333 2389 2089 2161 2267 2339 2393 2099 2179 2269 2341 2399 2111 2203 2273 2347 2411 2113 2207 2281 2351 2417 36_ 37_ 38_ 39_ 40_ 2423 2531 2617 2687 2741 2437 2539 2621 2689 2749 2441 2543 2633 2693 2753 2447 2549 2647 2699 2767 2459 2551 2657 2707 2777 2467 2557 2659 2711 2789 2473 2579 2663 2713 2791 2477 2591 2671 2719 2797 2503 2593 2677 2729 2801 2521 2609 2683 2731 2803 41_ 42_ 43_ 44_ 45_ 2819 2903 2999 3079 3181 2833 2909 3001 3083 3187 2837 2917 3011 3089 3191 2843 2927 3019 3109 3203 2851 2939 3023 3119 3209 2857 2953 3037 3121 3217 2861 2957 3041 3137 3221 2879 2963 3049 3163 3229 2887 2969 3061 3167 3251 2897 2971 3067 3169 3253 "smtf33" — 2017/12/6 — 19:00 — page 43 — #53 1.8. NUMBER THEORY _0 _1 _2 _3 _4 _5 _6 _7 _8 _9 46_ 47_ 48_ 49_ 50_ 3257 3331 3413 3511 3571 3259 3343 3433 3517 3581 3271 3347 3449 3527 3583 3299 3359 3457 3529 3593 3301 3361 3461 3533 3607 3307 3371 3463 3539 3613 3313 3373 3467 3541 3617 3319 3389 3469 3547 3623 3323 3391 3491 3557 3631 3329 3407 3499 3559 3637 51_ 52_ 53_ 54_ 55_ 3643 3727 3821 3907 3989 3659 3733 3823 3911 4001 3671 3739 3833 3917 4003 3673 3761 3847 3919 4007 3677 3767 3851 3923 4013 3691 3769 3853 3929 4019 3697 3779 3863 3931 4021 3701 3793 3877 3943 4027 3709 3797 3881 3947 4049 3719 3803 3889 3967 4051 56_ 57_ 58_ 59_ 60_ 4057 4139 4231 4297 4409 4073 4153 4241 4327 4421 4079 4157 4243 4337 4423 4091 4159 4253 4339 4441 4093 4177 4259 4349 4447 4099 4201 4261 4357 4451 4111 4211 4271 4363 4457 4127 4217 4273 4373 4463 4129 4219 4283 4391 4481 4133 4229 4289 4397 4483 61_ 62_ 63_ 64_ 65_ 4493 4583 4657 4751 4831 4507 4591 4663 4759 4861 4513 4597 4673 4783 4871 4517 4603 4679 4787 4877 4519 4621 4691 4789 4889 4523 4637 4703 4793 4903 4547 4639 4721 4799 4909 4549 4643 4723 4801 4919 4561 4649 4729 4813 4931 4567 4651 4733 4817 4933 66_ 67_ 68_ 69_ 70_ 4937 5003 5087 5179 5279 4943 5009 5099 5189 5281 4951 5011 5101 5197 5297 4957 5021 5107 5209 5303 4967 5023 5113 5227 5309 4969 5039 5119 5231 5323 4973 5051 5147 5233 5333 4987 5059 5153 5237 5347 4993 5077 5167 5261 5351 4999 5081 5171 5273 5381 71_ 72_ 73_ 74_ 75_ 5387 5443 5521 5639 5693 5393 5449 5527 5641 5701 5399 5471 5531 5647 5711 5407 5477 5557 5651 5717 5413 5479 5563 5653 5737 5417 5483 5569 5657 5741 5419 5501 5573 5659 5743 5431 5503 5581 5669 5749 5437 5507 5591 5683 5779 5441 5519 5623 5689 5783 76_ 77_ 78_ 79_ 80_ 5791 5857 5939 6053 6133 5801 5861 5953 6067 6143 5807 5867 5981 6073 6151 5813 5869 5987 6079 6163 5821 5879 6007 6089 6173 Crc Standard Mathematical Tables And Formulas 33rd Edition Pdf
Source: https://es.b-ok.as/book/3418821/51a438?dsource=recommend
Posted by: keoraws1985.blogspot.com
0 Response to "Crc Standard Mathematical Tables And Formulas 33rd Edition Pdf"
Post a Comment