integers-exercises-programming.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section2.4Programming Exercises

¶

1The Sieve of Eratosthenes

One method of computing all of the prime numbers less than a certain fixed positive integer $N$ is to list all of the numbers $n$ such that $1 \lt n \lt N\text{.}$ Begin by eliminating all of the multiples of 2. Next eliminate all of the multiples of 3. Now eliminate all of the multiples of 5. Notice that 4 has already been crossed out. Continue in this manner, noticing that we do not have to go all the way to $N\text{;}$ it suffices to stop at $\sqrt{N}\text{.}$ Using this method, compute all of the prime numbers less than $N = 250\text{.}$ We can also use this method to find all of the integers that are relatively prime to an integer $N\text{.}$ Simply eliminate the prime factors of $N$ and all of their multiples. Using this method, find all of the numbers that are relatively prime to $N= 120\text{.}$ Using the Sieve of Eratosthenes, write a program that will compute all of the primes less than an integer $N\text{.}$

2

Let ${\mathbb N}^0 = {\mathbb N} \cup \{ 0 \}\text{.}$ Ackermann's function is the function $A :{\mathbb N}^0 \times {\mathbb N}^0 \rightarrow {\mathbb N}^0$ defined by the equations

$$\begin{align*} A(0, y) & = y + 1,\\ A(x + 1, 0) & = A(x, 1),\\ A(x + 1, y + 1) & = A(x, A(x + 1, y)). \end{align*}$$

Use this definition to compute $A(3, 1)\text{.}$ Write a program to evaluate Ackermann's function. Modify the program to count the number of statements executed in the program when Ackermann's function is evaluated. How many statements are executed in the evaluation of $A(4, 1)\text{?}$ What about $A(5, 1)\text{?}$

3

Write a computer program that will implement the Euclidean algorithm. The program should accept two positive integers $a$ and $b$ as input and should output $\gcd( a,b)$ as well as integers $r$ and $s$ such that

$$\begin{equation*} \gcd( a,b) = ra + sb. \end{equation*}$$