Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

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*}