Exercises · Numerical algorithms

Exercises · Chapter 5 · each solution opens with a click · Chapter 5: Numerical algorithms · Exercises, volume 1 (PDF)

The exercises of this chapter apply the four algorithms of the chapter «Numerical algorithms»: ChangeOfBase, BasicPrimalityTest and PrimalityTest, SieveOfEratosthenes, EuclideanAlgorithm. The following facts of the chapter are used in the solutions.

Division with remainder. For every natural number \(n\) and every natural number \(b \ge 1\):

\[ n = \lfloor n/b \rfloor \; b + (n \bmod b) \qquad \text{with} \qquad 0 \le n \bmod b < b . \]

Change of base. If \(n = (d_{k-1} \dots d_1 d_0)_b\), then \(n \bmod b = d_0\) and \(\lfloor n/b \rfloor = (d_{k-1} \dots d_1)_b\); the number of digits is \(\lfloor \log_b n \rfloor + 1\). ChangeOfBase stores the digit \(d_{k-1}\) in the entry \(d[k]\).

Primality. A natural number \(n \ge 2\) is prime if and only if no natural number in \(\{2, 3, \dots, \lfloor \sqrt{n} \rfloor\}\) is a divisor of \(n\).

Sieve. The marking of the multiples of a prime \(p\) starts at \(p^2\), and the outer loop stops at \(\lfloor \sqrt{n} \rfloor\). In the trace tables, blue cells are the entries just set to \(0\) and red cells the current value of \(p\).

Greatest common divisor. For every pair of natural numbers \(n, m \ge 1\):

\[ \gcd(n, m) = \gcd(m,\ n \bmod m) \qquad \text{and} \qquad \gcd(n, 0) = n . \]

Two natural numbers are coprime if and only if their greatest common divisor is \(1\).

Exercise 5.1: Numerical algorithms (E1)

Consider the following natural number, written as a sequence of digits in base ten:

\[ (16)_{10} \]

Questions

1. Convert the number into base \(b=2\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

2. Convert the number into base \(b=3\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

3. Convert the number into base \(b=4\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

4. Convert the number into base \(b=5\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

5. Convert the number into base \(b=6\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

Solution

1. Translation of \(16\) into base \(b=2\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(16\)	\(16/2\)	\(8\)	\(0\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(8\)	\(8/2\)	\(4\)	\(0\)	\(d[2] = d_{1}\)
   \(3\)	\(4\)	\(4/2\)	\(2\)	\(0\)	\(d[3] = d_{2}\)
   \(4\)	\(2\)	\(2/2\)	\(1\)	\(0\)	\(d[4] = d_{3}\)
   \(5\)	\(1\)	\(1/2\)	\(0\)	\(1\)	\(d[5] = d_{4}\) (MSD)

   Accordingly, \(16\) in base \(2\) is \((10000)_{2}\), with \(nd = \lfloor \log_{2} 16 \rfloor + 1 = 5\) digits.

2. Translation of \(16\) into base \(b=3\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(16\)	\(16/3\)	\(5\)	\(1\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(5\)	\(5/3\)	\(1\)	\(2\)	\(d[2] = d_{1}\)
   \(3\)	\(1\)	\(1/3\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (MSD)

   Accordingly, \(16\) in base \(3\) is \((121)_{3}\), with \(nd = \lfloor \log_{3} 16 \rfloor + 1 = 3\) digits.

3. Translation of \(16\) into base \(b=4\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(16\)	\(16/4\)	\(4\)	\(0\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(4\)	\(4/4\)	\(1\)	\(0\)	\(d[2] = d_{1}\)
   \(3\)	\(1\)	\(1/4\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (MSD)

   Accordingly, \(16\) in base \(4\) is \((100)_{4}\), with \(nd = \lfloor \log_{4} 16 \rfloor + 1 = 3\) digits.

4. Translation of \(16\) into base \(b=5\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(16\)	\(16/5\)	\(3\)	\(1\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(3\)	\(3/5\)	\(0\)	\(3\)	\(d[2] = d_{1}\) (MSD)

   Accordingly, \(16\) in base \(5\) is \((31)_{5}\), with \(nd = \lfloor \log_{5} 16 \rfloor + 1 = 2\) digits.

5. Translation of \(16\) into base \(b=6\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(16\)	\(16/6\)	\(2\)	\(4\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(2\)	\(2/6\)	\(0\)	\(2\)	\(d[2] = d_{1}\) (MSD)

   Accordingly, \(16\) in base \(6\) is \((24)_{6}\), with \(nd = \lfloor \log_{6} 16 \rfloor + 1 = 2\) digits.

Exercise 5.2: Numerical algorithms (E2)

Consider the following natural number, written as a sequence of digits in base ten:

\[ (25)_{10} \]

Questions

1. Convert the number into base \(b=2\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

2. Convert the number into base \(b=3\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

3. Convert the number into base \(b=4\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

4. Convert the number into base \(b=5\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

5. Convert the number into base \(b=7\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

Solution

1. Translation of \(25\) into base \(b=2\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(25\)	\(25/2\)	\(12\)	\(1\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(12\)	\(12/2\)	\(6\)	\(0\)	\(d[2] = d_{1}\)
   \(3\)	\(6\)	\(6/2\)	\(3\)	\(0\)	\(d[3] = d_{2}\)
   \(4\)	\(3\)	\(3/2\)	\(1\)	\(1\)	\(d[4] = d_{3}\)
   \(5\)	\(1\)	\(1/2\)	\(0\)	\(1\)	\(d[5] = d_{4}\) (MSD)

   Accordingly, \(25\) in base \(2\) is \((11001)_{2}\), with \(nd = \lfloor \log_{2} 25 \rfloor + 1 = 5\) digits.

2. Translation of \(25\) into base \(b=3\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(25\)	\(25/3\)	\(8\)	\(1\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(8\)	\(8/3\)	\(2\)	\(2\)	\(d[2] = d_{1}\)
   \(3\)	\(2\)	\(2/3\)	\(0\)	\(2\)	\(d[3] = d_{2}\) (MSD)

   Accordingly, \(25\) in base \(3\) is \((221)_{3}\), with \(nd = \lfloor \log_{3} 25 \rfloor + 1 = 3\) digits.

3. Translation of \(25\) into base \(b=4\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(25\)	\(25/4\)	\(6\)	\(1\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(6\)	\(6/4\)	\(1\)	\(2\)	\(d[2] = d_{1}\)
   \(3\)	\(1\)	\(1/4\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (MSD)

   Accordingly, \(25\) in base \(4\) is \((121)_{4}\), with \(nd = \lfloor \log_{4} 25 \rfloor + 1 = 3\) digits.

4. Translation of \(25\) into base \(b=5\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(25\)	\(25/5\)	\(5\)	\(0\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(5\)	\(5/5\)	\(1\)	\(0\)	\(d[2] = d_{1}\)
   \(3\)	\(1\)	\(1/5\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (MSD)

   Accordingly, \(25\) in base \(5\) is \((100)_{5}\), with \(nd = \lfloor \log_{5} 25 \rfloor + 1 = 3\) digits.

5. Translation of \(25\) into base \(b=7\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(25\)	\(25/7\)	\(3\)	\(4\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(3\)	\(3/7\)	\(0\)	\(3\)	\(d[2] = d_{1}\) (MSD)

   Accordingly, \(25\) in base \(7\) is \((34)_{7}\), with \(nd = \lfloor \log_{7} 25 \rfloor + 1 = 2\) digits.

Exercise 5.3: Numerical algorithms (E3)

Consider the following natural number, written as a sequence of digits in base ten:

\[ (42)_{10} \]

Questions

1. Convert the number into base \(b=2\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

2. Convert the number into base \(b=3\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

3. Convert the number into base \(b=5\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

4. Convert the number into base \(b=6\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

5. Convert the number into base \(b=8\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

Solution

1. Translation of \(42\) into base \(b=2\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(42\)	\(42/2\)	\(21\)	\(0\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(21\)	\(21/2\)	\(10\)	\(1\)	\(d[2] = d_{1}\)
   \(3\)	\(10\)	\(10/2\)	\(5\)	\(0\)	\(d[3] = d_{2}\)
   \(4\)	\(5\)	\(5/2\)	\(2\)	\(1\)	\(d[4] = d_{3}\)
   \(5\)	\(2\)	\(2/2\)	\(1\)	\(0\)	\(d[5] = d_{4}\)
   \(6\)	\(1\)	\(1/2\)	\(0\)	\(1\)	\(d[6] = d_{5}\) (MSD)

   Accordingly, \(42\) in base \(2\) is \((101010)_{2}\), with \(nd = \lfloor \log_{2} 42 \rfloor + 1 = 6\) digits.

2. Translation of \(42\) into base \(b=3\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(42\)	\(42/3\)	\(14\)	\(0\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(14\)	\(14/3\)	\(4\)	\(2\)	\(d[2] = d_{1}\)
   \(3\)	\(4\)	\(4/3\)	\(1\)	\(1\)	\(d[3] = d_{2}\)
   \(4\)	\(1\)	\(1/3\)	\(0\)	\(1\)	\(d[4] = d_{3}\) (MSD)

   Accordingly, \(42\) in base \(3\) is \((1120)_{3}\), with \(nd = \lfloor \log_{3} 42 \rfloor + 1 = 4\) digits.

3. Translation of \(42\) into base \(b=5\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(42\)	\(42/5\)	\(8\)	\(2\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(8\)	\(8/5\)	\(1\)	\(3\)	\(d[2] = d_{1}\)
   \(3\)	\(1\)	\(1/5\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (MSD)

   Accordingly, \(42\) in base \(5\) is \((132)_{5}\), with \(nd = \lfloor \log_{5} 42 \rfloor + 1 = 3\) digits.

4. Translation of \(42\) into base \(b=6\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(42\)	\(42/6\)	\(7\)	\(0\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(7\)	\(7/6\)	\(1\)	\(1\)	\(d[2] = d_{1}\)
   \(3\)	\(1\)	\(1/6\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (MSD)

   Accordingly, \(42\) in base \(6\) is \((110)_{6}\), with \(nd = \lfloor \log_{6} 42 \rfloor + 1 = 3\) digits.

5. Translation of \(42\) into base \(b=8\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(42\)	\(42/8\)	\(5\)	\(2\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(5\)	\(5/8\)	\(0\)	\(5\)	\(d[2] = d_{1}\) (MSD)

   Accordingly, \(42\) in base \(8\) is \((52)_{8}\), with \(nd = \lfloor \log_{8} 42 \rfloor + 1 = 2\) digits.

Exercise 5.4: Numerical algorithms (E4)

Consider the following natural number, written as a sequence of digits in base ten:

\[ (63)_{10} \]

Questions

1. Convert the number into base \(b=2\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

2. Convert the number into base \(b=4\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

3. Convert the number into base \(b=7\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

4. Convert the number into base \(b=8\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

5. Convert the number into base \(b=9\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

Solution

1. Translation of \(63\) into base \(b=2\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(63\)	\(63/2\)	\(31\)	\(1\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(31\)	\(31/2\)	\(15\)	\(1\)	\(d[2] = d_{1}\)
   \(3\)	\(15\)	\(15/2\)	\(7\)	\(1\)	\(d[3] = d_{2}\)
   \(4\)	\(7\)	\(7/2\)	\(3\)	\(1\)	\(d[4] = d_{3}\)
   \(5\)	\(3\)	\(3/2\)	\(1\)	\(1\)	\(d[5] = d_{4}\)
   \(6\)	\(1\)	\(1/2\)	\(0\)	\(1\)	\(d[6] = d_{5}\) (MSD)

   Accordingly, \(63\) in base \(2\) is \((111111)_{2}\), with \(nd = \lfloor \log_{2} 63 \rfloor + 1 = 6\) digits.

2. Translation of \(63\) into base \(b=4\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(63\)	\(63/4\)	\(15\)	\(3\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(15\)	\(15/4\)	\(3\)	\(3\)	\(d[2] = d_{1}\)
   \(3\)	\(3\)	\(3/4\)	\(0\)	\(3\)	\(d[3] = d_{2}\) (MSD)

   Accordingly, \(63\) in base \(4\) is \((333)_{4}\), with \(nd = \lfloor \log_{4} 63 \rfloor + 1 = 3\) digits.

3. Translation of \(63\) into base \(b=7\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(63\)	\(63/7\)	\(9\)	\(0\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(9\)	\(9/7\)	\(1\)	\(2\)	\(d[2] = d_{1}\)
   \(3\)	\(1\)	\(1/7\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (MSD)

   Accordingly, \(63\) in base \(7\) is \((120)_{7}\), with \(nd = \lfloor \log_{7} 63 \rfloor + 1 = 3\) digits.

4. Translation of \(63\) into base \(b=8\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(63\)	\(63/8\)	\(7\)	\(7\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(7\)	\(7/8\)	\(0\)	\(7\)	\(d[2] = d_{1}\) (MSD)

   Accordingly, \(63\) in base \(8\) is \((77)_{8}\), with \(nd = \lfloor \log_{8} 63 \rfloor + 1 = 2\) digits.

5. Translation of \(63\) into base \(b=9\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(63\)	\(63/9\)	\(7\)	\(0\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(7\)	\(7/9\)	\(0\)	\(7\)	\(d[2] = d_{1}\) (MSD)

   Accordingly, \(63\) in base \(9\) is \((70)_{9}\), with \(nd = \lfloor \log_{9} 63 \rfloor + 1 = 2\) digits.

Exercise 5.5: Numerical algorithms (E5)

Consider the following natural number, written as a sequence of digits in base ten:

\[ (100)_{10} \]

Questions

1. Convert the number into base \(b=2\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

2. Convert the number into base \(b=3\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

3. Convert the number into base \(b=5\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

4. Convert the number into base \(b=8\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

5. Convert the number into base \(b=16\) with the algorithm ChangeOfBase, showing the quotient and the remainder of every division.

Solution

1. Translation of \(100\) into base \(b=2\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(100\)	\(100/2\)	\(50\)	\(0\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(50\)	\(50/2\)	\(25\)	\(0\)	\(d[2] = d_{1}\)
   \(3\)	\(25\)	\(25/2\)	\(12\)	\(1\)	\(d[3] = d_{2}\)
   \(4\)	\(12\)	\(12/2\)	\(6\)	\(0\)	\(d[4] = d_{3}\)
   \(5\)	\(6\)	\(6/2\)	\(3\)	\(0\)	\(d[5] = d_{4}\)
   \(6\)	\(3\)	\(3/2\)	\(1\)	\(1\)	\(d[6] = d_{5}\)
   \(7\)	\(1\)	\(1/2\)	\(0\)	\(1\)	\(d[7] = d_{6}\) (MSD)

   Accordingly, \(100\) in base \(2\) is \((1100100)_{2}\), with \(nd = \lfloor \log_{2} 100 \rfloor + 1 = 7\) digits.

2. Translation of \(100\) into base \(b=3\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(100\)	\(100/3\)	\(33\)	\(1\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(33\)	\(33/3\)	\(11\)	\(0\)	\(d[2] = d_{1}\)
   \(3\)	\(11\)	\(11/3\)	\(3\)	\(2\)	\(d[3] = d_{2}\)
   \(4\)	\(3\)	\(3/3\)	\(1\)	\(0\)	\(d[4] = d_{3}\)
   \(5\)	\(1\)	\(1/3\)	\(0\)	\(1\)	\(d[5] = d_{4}\) (MSD)

   Accordingly, \(100\) in base \(3\) is \((10201)_{3}\), with \(nd = \lfloor \log_{3} 100 \rfloor + 1 = 5\) digits.

3. Translation of \(100\) into base \(b=5\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(100\)	\(100/5\)	\(20\)	\(0\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(20\)	\(20/5\)	\(4\)	\(0\)	\(d[2] = d_{1}\)
   \(3\)	\(4\)	\(4/5\)	\(0\)	\(4\)	\(d[3] = d_{2}\) (MSD)

   Accordingly, \(100\) in base \(5\) is \((400)_{5}\), with \(nd = \lfloor \log_{5} 100 \rfloor + 1 = 3\) digits.

4. Translation of \(100\) into base \(b=8\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(100\)	\(100/8\)	\(12\)	\(4\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(12\)	\(12/8\)	\(1\)	\(4\)	\(d[2] = d_{1}\)
   \(3\)	\(1\)	\(1/8\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (MSD)

   Accordingly, \(100\) in base \(8\) is \((144)_{8}\), with \(nd = \lfloor \log_{8} 100 \rfloor + 1 = 3\) digits.

5. Translation of \(100\) into base \(b=16\):

   iteration \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	digit
   \(1\)	\(100\)	\(100/16\)	\(6\)	\(4\)	\(d[1] = d_{0}\) (LSD)
   \(2\)	\(6\)	\(6/16\)	\(0\)	\(6\)	\(d[2] = d_{1}\) (MSD)

   Accordingly, \(100\) in base \(16\) is \((64)_{16}\), with \(nd = \lfloor \log_{16} 100 \rfloor + 1 = 2\) digits.

Exercise 5.6: Numerical algorithms (E6)

Consider the following natural numbers:

\[ n \in \{2,\ 7,\ 9,\ 11,\ 25\} \]

Questions

1. Apply the algorithm PrimalityTest to each number in the list. For each \(n\), show the execution step by step, indicating the value of \(\lfloor\sqrt{n}\rfloor\), the values of \(d\) tested, and the result of each test \(n \bmod d = 0\).

Solution

1. Execution of PrimalityTest on each number.

   Check \(n = 2\): \(\lfloor\sqrt{2}\rfloor = 1\).

   \(d\)	\(2 \bmod d\)	action
   The loop is not executed, since \(2 > 1\).
   Return true: 2 is prime.

   Check \(n = 7\): \(\lfloor\sqrt{7}\rfloor = 2\).

   \(d\)	\(7 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   Loop ends. Return true: 7 is prime.

   Check \(n = 9\): \(\lfloor\sqrt{9}\rfloor = 3\).

   \(d\)	\(9 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   \(3\)	\(0\)	return false
   9 is not prime (\(9 = 3 \cdot 3\)).

   Check \(n = 11\): \(\lfloor\sqrt{11}\rfloor = 3\).

   \(d\)	\(11 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   \(3\)	\(2 \ne 0\)	continue
   Loop ends. Return true: 11 is prime.

   Check \(n = 25\): \(\lfloor\sqrt{25}\rfloor = 5\).

   \(d\)	\(25 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   \(3\)	\(1 \ne 0\)	continue
   \(4\)	\(1 \ne 0\)	continue
   \(5\)	\(0\)	return false
   25 is not prime (\(25 = 5 \cdot 5\)).

Exercise 5.7: Numerical algorithms (E7)

Consider the following natural numbers:

\[ n \in \{4,\ 13,\ 17,\ 49,\ 97\} \]

Questions

1. Apply the algorithm PrimalityTest to each number in the list. For each \(n\), show the execution step by step, indicating the value of \(\lfloor\sqrt{n}\rfloor\), the values of \(d\) tested, and the result of each test \(n \bmod d = 0\).

Solution

1. Execution of PrimalityTest on each number.

   Check \(n = 4\): \(\lfloor\sqrt{4}\rfloor = 2\).

   \(d\)	\(4 \bmod d\)	action
   \(2\)	\(0\)	return false
   4 is not prime (\(4 = 2 \cdot 2\)).

   Check \(n = 13\): \(\lfloor\sqrt{13}\rfloor = 3\).

   \(d\)	\(13 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   \(3\)	\(1 \ne 0\)	continue
   Loop ends. Return true: 13 is prime.

   Check \(n = 17\): \(\lfloor\sqrt{17}\rfloor = 4\).

   \(d\)	\(17 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   \(3\)	\(2 \ne 0\)	continue
   \(4\)	\(1 \ne 0\)	continue
   Loop ends. Return true: 17 is prime.

   Check \(n = 49\): \(\lfloor\sqrt{49}\rfloor = 7\).

   \(d\)	\(49 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   \(3\)	\(1 \ne 0\)	continue
   \(4\)	\(1 \ne 0\)	continue
   \(5\)	\(4 \ne 0\)	continue
   \(6\)	\(1 \ne 0\)	continue
   \(7\)	\(0\)	return false
   49 is not prime (\(49 = 7 \cdot 7\)).

   Check \(n = 97\): \(\lfloor\sqrt{97}\rfloor = 9\).

   \(d\)	\(97 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   \(3\)	\(1 \ne 0\)	continue
   \(4\)	\(1 \ne 0\)	continue
   \(5\)	\(2 \ne 0\)	continue
   \(6\)	\(1 \ne 0\)	continue
   \(7\)	\(6 \ne 0\)	continue
   \(8\)	\(1 \ne 0\)	continue
   \(9\)	\(7 \ne 0\)	continue
   Loop ends. Return true: 97 is prime.

Exercise 5.8: Numerical algorithms (E8)

Consider the following natural numbers:

\[ n \in \{1,\ 3,\ 15,\ 23,\ 36\} \]

Questions

1. Apply the algorithm PrimalityTest to each number in the list. For each \(n\), show the execution step by step, indicating the value of \(\lfloor\sqrt{n}\rfloor\), the values of \(d\) tested, and the result of each test \(n \bmod d = 0\).

Solution

1. Execution of PrimalityTest on each number.

   Check \(n = 1\): \(n < 2\).

   \(d\)	\(1 \bmod d\)	action
   \(n = 1 < 2\): return false immediately.
   1 is not prime.

   Check \(n = 3\): \(\lfloor\sqrt{3}\rfloor = 1\).

   \(d\)	\(3 \bmod d\)	action
   The loop is not executed, since \(2 > 1\).
   Return true: 3 is prime.

   Check \(n = 15\): \(\lfloor\sqrt{15}\rfloor = 3\).

   \(d\)	\(15 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   \(3\)	\(0\)	return false
   15 is not prime (\(15 = 3 \cdot 5\)).

   Check \(n = 23\): \(\lfloor\sqrt{23}\rfloor = 4\).

   \(d\)	\(23 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   \(3\)	\(2 \ne 0\)	continue
   \(4\)	\(3 \ne 0\)	continue
   Loop ends. Return true: 23 is prime.

   Check \(n = 36\): \(\lfloor\sqrt{36}\rfloor = 6\).

   \(d\)	\(36 \bmod d\)	action
   \(2\)	\(0\)	return false
   36 is not prime (\(36 = 2 \cdot 18\)).

Exercise 5.9: Numerical algorithms (E9)

Consider the natural numbers \(n = 29\) and \(n = 49\).

Questions

1. For each number \(n\), apply both the algorithm BasicPrimalityTest (loop up to \(\lfloor n/2 \rfloor\)) and the algorithm PrimalityTest (loop up to \(\lfloor\sqrt{n}\rfloor\)). Show the step-by-step execution of each algorithm.

2. For each number, count the number of iterations performed by each algorithm and compare.

Solution

1. Step-by-step execution.

   Case \(n = 29\).

   BasicPrimalityTest (\(\lfloor 29/2 \rfloor = 14\)):

   \(d\)	\(29 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   \(3\)	\(2 \ne 0\)	continue
   \(4\)	\(1 \ne 0\)	continue
   \(5\)	\(4 \ne 0\)	continue
   \(6\)	\(5 \ne 0\)	continue
   \(7\)	\(1 \ne 0\)	continue
   \(8\)	\(5 \ne 0\)	continue
   \(9\)	\(2 \ne 0\)	continue
   \(10\)	\(9 \ne 0\)	continue
   \(11\)	\(7 \ne 0\)	continue
   \(12\)	\(5 \ne 0\)	continue
   \(13\)	\(3 \ne 0\)	continue
   \(14\)	\(1 \ne 0\)	continue
   Loop ends. Return true: 29 is prime. (13 iterations)

   PrimalityTest (\(\lfloor\sqrt{29}\rfloor = 5\)):

   \(d\)	\(29 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   \(3\)	\(2 \ne 0\)	continue
   \(4\)	\(1 \ne 0\)	continue
   \(5\)	\(4 \ne 0\)	continue
   Loop ends. Return true: 29 is prime. (4 iterations)

   Case \(n = 49\).

   BasicPrimalityTest (\(\lfloor 49/2 \rfloor = 24\)):

   \(d\)	\(49 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   \(3\)	\(1 \ne 0\)	continue
   \(4\)	\(1 \ne 0\)	continue
   \(5\)	\(4 \ne 0\)	continue
   \(6\)	\(1 \ne 0\)	continue
   \(7\)	\(0\)	return false
   49 is not prime (\(49 = 7 \cdot 7\)). (6 iterations)

   PrimalityTest (\(\lfloor\sqrt{49}\rfloor = 7\)):

   \(d\)	\(49 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   \(3\)	\(1 \ne 0\)	continue
   \(4\)	\(1 \ne 0\)	continue
   \(5\)	\(4 \ne 0\)	continue
   \(6\)	\(1 \ne 0\)	continue
   \(7\)	\(0\)	return false
   49 is not prime (\(49 = 7 \cdot 7\)). (6 iterations)

2. Comparison of the iterations:

   \(n\)	\(\lfloor n/2 \rfloor\)	\(\lfloor\sqrt{n}\rfloor\)	BasicPrimalityTest	PrimalityTest
   \(29\)	\(14\)	\(5\)	\(13\)	\(4\)
   \(49\)	\(24\)	\(7\)	\(6\)	\(6\)

   For \(n = 29\) (prime), PrimalityTest performs only \(4\) iterations instead of \(13\): both algorithms must test all their candidates, and PrimalityTest has far fewer. For \(n = 49\) (composite, with smallest divisor \(7 = \sqrt{49}\)), both algorithms stop at the same divisor \(d = 7\), so the number of iterations is the same.

Exercise 5.10: Numerical algorithms (E10)

Consider the natural numbers \(n \in \{2, 3, 4, \dots, 30\}\).

Questions

1. Apply the algorithm PrimalityTest to each natural number \(n \in \{2, 3, \dots, 30\}\) and determine which numbers are prime. For each \(n\), report the value of \(\lfloor\sqrt{n}\rfloor\), whether a divisor was found (and which one), and the result.

2. List all the prime numbers in \(\{2, 3, \dots, 30\}\) and count them.

Solution

1. Summary of the executions of PrimalityTest (the divisor reported is the first one found, that is, the value of \(d\) for which the function returns false):

   \(n\)	\(\lfloor\sqrt{n}\rfloor\)	first divisor found	result
   \(2\)	\(1\)	none (loop not executed)	prime
   \(3\)	\(1\)	none (loop not executed)	prime
   \(4\)	\(2\)	\(d = 2\)	not prime (\(4 = 2 \cdot 2\))
   \(5\)	\(2\)	none	prime
   \(6\)	\(2\)	\(d = 2\)	not prime (\(6 = 2 \cdot 3\))
   \(7\)	\(2\)	none	prime
   \(8\)	\(2\)	\(d = 2\)	not prime (\(8 = 2 \cdot 4\))
   \(9\)	\(3\)	\(d = 3\)	not prime (\(9 = 3 \cdot 3\))
   \(10\)	\(3\)	\(d = 2\)	not prime (\(10 = 2 \cdot 5\))
   \(11\)	\(3\)	none	prime
   \(12\)	\(3\)	\(d = 2\)	not prime (\(12 = 2 \cdot 6\))
   \(13\)	\(3\)	none	prime
   \(14\)	\(3\)	\(d = 2\)	not prime (\(14 = 2 \cdot 7\))
   \(15\)	\(3\)	\(d = 3\)	not prime (\(15 = 3 \cdot 5\))
   \(16\)	\(4\)	\(d = 2\)	not prime (\(16 = 2 \cdot 8\))
   \(17\)	\(4\)	none	prime
   \(18\)	\(4\)	\(d = 2\)	not prime (\(18 = 2 \cdot 9\))
   \(19\)	\(4\)	none	prime
   \(20\)	\(4\)	\(d = 2\)	not prime (\(20 = 2 \cdot 10\))
   \(21\)	\(4\)	\(d = 3\)	not prime (\(21 = 3 \cdot 7\))
   \(22\)	\(4\)	\(d = 2\)	not prime (\(22 = 2 \cdot 11\))
   \(23\)	\(4\)	none	prime
   \(24\)	\(4\)	\(d = 2\)	not prime (\(24 = 2 \cdot 12\))
   \(25\)	\(5\)	\(d = 5\)	not prime (\(25 = 5 \cdot 5\))
   \(26\)	\(5\)	\(d = 2\)	not prime (\(26 = 2 \cdot 13\))
   \(27\)	\(5\)	\(d = 3\)	not prime (\(27 = 3 \cdot 9\))
   \(28\)	\(5\)	\(d = 2\)	not prime (\(28 = 2 \cdot 14\))
   \(29\)	\(5\)	none	prime
   \(30\)	\(5\)	\(d = 2\)	not prime (\(30 = 2 \cdot 15\))

2. The prime numbers in \(\{2, 3, \dots, 30\}\) are

   \[ 2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29 \]

   There are \(10\) prime numbers in \(\{2, 3, \dots, 30\}\).

Exercise 5.11: Numerical algorithms (E11)

Consider the following natural numbers:

\[ n \in \{6,\ 19,\ 49,\ 53,\ 91\} \]

Questions

1. Apply the algorithm PrimalityTest to each number in the list. For each \(n\), show the execution step by step, indicating the value of \(\lfloor\sqrt{n}\rfloor\), the values of \(d\) tested, and the result of each test \(n \bmod d = 0\).

Solution

1. Execution of PrimalityTest on each number.

   Check \(n = 6\): \(\lfloor\sqrt{6}\rfloor = 2\).

   \(d\)	\(6 \bmod d\)	action
   \(2\)	\(0\)	return false
   6 is not prime (\(6 = 2 \cdot 3\)).

   Check \(n = 19\): \(\lfloor\sqrt{19}\rfloor = 4\).

   \(d\)	\(19 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   \(3\)	\(1 \ne 0\)	continue
   \(4\)	\(3 \ne 0\)	continue
   Loop ends. Return true: 19 is prime.

   Check \(n = 49\): \(\lfloor\sqrt{49}\rfloor = 7\).

   \(d\)	\(49 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   \(3\)	\(1 \ne 0\)	continue
   \(4\)	\(1 \ne 0\)	continue
   \(5\)	\(4 \ne 0\)	continue
   \(6\)	\(1 \ne 0\)	continue
   \(7\)	\(0\)	return false
   49 is not prime (\(49 = 7 \cdot 7\)).

   Check \(n = 53\): \(\lfloor\sqrt{53}\rfloor = 7\).

   \(d\)	\(53 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   \(3\)	\(2 \ne 0\)	continue
   \(4\)	\(1 \ne 0\)	continue
   \(5\)	\(3 \ne 0\)	continue
   \(6\)	\(5 \ne 0\)	continue
   \(7\)	\(4 \ne 0\)	continue
   Loop ends. Return true: 53 is prime.

   Check \(n = 91\): \(\lfloor\sqrt{91}\rfloor = 9\).

   \(d\)	\(91 \bmod d\)	action
   \(2\)	\(1 \ne 0\)	continue
   \(3\)	\(1 \ne 0\)	continue
   \(4\)	\(3 \ne 0\)	continue
   \(5\)	\(1 \ne 0\)	continue
   \(6\)	\(1 \ne 0\)	continue
   \(7\)	\(0\)	return false
   91 is not prime (\(91 = 7 \cdot 13\)).

Exercise 5.12: Numerical algorithms (E12)

Consider the natural number \(n = 15\).

Questions

1. Apply the algorithm SieveOfEratosthenes for \(n = 15\). Show the execution step by step: indicate the value of \(\lfloor\sqrt{15}\rfloor\), and for each prime \(p\) found, list the values of \(j\) in the inner loop and the corresponding assignments \(prime[j] \leftarrow 0\).

2. List all the prime numbers \(\le 15\).

Solution

1. We have \(n = 15\) and \(\lfloor\sqrt{15}\rfloor = 3\). The array \(prime[1..15]\) is initialized to \(1\) and then \(prime[1] \leftarrow 0\). Each row of the table shows the state of the array after the assignment \(prime[j] \leftarrow 0\) (blue: entry just set to \(0\); red: current value of \(p\)).

   		\(prime[1..15]\)
   \(p\)	\(j\)	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	action
   \(-\)	\(-\)	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	initialization
   2	4	0	1	1	0	1	1	1	1	1	1	1	1	1	1	1	\(prime[4] \leftarrow 0\)
   	6	0	1	1	0	1	0	1	1	1	1	1	1	1	1	1	\(prime[6] \leftarrow 0\)
   	8	0	1	1	0	1	0	1	0	1	1	1	1	1	1	1	\(prime[8] \leftarrow 0\)
   	10	0	1	1	0	1	0	1	0	1	0	1	1	1	1	1	\(prime[10] \leftarrow 0\)
   	12	0	1	1	0	1	0	1	0	1	0	1	0	1	1	1	\(prime[12] \leftarrow 0\)
   	14	0	1	1	0	1	0	1	0	1	0	1	0	1	0	1	\(prime[14] \leftarrow 0\)
   	16																\(j = 16 > 15\): stop
   3	9	0	1	1	0	1	0	1	0	0	0	1	0	1	0	1	\(prime[9] \leftarrow 0\)
   	12	0	1	1	0	1	0	1	0	0	0	1	0	1	0	1	\(prime[12] \leftarrow 0\) (already \(0\))
   	15	0	1	1	0	1	0	1	0	0	0	1	0	1	0	0	\(prime[15] \leftarrow 0\)
   	18																\(j = 18 > 15\): stop
   Outer loop ends: \(p = 4 > \lfloor\sqrt{15}\rfloor = 3\).

2. The prime numbers \(\le 15\) are \(2,\ 3,\ 5,\ 7,\ 11,\ 13\).

Exercise 5.13: Numerical algorithms (E13)

Consider the natural number \(n = 30\).

Questions

1. Apply the algorithm SieveOfEratosthenes for \(n = 30\). Show the execution step by step: indicate the value of \(\lfloor\sqrt{30}\rfloor\), and for each prime \(p\) found, list the values of \(j\) in the inner loop and the corresponding assignments \(prime[j] \leftarrow 0\).

2. List all the prime numbers \(\le 30\).

Solution

1. We have \(n = 30\) and \(\lfloor\sqrt{30}\rfloor = 5\). The array \(prime[1..30]\) is initialized to \(1\) and then \(prime[1] \leftarrow 0\).

   • Iteration \(p = 2\): \(prime[2] = 1\), so \(2\) is prime. Inner loop from \(j = p^2 = 4\) with step \(2\):

     \(j\)	assignment	note
     \(4\)	\(prime[4] \leftarrow 0\)
     \(6\)	\(prime[6] \leftarrow 0\)
     \(8\)	\(prime[8] \leftarrow 0\)
     \(10\)	\(prime[10] \leftarrow 0\)
     \(12\)	\(prime[12] \leftarrow 0\)
     \(14\)	\(prime[14] \leftarrow 0\)
     \(16\)	\(prime[16] \leftarrow 0\)
     \(18\)	\(prime[18] \leftarrow 0\)
     \(20\)	\(prime[20] \leftarrow 0\)
     \(22\)	\(prime[22] \leftarrow 0\)
     \(24\)	\(prime[24] \leftarrow 0\)
     \(26\)	\(prime[26] \leftarrow 0\)
     \(28\)	\(prime[28] \leftarrow 0\)
     \(30\)	\(prime[30] \leftarrow 0\)
     \(32\)		\(j = 32 > 30\): stop

   • Iteration \(p = 3\): \(prime[3] = 1\), so \(3\) is prime. Inner loop from \(j = p^2 = 9\) with step \(3\):

     \(j\)	assignment	note
     \(9\)	\(prime[9] \leftarrow 0\)
     \(12\)	\(prime[12] \leftarrow 0\)	already \(0\)
     \(15\)	\(prime[15] \leftarrow 0\)
     \(18\)	\(prime[18] \leftarrow 0\)	already \(0\)
     \(21\)	\(prime[21] \leftarrow 0\)
     \(24\)	\(prime[24] \leftarrow 0\)	already \(0\)
     \(27\)	\(prime[27] \leftarrow 0\)
     \(30\)	\(prime[30] \leftarrow 0\)	already \(0\)
     \(33\)		\(j = 33 > 30\): stop

   • Iteration \(p = 4\): \(prime[4] = 0\), so \(4\) is not prime: skip.

   • Iteration \(p = 5\): \(prime[5] = 1\), so \(5\) is prime. Inner loop from \(j = p^2 = 25\) with step \(5\):

     \(j\)	assignment	note
     \(25\)	\(prime[25] \leftarrow 0\)
     \(30\)	\(prime[30] \leftarrow 0\)	already \(0\)
     \(35\)		\(j = 35 > 30\): stop

   • Outer loop ends: \(p = 6 > \lfloor\sqrt{30}\rfloor = 5\).

   Final state of the array \(prime[1..30]\) (the entries equal to \(1\) are in blue):

   \(i\)	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
   \(prime[i]\)	0	1	1	0	1	0	1	0	0	0	1	0	1	0	0
   \(i\)	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
   \(prime[i]\)	0	1	0	1	0	0	0	1	0	0	0	0	0	1	0

2. The prime numbers \(\le 30\) are \(2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29\).

Exercise 5.14: Numerical algorithms (E14)

Consider the following execution trace of the algorithm SieveOfEratosthenes for \(n = 12\), where some entries have been replaced by a question mark.

		\(prime[1..12]\)
\(p\)	\(j\)	1	2	3	4	5	6	7	8	9	10	11	12	action
\(-\)	\(-\)	0	1	1	1	1	1	1	1	1	1	1	1	initialization
2	4	0	1	1	?	1	1	1	1	1	1	1	1	\(prime[4] \leftarrow 0\)
	6	0	1	1	0	1	?	1	1	1	1	1	1	\(prime[6] \leftarrow 0\)
	8	0	1	1	0	1	0	1	?	1	1	1	1	\(prime[8] \leftarrow 0\)
	10	0	1	1	0	1	0	1	0	1	?	1	1	\(prime[10] \leftarrow 0\)
	12	0	1	1	0	1	0	1	0	1	0	1	?	\(prime[12] \leftarrow 0\)
	14													\(j = 14 > 12\): stop
3	9	0	1	1	0	1	0	1	0	?	0	1	0	\(prime[9] \leftarrow 0\)
	12	0	1	1	0	1	0	1	0	0	0	1	?	\(prime[12] \leftarrow 0\) (already \(0\))
	15													\(j = 15 > 12\): stop
Outer loop ends: \(p = 4 > \lfloor\sqrt{12}\rfloor = ?\).

Questions

1. Fill in all the entries marked with a question mark in the table.

2. What is the value of \(\lfloor\sqrt{12}\rfloor\)? Why can the outer loop stop when \(p = 4\)?

3. List all the prime numbers \(\le 12\).

Solution

1. Completed table:

   		\(prime[1..12]\)
   \(p\)	\(j\)	1	2	3	4	5	6	7	8	9	10	11	12	action
   \(-\)	\(-\)	0	1	1	1	1	1	1	1	1	1	1	1	initialization
   2	4	0	1	1	0	1	1	1	1	1	1	1	1	\(prime[4] \leftarrow 0\)
   	6	0	1	1	0	1	0	1	1	1	1	1	1	\(prime[6] \leftarrow 0\)
   	8	0	1	1	0	1	0	1	0	1	1	1	1	\(prime[8] \leftarrow 0\)
   	10	0	1	1	0	1	0	1	0	1	0	1	1	\(prime[10] \leftarrow 0\)
   	12	0	1	1	0	1	0	1	0	1	0	1	0	\(prime[12] \leftarrow 0\)
   	14													\(j = 14 > 12\): stop
   3	9	0	1	1	0	1	0	1	0	0	0	1	0	\(prime[9] \leftarrow 0\)
   	12	0	1	1	0	1	0	1	0	0	0	1	0	\(prime[12] \leftarrow 0\) (already \(0\))
   	15													\(j = 15 > 12\): stop
   Outer loop ends: \(p = 4 > \lfloor\sqrt{12}\rfloor = 3\).

   Every question mark is the entry \(prime[j]\) of the row with index \(j\): it is \(0\) after the assignment \(prime[j] \leftarrow 0\) (in the row \(p = 3\), \(j = 12\), the entry was already \(0\)).

2. \(\lfloor\sqrt{12}\rfloor = 3\). The outer loop runs for \(p = 2, 3\) and stops when \(p = 4 > 3\). Every composite number \(m \le 12\) has a prime divisor not larger than \(\lfloor\sqrt{12}\rfloor = 3\) (chapter «Numerical algorithms», section «Sieve of Eratosthenes»), so all the composite numbers have already been marked: \(4, 6, 8, 10, 12\) by \(p = 2\) and \(9\) by \(p = 3\).

3. The prime numbers \(\le 12\) are \(2,\ 3,\ 5,\ 7,\ 11\).

Exercise 5.15: Numerical algorithms (E15)

Consider the algorithm SieveOfEratosthenes applied to \(n = 25\).

Questions

1. Apply the algorithm SieveOfEratosthenes for \(n = 25\). Show the execution step by step, indicating the value of \(\lfloor\sqrt{25}\rfloor\), and for each prime \(p\) the values of \(j\) tested in the inner loop and the corresponding assignments \(prime[j] \leftarrow 0\).

2. For \(p = 5\): what is the first value of \(j\) processed by the inner loop? Why is \(p^2 = 25\) the starting point and not \(2p = 10\)?

3. List all the prime numbers \(\le 25\).

Solution

1. We have \(n = 25\) and \(\lfloor\sqrt{25}\rfloor = 5\). The array \(prime[1..25]\) is initialized to \(1\) and then \(prime[1] \leftarrow 0\).

   • Iteration \(p = 2\): \(prime[2] = 1\), so \(2\) is prime. Inner loop from \(j = p^2 = 4\) with step \(2\):

     \(j\)	assignment	note
     \(4\)	\(prime[4] \leftarrow 0\)
     \(6\)	\(prime[6] \leftarrow 0\)
     \(8\)	\(prime[8] \leftarrow 0\)
     \(10\)	\(prime[10] \leftarrow 0\)
     \(12\)	\(prime[12] \leftarrow 0\)
     \(14\)	\(prime[14] \leftarrow 0\)
     \(16\)	\(prime[16] \leftarrow 0\)
     \(18\)	\(prime[18] \leftarrow 0\)
     \(20\)	\(prime[20] \leftarrow 0\)
     \(22\)	\(prime[22] \leftarrow 0\)
     \(24\)	\(prime[24] \leftarrow 0\)
     \(26\)		\(j = 26 > 25\): stop

   • Iteration \(p = 3\): \(prime[3] = 1\), so \(3\) is prime. Inner loop from \(j = p^2 = 9\) with step \(3\):

     \(j\)	assignment	note
     \(9\)	\(prime[9] \leftarrow 0\)
     \(12\)	\(prime[12] \leftarrow 0\)	already \(0\)
     \(15\)	\(prime[15] \leftarrow 0\)
     \(18\)	\(prime[18] \leftarrow 0\)	already \(0\)
     \(21\)	\(prime[21] \leftarrow 0\)
     \(24\)	\(prime[24] \leftarrow 0\)	already \(0\)
     \(27\)		\(j = 27 > 25\): stop

   • Iteration \(p = 4\): \(prime[4] = 0\), so \(4\) is not prime: skip.

   • Iteration \(p = 5\): \(prime[5] = 1\), so \(5\) is prime. Inner loop from \(j = p^2 = 25\) with step \(5\):

     \(j\)	assignment	note
     \(25\)	\(prime[25] \leftarrow 0\)
     \(30\)		\(j = 30 > 25\): stop

   • Outer loop ends: \(p = 6 > \lfloor\sqrt{25}\rfloor = 5\).

   Final state of the array \(prime[1..25]\) (the entries equal to \(1\) are in blue):

   \(i\)	1	2	3	4	5	6	7	8	9	10	11	12	13
   \(prime[i]\)	0	1	1	0	1	0	1	0	0	0	1	0	1
   \(i\)	14	15	16	17	18	19	20	21	22	23	24	25
   \(prime[i]\)	0	0	0	1	0	1	0	0	0	1	0	0

2. For \(p = 5\), the inner loop starts at \(j = p^2 = 25\). All the smaller multiples of \(5\) larger than \(5\), namely \(10, 15, 20\), have already been set to \(0\): \(10 = 2 \cdot 5\) and \(20 = 2 \cdot 10\) when \(p = 2\), and \(15 = 3 \cdot 5\) when \(p = 3\). In general, every multiple \(m\) of \(p\) with \(p < m < p^2\) has a divisor \(d\) with \(2 \le d < p\), hence a prime divisor smaller than \(p\), which has already marked it.

3. The prime numbers \(\le 25\) are \(2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23\).

Exercise 5.16: Numerical algorithms (E16)

Consider the natural number \(n = 50\).

Questions

1. Apply the algorithm SieveOfEratosthenes for \(n = 50\). For each value of \(p\) of the outer loop, report the value of \(prime[p]\) and, when \(p\) is prime, all the values of \(j\) processed by the inner loop (the multiples of \(p\) from \(p^2\) to \(50\)), distinguishing the entries newly set to \(0\) from those already equal to \(0\).

2. List all the prime numbers \(\le 50\) and count them.

Solution

1. We have \(n = 50\) and \(\lfloor\sqrt{50}\rfloor = 7\). The array \(prime[1..50]\) is initialized to \(1\) and then \(prime[1] \leftarrow 0\).

   \(p\)	\(prime[p]\)	values of \(j\)	newly set to \(0\)	already \(0\)
   \(2\)	\(1\) (prime)	\(4, 6, \dots, 50\)	4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50	—
   \(3\)	\(1\) (prime)	\(9, 12, \dots, 48\)	9, 15, 21, 27, 33, 39, 45	12, 18, 24, 30, 36, 42, 48
   \(4\)	\(0\) (skip)	—	—	—
   \(5\)	\(1\) (prime)	\(25, 30, \dots, 50\)	25, 35	30, 40, 45, 50
   \(6\)	\(0\) (skip)	—	—	—
   \(7\)	\(1\) (prime)	\(49\)	49	—
   Outer loop ends: \(p = 8 > \lfloor\sqrt{50}\rfloor = 7\).

   Final state of the array \(prime[1..50]\) (the entries equal to \(1\) are in blue):

   \(i\)	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
   \(prime[i]\)	0	1	1	0	1	0	1	0	0	0	1	0	1	0	0	0	1
   \(i\)	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34
   \(prime[i]\)	0	1	0	0	0	1	0	0	0	0	0	1	0	1	0	0	0
   \(i\)	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50
   \(prime[i]\)	0	0	1	0	0	0	1	0	1	0	0	0	1	0	0	0

2. The prime numbers \(\le 50\) are

   \[ 2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47 \]

   There are \(15\) prime numbers \(\le 50\).

Exercise 5.17: Numerical algorithms (E17)

Consider the following pairs of natural numbers \((n,m)\):

1. \((1071,\ 462)\)

2. \((100,\ 75)\)

3. \((17,\ 5)\)

4. \((89,\ 55)\)

5. \((30,\ 84)\)

Questions

1. Apply the algorithm EuclideanAlgorithm to compute \(\gcd(n,m)\) for all the pairs. For each pair, show the execution step by step in a table, indicating at each step the values of \(n\), \(m\) and \(r=n\bmod m\), and give the number of iterations of the while loop.

2. Which pairs are coprime?

3. In pair 5 we have \(n<m\). What happens in the first iteration?

Solution

1. Executions of the Euclidean algorithm.

   1. Compute \(\gcd(1071,462)\):

      step	\(n\)	\(m\)	\(r = n \bmod m\)
      \(1\)	\(1071\)	\(462\)	\(1071 \bmod 462 = 147\)
      \(2\)	\(462\)	\(147\)	\(462 \bmod 147 = 21\)
      \(3\)	\(147\)	\(21\)	\(147 \bmod 21 = 0\)
      \(4\)	\(21\)	\(0\)	— (loop ends)

      Result: \(\gcd(1071, 462) = 21\), with \(3\) iterations of the while loop.

   2. Compute \(\gcd(100,75)\):

      step	\(n\)	\(m\)	\(r = n \bmod m\)
      \(1\)	\(100\)	\(75\)	\(100 \bmod 75 = 25\)
      \(2\)	\(75\)	\(25\)	\(75 \bmod 25 = 0\)
      \(3\)	\(25\)	\(0\)	— (loop ends)

      Result: \(\gcd(100, 75) = 25\), with \(2\) iterations of the while loop.

   3. Compute \(\gcd(17,5)\):

      step	\(n\)	\(m\)	\(r = n \bmod m\)
      \(1\)	\(17\)	\(5\)	\(17 \bmod 5 = 2\)
      \(2\)	\(5\)	\(2\)	\(5 \bmod 2 = 1\)
      \(3\)	\(2\)	\(1\)	\(2 \bmod 1 = 0\)
      \(4\)	\(1\)	\(0\)	— (loop ends)

      Result: \(\gcd(17, 5) = 1\), with \(3\) iterations of the while loop.

   4. Compute \(\gcd(89,55)\):

      step	\(n\)	\(m\)	\(r = n \bmod m\)
      \(1\)	\(89\)	\(55\)	\(89 \bmod 55 = 34\)
      \(2\)	\(55\)	\(34\)	\(55 \bmod 34 = 21\)
      \(3\)	\(34\)	\(21\)	\(34 \bmod 21 = 13\)
      \(4\)	\(21\)	\(13\)	\(21 \bmod 13 = 8\)
      \(5\)	\(13\)	\(8\)	\(13 \bmod 8 = 5\)
      \(6\)	\(8\)	\(5\)	\(8 \bmod 5 = 3\)
      \(7\)	\(5\)	\(3\)	\(5 \bmod 3 = 2\)
      \(8\)	\(3\)	\(2\)	\(3 \bmod 2 = 1\)
      \(9\)	\(2\)	\(1\)	\(2 \bmod 1 = 0\)
      \(10\)	\(1\)	\(0\)	— (loop ends)

      Result: \(\gcd(89, 55) = 1\), with \(9\) iterations of the while loop.

      The numbers \(89, 55, 34, 21, 13, 8, 5, 3, 2, 1\) are consecutive Fibonacci numbers: at every step the quotient is \(1\), and the remainders decrease as slowly as possible.

   5. Compute \(\gcd(30,84)\):

      step	\(n\)	\(m\)	\(r = n \bmod m\)
      \(1\)	\(30\)	\(84\)	\(30 \bmod 84 = 30\)
      \(2\)	\(84\)	\(30\)	\(84 \bmod 30 = 24\)
      \(3\)	\(30\)	\(24\)	\(30 \bmod 24 = 6\)
      \(4\)	\(24\)	\(6\)	\(24 \bmod 6 = 0\)
      \(5\)	\(6\)	\(0\)	— (loop ends)

      Result: \(\gcd(30, 84) = 6\), with \(4\) iterations of the while loop.

2. Two numbers are coprime if and only if their greatest common divisor is \(1\). Hence the coprime pairs are \((17,5)\) and \((89,55)\). The pairs \((1071,462)\), \((100,75)\) and \((30,84)\) are not coprime.

3. Since \(30<84\), we have \(30\bmod 84=30\), so the first iteration replaces \((30,84)\) with \((84,30)\): it simply swaps the two numbers. From the second iteration on, the execution is the same as for \((84,30)\), which needs \(3\) iterations. Therefore the assumption \(n\ge m\) is not needed for correctness: if \(n<m\), the algorithm only executes one extra iteration.

Exercise 5.18: Numerical algorithms (E18)

Consider the following naive algorithm for the greatest common divisor, which tries all the candidate divisors from \(\min\{n,m\}\) down to \(1\).

Algorithm: NaiveGCD

Input: Two natural numbers \(n, m \ge 1\)

Output: \(\gcd(n, m)\)

1function NaiveGCD(\(n\), \(m\))

2\(d := \min\{n,m\}\)

3while \(n \bmod d \ne 0\) or \(m \bmod d \ne 0\) do

4\(d \leftarrow d - 1\)

5end

6return \(d\)

7end

Questions

Questions 2–4 use the notions of loop invariant, number of steps and input size \(|I|\) (chapters «Input size», «Running time» and «Correctness»).

1. Apply NaiveGCD to \((48,18)\) and \((35,12)\). How many iterations of the while loop are executed? Compare with the number of iterations of the Euclidean algorithm on the same pairs.

2. Prove that NaiveGCD is correct, using a loop invariant.

3. Compute the number of steps \(S\) of NaiveGCD as a function of \(n\), \(m\) and \(\gcd(n,m)\), counting one step for each execution of a line. Which inputs give the worst case? Compare the two algorithms on \((1000,999)\).

4. Show that NaiveGCD is exponential in the input size \(|I|\).

Solution

1. For \((48,18)\): \(d\) starts from \(\min\{48,18\}=18\), and the candidates are checked in the order

   \[ 18,17,16,15,14,13,12,11,10,9,8,7,6. \]

   The first common divisor is \(d=6\) (\(48=8\cdot 6\), \(18=3\cdot 6\)). The while loop body is executed \(18-6=12\) times. The Euclidean algorithm needs only \(3\) iterations (\(48\bmod 18=12\), \(18\bmod 12=6\), \(12\bmod 6=0\)).

   For \((35,12)\): \(d\) goes from \(12\) down to \(1\), since \(35\) and \(12\) are coprime: \(12-1=11\) iterations. The Euclidean algorithm needs \(3\) iterations (\(35\bmod 12=11\), \(12\bmod 11=1\), \(11\bmod 1=0\)).

2. Loop invariant:

   Every time the condition at line 3 is evaluated, \(1\le \gcd(n,m)\le d\le\min\{n,m\}\), i.e., no number \(d'\) with \(d<d'\le\min\{n,m\}\) is a common divisor of \(n\) and \(m\).

   • Initialization. \(d=\min\{n,m\}\), and every common divisor is at most \(\min\{n,m\}\).

   • Maintenance. If the condition is true, \(d\) is not a common divisor; since no larger number up to \(\min\{n,m\}\) is a common divisor, \(\gcd(n,m)<d\), i.e., \(\gcd(n,m)\le d-1\). Line 4 sets \(d\leftarrow d-1\), and the invariant holds.

   • Termination. \(d\) decreases by \(1\) at every iteration and, by the invariant, it can never become smaller than \(\gcd(n,m)\ge 1\); when \(d=\gcd(n,m)\) the condition is false. Hence the loop terminates, and when it terminates \(d\) is a common divisor with \(d\ge\gcd(n,m)\), hence \(d=\gcd(n,m)\), which is returned.

3. Let \(k=\min\{n,m\}-\gcd(n,m)\) be the number of iterations. Lines 2 and 6 are executed once, line 3 \(k+1\) times, line 4 \(k\) times:

   \[ S=1+(k+1)+k+1=2k+3=2\big(\min\{n,m\}-\gcd(n,m)\big)+3. \]

   The worst case is when \(n\) and \(m\) are coprime: \(S=2\min\{n,m\}+1\). For \((1000,999)\) (consecutive numbers are always coprime) NaiveGCD executes \(999-1=998\) iterations, while the Euclidean algorithm executes only \(2\) (\(1000\bmod 999=1\), \(999\bmod 1=0\)).

4. Consider the pairs \((n,m)=(M,M-1)\), with \(M\ge 3\): they are coprime, so \(S=2(M-1)+1=2M-1=\Theta(M)\). The input consists of two natural numbers, so \(|I|=\Theta(\log_2 M)\) with \(M=\max\{n,m\}\), i.e., there exist \(c_1,c_2>0\) such that

   \[ 2^{\frac{1}{c_2}|I|}\le M\le 2^{\frac{1}{c_1}|I|}. \]

   Hence, on these inputs, \(S=2^{\Theta(|I|)}\), and the worst-case running time satisfies \(T(|I|)=2^{\Theta(|I|)}\) (it is also at most \(2M+1\) on every input).

   NaiveGCD is exponential in the input size, while the Euclidean algorithm executes \(O(\log_2 m)\) iterations (see the next exercise): for numbers with hundreds of digits, only the Euclidean algorithm can be used.

Exercise 5.19: Numerical algorithms (E19)

Consider the Euclidean algorithm.

Algorithm: EuclideanAlgorithm

Input: Two natural numbers \(n, m \ge 1\)

Output: \(\gcd(n, m)\)

1function EuclideanAlgorithm(\(n\), \(m\))

2while \(m \ne 0\) do

3\(r := n \bmod m\)

4\(n \leftarrow m\)

5\(m \leftarrow r\)

6end

7return \(n\)

8end

The Fibonacci numbers are \(F_1=F_2=1\) and \(F_{k}=F_{k-1}+F_{k-2}\) for \(k\ge 3\):

\[ 1,1,2,3,5,8,13,21,34,55,89,144,233,\dots \]

Questions

Question 4 uses the notions of running time and input size \(|I|\) (chapters «Input size» and «Running time»).

1. Count the number of iterations of the while loop for the pairs of consecutive Fibonacci numbers \((5,3)\), \((8,5)\), \((13,8)\), \((21,13)\), \((34,21)\), \((55,34)\), \((89,55)\), \((144,89)\), \((233,144)\).

2. Prove that, for every \(n\ge m\ge 1\),

   \[ n\bmod m<\frac n2. \]

3. Using point 2, prove that the number \(t\) of iterations of the while loop on input \((n_0,m_0)\) satisfies

   \[ t<2\log_2 m_0+2. \]

4. Assuming that each arithmetic operation is a step, determine the worst-case running time \(T(|I|)\) of the Euclidean algorithm. Is it polynomial?

Solution

1. For a pair \((F_{k+1},F_k)\) with \(k\ge 3\) we have \(F_k < F_{k+1} < 2F_k\), hence \(F_{k+1}\bmod F_k=F_{k+1}-F_k=F_{k-1}\): each iteration moves to the previous pair of consecutive Fibonacci numbers, until \((2,1)\to(1,0)\). The number of iterations is:

   \((n, m)\)	iterations \(t\)	\(2 \log_2 m + 2\)
   \((5, 3)\)	\(3\)	\(\approx 5.17\)
   \((8, 5)\)	\(4\)	\(\approx 6.64\)
   \((13, 8)\)	\(5\)	\(8\)
   \((21, 13)\)	\(6\)	\(\approx 9.40\)
   \((34, 21)\)	\(7\)	\(\approx 10.78\)
   \((55, 34)\)	\(8\)	\(\approx 12.17\)
   \((89, 55)\)	\(9\)	\(\approx 13.56\)
   \((144, 89)\)	\(10\)	\(\approx 14.95\)
   \((233, 144)\)	\(11\)	\(\approx 16.34\)

   For example, \((89,55)\to(55,34)\to(34,21)\to(21,13)\to(13,8)\to(8,5)\to(5,3)\to(3,2)\to(2,1)\to(1,0)\): \(9\) iterations. The number of iterations grows by \(1\) each time \(m\) is multiplied by about \(1.618\): it grows logarithmically in \(m\). (Consecutive Fibonacci numbers are, in fact, the worst case of the Euclidean algorithm.)

2. Let \(n\ge m\ge 1\). Two cases:

   • if \(m\le\frac n2\), then \(n\bmod m<m\le\frac n2\);

   • if \(m>\frac n2\), then \(m\le n<2m\), so the quotient of \(n\) divided by \(m\) is \(1\) and \(n\bmod m=n-m<n-\frac n2=\frac n2\).

3. Denote by \(m_s\) the value of \(m\) after \(s\) iterations (\(m_0\) is the input). In iteration \(s+1\) the pair \((n,m)\) becomes \((m,\ n\bmod m)\), so after iteration \(s+1\) the variable \(n\) is equal to \(m_s\) and \(m_{s+1}<m_s\). Therefore, if iteration \(s+2\) is executed,

   \[ m_{s+2}=m_s\bmod m_{s+1} \quad\text{with}\quad m_s> m_{s+1}\ge 1, \]

   and by point 2, \(m_{s+2}<\dfrac{m_s}{2}\): every two iterations the value of \(m\) is at least halved. By induction on \(k\),

   \[ m_{2k}<\frac{m_0}{2^k}\qquad\text{whenever iteration }2k\text{ is executed}, \ k\ge 1. \]

   If \(t\le 2\) the bound holds: \(t=1<2\le 2\log_2 m_0+2\), and \(t=2\) is possible only if \(m_0\ge 2\) (for \(m_0=1\) the first remainder is \(0\)), so \(2<2\log_2 m_0+2\). Let \(t\ge 3\) and let \(k=\lfloor (t-1)/2\rfloor\ge 1\). Since \(2k\le t-1\), iteration \(2k+1\) is executed, hence \(m_{2k}\ge 1\). Therefore

   \[ 1\le m_{2k}<\frac{m_0}{2^k} \quad\Longrightarrow\quad 2^k<m_0 \quad\Longrightarrow\quad k<\log_2 m_0 . \]

   Since \(k\ge\frac{t-2}{2}\), we get \(\frac{t-2}{2}<\log_2 m_0\), i.e.,

   \[ t<2\log_2 m_0+2. \]

   The values in the table of point 1 respect this bound.

4. Each iteration executes a constant number of steps (lines 2–5), so the number of steps satisfies \(S=O(t)=O(\log_2 m_0)\). The input consists of two natural numbers, hence \(|I|=\Theta(\log_2 M)\) with \(M=\max\{n_0,m_0\}\ge m_0\): there is \(c>0\) such that \(\log_2 m_0\le\log_2 M\le\frac1c|I|\) for all sufficiently large inputs. Therefore

   \[ T(|I|)=O(|I|). \]

   The Euclidean algorithm executes \(O(\log_2 m)\) iterations, and its worst-case running time is \(T(|I|)=O(|I|)\): it is polynomial (linear) in the input size.

   Remark: if the numbers are very large, an operation \(n\bmod m\) is not a single step, but it can be executed in a number of steps polynomial in \(|I|\); hence the algorithm remains polynomial.

Exercise 5.20: Numerical algorithms (E20)

Consider the following variant of the Euclidean algorithm, which uses only subtractions (this is the version originally described by Euclid).

Algorithm: SubtractiveGCD

Input: Two natural numbers \(n, m \ge 1\)

Output: \(\gcd(n, m)\)

1function SubtractiveGCD(\(n\), \(m\))

2while \(n \ne m\) do

3if \(n > m\) then

4\(n \leftarrow n - m\)

5end

6else

7\(m \leftarrow m - n\)

8end

9end

10return \(n\)

11end

Questions

Questions 3 and 4 use the notions of loop invariant, running time and input size \(|I|\) (chapters «Input size», «Running time» and «Correctness»).

1. Apply SubtractiveGCD to \((48,18)\), showing the values of \(n\) and \(m\) at every iteration. Compare with the Euclidean algorithm.

2. Prove that, for every \(n>m\ge 1\), \(\gcd(n,m)=\gcd(n-m,m)\).

3. Prove the correctness of SubtractiveGCD using a loop invariant.

4. How many iterations are executed on the input \((n,1)\)? Is SubtractiveGCD polynomial in the input size?

Solution

1. Execution on \((48,18)\):

   iteration	\(n\)	\(m\)	action
   \(1\)	\(48\)	\(18\)	\(n > m\): \(n \leftarrow 48 - 18 = 30\)
   \(2\)	\(30\)	\(18\)	\(n > m\): \(n \leftarrow 30 - 18 = 12\)
   \(3\)	\(12\)	\(18\)	\(n < m\): \(m \leftarrow 18 - 12 = 6\)
   \(4\)	\(12\)	\(6\)	\(n > m\): \(n \leftarrow 12 - 6 = 6\)
   —	\(6\)	\(6\)	\(n = m\): loop ends, return \(6\)

   Result: \(\gcd(48,18)=6\), with \(4\) iterations. The Euclidean algorithm computes \(48\bmod 18=12\) in a single step: subtracting \(18\) from \(48\) as long as possible (iterations 1–2) gives exactly the remainder \(12\). In general, a sequence of consecutive subtractions of the same number is one step of the Euclidean algorithm.

2. Let \(n>m\ge 1\). If \(d\) is a common divisor of \(n\) and \(m\), then \(n=k_1d\) and \(m=k_2d\), so \(n-m=(k_1-k_2)d\), with \(k_1-k_2\ge 1\) since \(n>m\): \(d\) is a common divisor of \(n-m\) and \(m\). Conversely, if \(n-m=k_1d\) and \(m=k_2d\), then \(n=(n-m)+m=(k_1+k_2)d\): \(d\) is a common divisor of \(n\) and \(m\). The two pairs have the same common divisors, hence the same greatest common divisor.

3. Denote by \(n_0,m_0\) the input values. Loop invariant:

   Every time the condition at line 2 is evaluated, \(n\ge 1\), \(m\ge 1\) and \(\gcd(n,m)=\gcd(n_0,m_0)\).

   • Initialization. \(n=n_0\ge 1\), \(m=m_0\ge 1\).

   • Maintenance. Assume the invariant and \(n\neq m\). If \(n>m\), line 4 replaces \(n\) with \(n-m\ge 1\) and, by point 2, \(\gcd(n-m,m)=\gcd(n,m)\). If \(n<m\), line 7 replaces \(m\) with \(m-n\ge 1\) and, by point 2 with the roles exchanged, \(\gcd(n,m-n)=\gcd(n,m)\). In both cases the invariant still holds.

   • Termination. The natural number \(n+m\) decreases by at least \(1\) at every iteration (we subtract a number \(\ge 1\)), and it is always at least \(2\). Hence the loop terminates, and it terminates when \(n=m\). Then

     \[ \gcd(n_0,m_0)=\gcd(n,n)=n, \]

     which is returned at line 10.

4. On \((n,1)\) with \(n\ge 2\), every iteration executes \(n\leftarrow n-1\), until \(n=1\): the loop executes \(n-1\) iterations (e.g., \((7,1)\) needs \(6\) iterations), while the Euclidean algorithm needs only \(1\) iteration (\(n\bmod 1=0\)). Each iteration executes a constant number of steps, so on the inputs \((M,1)\) we have \(S=\Theta(M)\). The input size is \(|I|=(\lfloor\log_2 M\rfloor+1)+1=\Theta(\log_2 M)\), hence \(M=2^{\Theta(|I|)}\) and

   \[ T(|I|)=2^{\Theta(|I|)}. \]

   SubtractiveGCD is correct, but it is exponential in the input size. Replacing the repeated subtractions with a single \(\bmod\) operation gives the Euclidean algorithm, which is polynomial.