The World of Algorithms

Worked example: Add 3487 and 2756.

For this pair, the algorithm works. But it does not always work exactly as written. The textbook gives branches for a sum less than 10 and a sum more than 10; it leaves out a sum equal to 10. For instance, in 1234 + 5676, the units total is 4 + 6 = 10, and neither instruction applies.

Fix: Replace “more than 10” with “10 or more” (or “≥ 10”) wherever a carry is determined. Then 1234 + 5676 = 6910.

Not fully. The original instructions say to align the rightmost digits but do not explicitly explain what to do when one number has fewer digits.

For example, write 12,345 + 678 as:

 12345
+00678
------
 13023

We treat the absent left-hand digits of 678 as zeros. We must also correct the rule for column sums equal to 10. After both clarifications, 12,345 + 678 = 13,023.

Because digits have different place values. The rightmost positions are units, then tens, hundreds, and so on. Aligning from the right means we add quantities of the same place value: units with units, tens with tens, etc.

If we line up the leftmost digits of numbers with different lengths, a hundreds digit could be incorrectly added to a tens digit.

The largest single digit is 9, and the incoming carry is at most 1. Therefore the greatest possible total for a column is:

Since 19 contains only one ten, at most 1 needs to be carried to the next column. No column can generate a carry of 2 when adding only two numbers.

Case where it works: 1234 + 4321 = 5555. There is no final carry after the thousands column, so skipping Step 5 causes no problem.

Case where it fails: 8888 + 8888 = 17,776. The column operations leave a final carry of 1. Without Step 5, we would write just 7776, which is wrong.

Conclusion: The final step is necessary whenever the leftmost column produces a carry.

Start with an empty result list. For every number x in List 1, check if x occurs in List 2. If it does not, append x to the result.

only_in_1 = []
for each x in List1:
    if x is not in List2:
        append x to only_in_1
report only_in_1

Example: List 1 = [1, 3, 5, 7] and List 2 = [3, 4, 7]. Answer = [1, 5].

This is the same procedure with the roles reversed:

only_in_2 = []
for each y in List2:
    if y is not in List1:
        append y to only_in_2
report only_in_2

Example: For the same two lists, the answer is [4].

Efficiency tip: Because both lists are sorted, a two-pointer scan can compare the smallest remaining elements and move forward without repeatedly searching the entire other list. This is an optional improvement, not required to understand the original algorithm.

The LCM is the smallest positive number divisible by both inputs. One direct algorithm checks multiples in ascending order:

step = max(m, n)
candidate = step
while candidate is not divisible by min(m, n):
    candidate = candidate + step
report candidate

Example: For 12 and 18, test multiples of 18: 18 is not divisible by 12, but 36 is. The first positive integer divisible by both is 36, so LCM(12, 18) = 36.

Faster method: Once we know the GCD, use LCM(m, n) = (m ÷ GCD(m, n)) × n. Here, GCD(12, 18) = 6 and (12 ÷ 6) × 18 = 36.

We only need to check 1, 2, …, ⌊√n⌋ (all positive integers up to the square root of n).

If j divides n, then n ÷ j is also a divisor. At least one number in each factor pair is ≤ √n.

Example: For 36, check j = 1, 2, 3, 4, 5, 6 (just 6 checks instead of 36). The pairs found are (1,36), (2,18), (3,12), (4,9), and (6,6). When both elements of a pair are equal, include the divisor only once.

Not necessarily. The original algorithm assumes the divisor lists are in increasing order, then takes the rightmost common divisor as the largest. Pair-generation does not automatically preserve that order.

Counterexample: Pair-order divisors of 36 can be [1, 36, 2, 18, 3, 12, 4, 9, 6]. Comparing with divisors of 24 gives common values in this order: [1, 2, 3, 12, 4, 6]. The final value is 6, but the true GCD(36, 24) is 12.

Fix: Sort the divisors into ascending order before using the original algorithm, or track the maximum common divisor rather than taking the last one.

Each divisor list will now be in decreasing order, not increasing order. Therefore the common-divisor list will also be decreasing.

We must report its first (leftmost) element, rather than its last element.

Example: For 12 and 18, the common-divisor list in descending order is [6, 3, 2, 1]. The first element gives the correct GCD, 6; the last would incorrectly give 1.

We can stop at the first number that divides both inputs. Since we are searching from largest to smallest, the first common divisor encountered must be the GCD.

for k from min(m, n) down to 1:
    if k divides m and k divides n:
        report k
        stop

Example: For 12 and 18, test 12, 11, 10, 9, 8, 7, then 6. The first common divisor is 6, so the algorithm stops.

If d divides both m and n, then d also divides their difference m−n.

Conversely, if d divides both n and m−n, it must divide their sum n + (m−n) = m.

Thus the two number-pairs have exactly the same common divisors and consequently the same GCD.

Every odd number can be written as 2k + 1. Dividing it by 2 leaves remainder 1.

two remainder reductions suffice when the odd number is at least 3. For the odd number 1, starting with the larger input gives 2 mod 1 = 0 in one step.

Use larger number = smaller number × quotient + remainder, then repeat with the smaller number and the remainder:

The last nonzero remainder is 75, so GCD(375, 825) = 75.

Use larger number = smaller number × quotient + remainder, then repeat with the smaller number and the remainder:

The last nonzero remainder is 3,000, so GCD(51,000, 81,000) = 3,000.

Use larger number = smaller number × quotient + remainder, then repeat with the smaller number and the remainder:

The last nonzero remainder is 1, so GCD(1,789,287, 237,656) = 1.

Use larger number = smaller number × quotient + remainder, then repeat with the smaller number and the remainder:

The last nonzero remainder is 24, so GCD(2,587,392, 157,656) = 24.

By the division algorithm, we can write m = qn + r, where r = m mod n and 0 ≤ r < n.

1. Forward direction: If d divides m and n, then it divides m − qn = r. So d divides n and r.
2. Reverse direction: If d divides n and r, then it divides qn + r = m. So d divides m and n.

Therefore the common divisors of (m, n) and (n, m mod n) are identical. GCD(m, n) = GCD(n, m mod n).

A prime number has exactly two distinct positive divisors, 1 and itself. The number 1 is not prime.

prime(n):
    if n <= 1:
        return False
    D = divisors(n)
    if length(D) == 2:
        return True
    else:
        return False

Example: divisors(13) = [1, 13], so prime(13) is True. But divisors(12) = [1, 2, 3, 4, 6, 12], so prime(12) is False.

Optional speed improvement: Check possible divisors only from 2 up to ⌊√n⌋. If any divides n, the number is not prime; otherwise a number greater than 1 is prime.

First find all divisors, then keep only those for which prime(d) returns True.

primedivisors(n):
    result = []
    D = divisors(n)
    for each d in D:
        if prime(d):
            append d to result
    return result

Example: Divisors of 180 are [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]. The prime divisors are [2, 3, 5].

Note that 1 is excluded, because it is not prime.

Start with the smallest possible prime factor, 2. Divide by that factor repeatedly and record the number of times it divides. Then move to the next possible factor.

prime_factorisation(n):
    factors = []
    p = 2
    while p * p <= n:
        exponent = 0
        while n mod p == 0:
            n = n / p
            exponent = exponent + 1
        if exponent > 0:
            append (p, exponent) to factors
        p = p + 1
    if n > 1:
        append (n, 1) to factors
    return factors

Why this works: We repeatedly divide out the smallest remaining factor. If a number p greater than 2 is composite, its smaller factors would already have been removed; therefore a successful new factor is prime. If the leftover n > 1 after testing up to its square root, it is itself prime.

Store a list of (prime, exponent) pairs:

[(2, 2), (3, 2), (5, 1)]

This means that 2 is multiplied twice, 3 is multiplied twice, and 5 is multiplied once: 4 × 9 × 5 = 180.

Match the prime bases. For the GCD, choose the smaller exponent of each prime shared by both numbers. For the LCM, choose the larger exponent of each prime appearing in either factorisation (using exponent 0 if a prime is absent).

With the pair-list representation, compare the matching prime entries and select the exponent according to the operation.