Chapter 11: The World of Algorithms (Algorithms)

Example: 4786 + 3597. Following the steps exactly:

• Step 1: write 4786 above 3597, digits aligned from the right.
• Step 2: rightmost digits 6 + 7 = 13 (more than 10): write 3, carry = 1.
• Step 3: next column 8 + 9 + 1 = 18: write 8, carry = 1.
• Step 4 (repeat Step 3): 7 + 5 + 1 = 13: write 3, carry = 1; then 4 + 3 + 1 = 8: write 8, carry = 0.
• Step 5: carry is 0, so nothing more is written.

Result: 8383, which is correct (4786 + 3597 = 8383).

But try 4785 + 3125: in Step 2 the sum is 5 + 5 = 10. The steps say what to do if the sum is "less than 10" or "more than 10", but not if it is exactly 10! Followed precisely, the algorithm gets stuck. The fix is to change "more than 10" to "10 or more" in Steps 2 and 3 (as the text itself said before the algorithm). With that change, 4785 + 3125 = 7910 ✓.

For most numbers the steps give the correct sum (e.g. 4786 + 3597 = 8383), but a column sum of exactly 10 is not covered; "more than 10" must be changed to "10 or more".

Take 45678 + 396. After three columns, the 3-digit number has no more digits, but Step 3 says "add the two digits and the current value of carry". There is only one digit, so the steps do not say what to do, and Step 4 ("until there are no more digits on the left") is also unclear.

To handle it, we must add an instruction: "if one number has no digit in a column, treat that digit as 0" (or write extra zeros in front of the shorter number: 00396). Then:

$$45678+00396=46074$$

Not exactly: the steps assume both numbers have a digit in every column. Treating missing digits as 0 (writing 396 as 00396) fixes this; e.g. 45678 + 396 = 46074.

In the place-value system, the rightmost digit is units, the next is tens, then hundreds, and so on. Aligning from the right puts units under units, tens under tens, etc., so each column adds quantities of the same place value. If we aligned from the left, numbers of different lengths would add, for example, hundreds to tens: 473 + 69 would be added as 473 + 690, giving 1163 instead of the correct 542.

So that digits of the same place value (units with units, tens with tens, ...) are added together.

The largest digits are 9. In the first column the largest sum is 9 + 9 = 18, so the carry is at most 1. In any later column the largest sum is 9 + 9 + 1 = 19, which is still less than 20, so the carry is again at most 1. This continues for every column.

The largest possible column sum is 9 + 9 + 1 = 19 < 20, so the carry is never more than 1.

Step 5 writes the final carry. Without it, a carry out of the leftmost column is lost.

• Works: 23 + 45. The last column gives 2 + 4 = 6 with carry 0, so the result 68 is correct.
• Fails: 73 + 45. The last column gives 7 + 4 = 11: we write 1 and carry 1, but without Step 5 the carry is never written. The result would be 18 instead of 118.

Without Step 5 the answer is wrong whenever the leftmost column produces a carry (73 + 45 would give 18 instead of 118); it is correct only when the final carry is 0 (e.g. 23 + 45 = 68).

(i) Algorithm only-in-list-1:

1. Start with an empty list result.
2. For each number x in List 1:
   • if x does not appear in List 2, add x to the end of result.
3. Report result.

Because both lists are in increasing order, result is also in increasing order. A faster version uses the ordering: keep a position in each list, start both at the first element, and repeatedly compare the current elements a (List 1) and b (List 2): if a < b, a is not in List 2, so add it to result and move on in List 1; if a = b, move on in both lists; if a > b, move on in List 2. When List 2 runs out, add all remaining elements of List 1. This scans each list only once.

Example: List 1 = [1, 3, 5, 15, 25, 75, 125, 375], List 2 = [1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825] gives result = [125, 375].

(ii) Exchange the roles of the two lists: for each number y in List 2, add y to result if it does not appear in List 1. For the example above, result = [11, 33, 55, 165, 275, 825].

For each element of one list, add it to the answer if it is not in the other list (or use a single simultaneous scan of both sorted lists).

Method 1 (from the definition): the lcm is the smallest number that is a multiple of both m and n.

1. Let big be the larger of m and n, and small the smaller.
2. For each k = 1, 2, 3, ...:
   • if k × big is divisible by small, report k × big as lcm(m, n) and stop.

This always stops, at the latest when k = small (since big × small is a multiple of both). Example: lcm(6, 15): 15 (not divisible by 6), 30 (divisible), so lcm = 30.

Method 2 (using gcd): compute gcd(m, n) with Euclid's algorithm, then

$$\text{lcm}(m,n)=\frac{m\times n}{\gcd (m,n)}$$

Example: $\text{lcm}(375,825)=\frac{375\times 825}{75}=4125$.

Check the multiples of the larger number in order until one is divisible by the smaller number; or use lcm(m, n) = m × n ÷ gcd(m, n).

(i) In each pair (j, n/j), the smaller number j satisfies $j\times j\le n$, i.e. $j\le \sqrt{n}$. So we only need to examine j = 1, 2, ..., up to $\sqrt{n}$; each time j divides n we get two divisors, j and n/j. For n = 18 we check only 1, 2, 3, 4 (since $4^2=16\le 18<25$). For n = 10000 we check only 100 numbers instead of 10000.

(ii) Not without a change. Listed in pairs, the divisors are not in increasing order: for 18 we would get [1, 18, 2, 9, 3, 6]. Our algorithm reported the rightmost common divisor as the gcd, which relied on the list being in increasing order. With pairs, the rightmost common divisor need not be the largest one. We must either sort the lists first or look for the largest common divisor rather than the rightmost one.

(i) Only the numbers from 1 to √n. (ii) No: the lists are no longer in increasing order, so "take the rightmost common divisor" must be replaced by "take the largest common divisor".

The lists of divisors would come out in decreasing order (e.g. divisors(18) = [18, 9, 6, 3, 2, 1]), and so would the list of common divisors. The largest common divisor would then be the first (leftmost) element instead of the last. So the only change is in the last step: report the leftmost element of common-divisors as gcd(m, n).

Everything works the same, but the lists are in decreasing order, so the gcd is the leftmost element of the list of common divisors.

Scanning k = min(m, n), min(m, n) − 1, ..., 1, the first k that divides both m and n is the largest common divisor, i.e. the gcd. So we can stop as soon as we find it, without keeping most-recent-common-divisor or checking the remaining numbers. (In the worst case, when the gcd is 1, we still check all the numbers.)

Example: gcd(6, 12): start at 6, which divides both, so the answer is 6 after just one check.

The first common divisor found is the gcd, so we can stop immediately; this is usually faster.

Each step replaces gcd(m, n) by gcd(n, m mod n), until the remainder is 0.

(i) gcd(825, 375): $825=375\times 2+75$; $375=75\times 5+0$. So gcd = 75.

(ii) gcd(81000, 51000):

• $81000=51000\times 1+30000$
• $51000=30000\times 1+21000$
• $30000=21000\times 1+9000$
• $21000=9000\times 2+3000$
• $9000=3000\times 3+0$

So gcd = 3000.

(iii) gcd(1789287, 237656):

• $1789287=237656\times 7+125695$
• $237656=125695\times 1+111961$
• $125695=111961\times 1+13734$
• $111961=13734\times 8+2089$
• $13734=2089\times 6+1200$
• $2089=1200\times 1+889$
• $1200=889\times 1+311$
• $889=311\times 2+267$
• $311=267\times 1+44$
• $267=44\times 6+3$
• $44=3\times 14+2$
• $3=2\times 1+1$
• $2=1\times 2+0$

So gcd = 1: the two numbers have no common factor other than 1.

(iv) gcd(2587392, 157656):

• $2587392=157656\times 16+64896$
• $157656=64896\times 2+27864$
• $64896=27864\times 2+9168$
• $27864=9168\times 3+360$
• $9168=360\times 25+168$
• $360=168\times 2+24$
• $168=24\times 7+0$

So gcd = 24.

(i) 75 (ii) 3000 (iii) 1 (iv) 24

Divide m by n: $m=qn+r$, where q is the quotient and $r=m\mathrm{mod}n$ ($0\le r<n$).

• If d divides m and n, say $m=ad$ and $n=bd$, then $r=m-qn=ad-qbd=(a-qb)d$, so d divides r.
• If d divides n and r, say $n=bd$ and $r=cd$, then $m=qn+r=qbd+cd=(qb+c)d$, so d divides m.

So m, n and n, m mod n have exactly the same common divisors, and therefore the same gcd. This is why Āryabhaṭa's division step is correct.

Writing m = qn + r: a common divisor of m and n divides r = m − qn, and a common divisor of n and r divides m = qn + r.

Algorithm prime(n):

1. Compute the list divisors(n).
2. If the list has exactly two elements, report "n is prime".
3. Otherwise, report "n is not prime".

This handles n = 1 correctly too: divisors(1) = [1] has only one element, and 1 is not prime.

Faster version: n (> 1) is prime if no j with $2\le j\le \sqrt{n}$ divides n, because if n = ab with $1<a\le b$, then $a\le \sqrt{n}$. Example: to test 97 we only check 2, 3, 4, ..., 9; none divides 97, so 97 is prime.

prime(n): compute divisors(n); n is prime exactly when this list has exactly two elements (1 and n).

Algorithm primedivisors(n):

1. Compute the list divisors(n).
2. Start with an empty list prime-divisors.
3. For each d in divisors(n):
   • if prime(d) reports that d is prime, add d to the end of prime-divisors.
4. Report prime-divisors.

Example: divisors(180) = [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]; filtering the primes gives primedivisors(180) = [2, 3, 5].

Compute divisors(n), then keep only those divisors d for which prime(d) is true.

Algorithm factorise(n) (for n > 1):

1. Start with an empty list factors, and let p = 2.
2. While n > 1:
   • Count how many times p divides n: set e = 0; while p divides n, replace n by n ÷ p and increase e by 1.
   • If e > 0, add the pair (p, e) to the end of factors.
   • Increase p by 1.
3. Report factors.

Only primes are ever recorded, because by the time p is reached, all smaller primes have already been divided out (so a composite p, like 4 or 6, can no longer divide n).

(i) Represent the factorisation as a list of (prime, exponent) pairs in increasing order of the primes:

$$180=2^2\times 3^2\times 5^1⟶[(2,2),(3,2),(5,1)]$$

(ii) To compare two factorisations, go through the primes. For the gcd, take each prime that appears in both lists with the smaller of its two exponents; for the lcm, take every prime with the larger exponent. Example:

$$375=[(3,1),(5,3)],825=[(3,1),(5,2),(11,1)]$$

$$\gcd =3^1\times 5^2=75,\text{lcm}=3^1\times 5^3\times 11^1=4125$$

Divide out 2, 3, 4, ... in turn, recording each prime with its exponent; 180 → [(2, 2), (3, 2), (5, 1)]. For the gcd take common primes with the smaller exponents (for the lcm, the larger exponents).