Elementary Number Theory with Programming (eBook)

Marty Lewinter, Jeanine Meyer (Autoren)

eBook Download: EPUB

2015
John Wiley & Sons (Verlag)
978-1-119-06277-6 (ISBN)

Infos

A highly successful presentation of the fundamental concepts of number theory and computer programming

Bridging an existing gap between mathematics and programming, Elementary Number Theory with Programming provides a unique introduction to elementary number theory with fundamental coverage of computer programming. Written by highly-qualified experts in the fields of computer science and mathematics, the book features accessible coverage for readers with various levels of experience and explores number theory in the context of programming without relying on advanced prerequisite knowledge and concepts in either area.

Elementary Number Theory with Programming features comprehensive coverage of the methodology and applications of the most well-known theorems, problems, and concepts in number theory. Using standard mathematical applications within the programming field, the book presents modular arithmetic and prime decomposition, which are the basis of the public-private key system of cryptography. In addition, the book includes:

• Numerous examples, exercises, and research challenges in each chapter to encourage readers to work through the discussed concepts and ideas
• Select solutions to the chapter exercises in an appendix
• Plentiful sample computer programs to aid comprehension of the presented material for readers who have either never done any programming or need to improve their existing skill set
• A related website with links to select exercises
• An Instructor's Solutions Manual available on a companion website

Elementary Number Theory with Programming is a useful textbook for undergraduate and graduate-level students majoring in mathematics or computer science, as well as an excellent supplement for teachers and students who would like to better understand and appreciate number theory and computer programming. The book is also an ideal reference for computer scientists, programmers, and researchers interested in the mathematical applications of programming.

Marty Lewinter, PhD, is Professor Emeritus of Mathematics at the State University of New York, Purchase College. The author of three books and more than 80 articles, he is Executive Director of Mathematics at American Digital University Services.

Jeanine Meyer, PhD, is Professor of Mathematics/Computer Science at the State University of New York, Purchase College. She is the author of six books as well as numerous journal articles.

Inhalt

Chapter I: Pythagoras: "Everything is number"

This first chapter presents several definitions for classes ofnumber, including triangular and perfect. The programs include onefor factoring numbers and one to test a conjecture up to a fixedlimit

Chapter II: Proof

The second chapter focuses on primes as well as approaches forsolving Pell equations. The programs include examples that countsteps to compare two different approaches

Chapter III: Pascal's Triangle

The third chapter focuses on factorial. It also presentsPascal's Triangle. The programs include examples thatgenerate factorial using iteration and using recursion and thusdemonstrate and compare important techniques in programming

Chapter IV: Divisors and Primes

The fourth chapter returns to factoring, demonstrating thealgorithm for producing the greatest common divisor of two numbers.The programs include one that uses the algorithm to produce the GCDof a pair of numbers and a program to produce the primedecomposition of a number

Chapter V: Modular Arithmetic

The fifth chapter presents mod equations. One program checks ifa mod equation is true and another determines the solvability of amod equation and then solves an equation that is solvable by abrute force approach

Chapter VI: Number Theoretic Functions

The sixth chapter is again on factoring and also the Taufunction. The programs include two distinct approaches tocalculating the Tau function

Chapter VII: Euler's Phi Function

The seventh chapter presents the Euler Phi function and otherfunctions. The programs demonstrate two approaches to calculatingthe Phi function

Chapter VIII: Sums and Partitions

The eighth chapter presents partitions, including binarypartitions. The exposition explains the central role of binaryrepresentation in computing and the programs produce the binarypartition using a built-in function and also using the mathematicalapproach explained in the chapter

Chapter IX: Cryptography

The ninth chapter presents codes from very old to modern day.The programs include different ways to generate counts of lettersand also Fermat factoring

Answers or hints to selected exercises

Sample programs at the end of each chapter. You canaccess working examples of the sample programs at thewebsite: http://faculty.purchase.edu/jeanine.meyer/numbertheory/

Rezensionen

"It consists of nine chapters, all including the corresponding programs along with their mathematical content. The mathematical structure is also interesting and well-formed starting from special numbers, primes and Pell equation, to Pascal's triangle, prime decomposition and modular arithmetic and finishing with number-theoretic functions, the Euler Phi-function, sums and partitions and the classical application to cryptography. It is also remarkable that the main scope of the programs is defined before their use from the reader, providing him the best orientation for his study." (Zentralblatt MATH 2016)

Textauszug

1
SPECIAL NUMBERS: TRIANGULAR, OBLONG, PERFECT, DEFICIENT, AND ABUNDANT

We start our introduction to number theory with definitions, properties, and relationships of several categories of numbers.

TRIANGULAR NUMBERS

Triangular numbers are those that can be written as the sum of a consecutive series of (whole) numbers beginning with 1. Thus 6 is triangular because it is the sum of the first three numbers: 6 = 1 + 2 + 3. The first few triangular numbers are 1, 3, 6, 10, 15, 21, 28, 36, 45, and 55. We denote the nth triangular number by tn. Thus t5 = 1 + 2 + 3 + 4 + 5 = 15. More generally,

(1.1)

Our first program, calculating a specific triangular number, shows the format of an HTML document. The first line specifies the doctype. The rest is an html element, starting with <html> and ending with </html>. Within the html element is a head element and a body element. In this case, the body element is empty. The head element contains a meta tag specifying the character type (it can be omitted), a title, and a script element. All the action is in the script element.

The code makes use of standard programming constructs such as variables and functions and for-loops (if you don’t understand what these terms are, please consult any beginner book on programming. Shameless plug: go to The Essential Guide to HTML5: Using Games to Learn HTML5 and JavaScript, http://www.apress.com/9781430233831).

The specific triangular number we want is specified in the coding by setting the variable n . This is termed hard-coding. The computation is done using a for-loop. The for-loop adds up the values from 1 to n , exactly following Equation 1.1. The built-in method document.write writes out the result.

The challenge in Exercise 1 is to compare coding using Equation 1.1 versus Equation 1.2. The challenge is that computers are very fast. I use the built-in Date function with the method getTime to get the number of milliseconds from a base date at the start and after the computation. It turns out that computing the millionth triangular number takes 3 ms! You can experiment with different values. Using the formula given in Equation 1.2 would be much, much faster. Give it a try.

The nth triangular number is given by the formula:

(1.2)

Example:

Example:

Write 6 + 7 + 8 + 9 + 10 + 11 as the difference of two triangular numbers. We observe that 6 + 7 + 8 + 9 + 10 + 11 = (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11) − (1 + 2 + 3 + 4 + 5), which is t11 − t5.

Example:

Generalize the previous example to any consecutive sum such as 45 + 46 + + 987. Note that a + (a+1) + (a+2) +…+ b = (1 + 2 + 3 + … + b)–(1 + 2 + 3 + … + (a-1)) = tb–ta-1. By letting a = 6 and b = 11, we get the result of the previous example.

It should be noted that

(1.3)

The sum of any two consecutive triangular numbers is a square. For example, t4 + t3 = 10 + 6 = 16 = 42 and t5 + t4 = 15 + 10 = 25 = 52. This is expressed by the formula

(1.4)

Example:

Verify (1.4) for n = 10. We have t10 + t9 = 55 + 45 = 102.

Example:

Find two triangular numbers whose sum is 900. Since 900 = 302, we have n = 30. Then using (1.4), .

The sum of the reciprocals of all the triangular numbers is 2. Formally,

(1.5)

OBLONG NUMBERS AND SQUARES

A positive integer of the form n(n + 1) is called oblong. The nth oblong number is the sum of the first n even numbers. To see this, observe that the nth even number is 2n. Then we have , the nth oblong number. What about the sum of the first n odd numbers? The nth odd number is 2n − 1. So , in which −1 appears n times. We then get . So the sum of the first n odd numbers is n2.

Example:

The sum of the first 5 odd numbers is 25. (Check this: 1 + 3 + 5 + 7 + 9 = 25.) More impressively, the sum of the first 100 odd numbers is 1002 = 10,000.

The great French mathematician LaGrange (1736–1813) showed in the late eighteenth century that every positive number can be written as a sum of four or fewer squares. Thus, for example, 30 = 25 + 4 + 1.

Number theorists are fond of numbers, such as 40, which are the sum of only two squares (e.g., 40 = 36 + 4).

The Pythagoreans computed the sum of the first n powers of 2. Let

1. . Then
2. .

Now subtract Equation (a) from Equation (b), and we get S = 2n − 1. We have, then, the following formula:

(1.6)

With a minor change in the proof of (1.6), we obtain an analogous formula for the sum of the first n powers of any base. Let . Then . Subtract the first equation from the second, and we get (a − 1)S = an − 1. Upon division by a − 1, we obtain the following formula:

(1.7)

DEFICIENT, ABUNDANT, AND PERFECT NUMBERS

The Pythagoreans classified all numbers as deficient, abundant, or perfect. Given a number, find all of its proper factors, that is, all numbers that go into it (with the exclusion of the given number). The proper factors of 30, for example, are 1, 2, 3, 5, 6, 10, and 15.

Generating a list of the factors of a number is easy in JavaScript (and other programming languages), though it appears tedious to us. The modulo operation, %, determines the remainder. So if n is the number and f is a candidate factor, then

n % f

will produce the remainder of n divided by f. If this is 0, then f is a factor. If f < n, then f is a proper factor.

The program uses a for-loop going from 1 up to but not including n. If it is a factor, the number is written out in the html document using document.write and a variable count is incremented.

If the sum of the proper factors of n is less than n, we call n deficient. If the sum exceeds n, it is called abundant. If the sum equals n, we call it perfect. For example, 8 is deficient since 1 + 2 + 4 < 8, 18 is abundant since 1 + 2 + 3 + 6 + 9 > 18, and 28 is perfect since 1 + 2 + 4 + 7 + 14 = 28. The smallest perfect number is 6. The first few perfect numbers are 6, 28, 496, and 8128. It is not known today whether there are infinitely many perfect numbers. Moreover, all known perfect numbers are even. No one knows if there are any odd perfect numbers! Incidentally, the smallest abundant odd number is 945, while the smallest abundant even number is 12.

The program to characterize a number as deficient, perfect, or abundant was made by modifying the previous one that listed and counted the number of proper factors. To make the determination of whether a number n is deficient, perfect, or abundant, the program has to add up the proper factors. So the statement count++ is removed and the statement

sum += i;

is inserted. By the way, this is shorthand for taking the original value of the variable sum, adding one to it and then assigning that back to the variable sum.

sum = sum + i;

I also changed the name of the function to addUpFactors. I tested the program using the specific numbers given in the text.

The Pythagoreans found an amazing method for finding perfect numbers. They observed, using (1.6), that sums of the form are prime for certain values of n and are...

Produkt-Details

• Erscheint lt. Verlag: 8.5.2015
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Arithmetik / Zahlentheorie
• Themenwelt: Technik
• Schlagworte: computer programming • Computer Science • cryptography • divisors and prime decomposition • Euler's Phi function • fibonacci sequence • Informatik • Kryptographie • <p>number theory • Mathematics • Mathematik • modular arithmetic • number theoretic functions • Number Theory • Pascal's triangle • special numbers • sums and partitions</p> • the Pell equation • triangle numbers • Zahlentheorie
• ISBN-10: 1-119-06277-2 / 1119062772
• ISBN-13: 978-1-119-06277-6 / 9781119062776