Introduction to Algorithms
Week 2 – Notes

Extracting digits in any base

To split an integer into digits in base b, we first notice that for any integer i,

i mod b is the last digit of i (in base b)
i div b is the number formed by all digits of i except the last (in base b)

These facts should be obvious in base 10; for example, 2765 mod 10 = 5, and 2765 div 10 = 276. But they work in other bases too. For example, consider 1022₃, which equals 35₁₀ since

1 · 3³ + 0 · 3² + 2 · 3¹ + 2 · 3⁰ = 35

Notice that 35 mod 3 = 2 (which is the last digit of 1022₃), and 35 div 3 = 11 = 102₃ (all digits except the last).

And so we can use an iterative process to extract all digits from a number:

35 mod 3 = 2
35 div 3 = 11
11 mod 3 = 2
11 div 3 = 3
3 mod 3 = 0
3 div 3 = 1
1 mod 3 = 1
1 div 3 = 0

We have extracted the digits 2, 2, 0, 1 in reverse order, so we have produced the number 1022₃.

We can implement this algorithm in Python:

n = int(input('Enter n: '))
b = int(input('Enter base: '))

s = ''
while n > 0:
    d = n % b
    s = str(d) + s   # prepend d to s
    n = n // b

print(s)

For example:

Enter n: 35
Enter base: 3
1022

Because the digits are generated in reverse order, we must prepend to the string at each step to end up with the digits in the correct order.

The program above will work correctly only for bases 10 and lower. If we try a base such as 16, it may fail:

Enter n: 255
Enter base: 16
1515

That is wrong, since 255₁₀ = FF₁₆. The problem is that the program cannot generate digits beyond 9. Let's extend it to generate the digits A = 10, B = 11, and so on:

n = int(input('Enter n: '))
b = int(input('Enter base: '))

s = ''
while n > 0:
    d = n % b
    if d < 10:
        p = str(d)
    else:
        p = chr(ord('a') + d - 10)
    s = p + s   # prepend p to s
    n = n // b

print(s)

Now it works even for base 16:

Enter n: 255
Enter base: 16
ff

Combining digits in any base

To combine a series of digits into a number, we first notice that we can append a digit d to an integer n in base b using this formula:

n' = b · n + d

In base 10, this should be pretty obvious. For example, if n = 198 and d = 5, then n' = 10 · 198 + 5 = 1985.

However, this will work in any base. For example, we have seen above that 35₁₀ = 1022₃. Supose that we'd like to append the digit 1 to this base-3 number. Then we can compute 35 · 3 + 1 = 106, which equals 10221₃.

So now suppose that we have the base-3 digits 1, 0, 2, 2, 1 and we'd like to combine them into an integer. We can use an iterative process:

0 · 3 + 1 = 1
1 · 3 + 0 = 3
3 · 3 + 2 = 11
11 · 3 + 2 = 35
35 · 3 + 1 = 106

Let's implement this algorithm in Python:

s = input('Enter digits: ')
b = int(input('Enter base: '))

n = 0
for c in s:
    n = n * b + int(c)

print(n)

It works:

Enter digits: 10221
Enter base: 3
106

However, this program will not handle bases larger than 10. An excellent exercise would be to extend it to handle such bases, just as we did in the program in the previous section.

converting between bases

To convert from base B to base C, you can perform these two steps in succession:

Combine the base B digits into an integer.
Extract digits in base C from the integer.

primality testing

As we know from mathematics, a prime number is an integer greater than 1 whose only factors are 1 and itself. For example, 2, 7, 47 and 101 are all prime. A integer greater than 1 that is not prime is said to be composite.

We would now like to write a program that tests whether a given number is prime. To do this, we will use a simple algorithm called trial division, which means dividing by each possible factor in turn. (By the way, there also exist more efficient algorithms for primality testing, though they are more complex.)

Here is a naive implementation of trial division:

n = int(input('Enter n: '))

prime = True

for i in range(2, n):  # loop from 2 .. (n - 1)
    if n % i == 0:
        prime = False
        break

if prime:
    print('n is prime')
else
    print('not prime')

This works fine, but is inefficient because it may need to test all integers from 2 up to (n – 1). When n is large, this can take a long time.

Actually for a given n we need test only the values up to √n, i.e. the square root of n. To see this, consider the following fact:

Fact. If n is composite, then it has a prime factor that is less than or equal to √n.

Proof. If n is composite, then n = ab for some integers 1 < a, b < n. Suppose that a > √n and b > √n. Then ab > √n ⋅ √n = n, which is a contradiction since ab = n. So either a ≤ √n or b ≤ √n.

It follows that if we have tested all the values from 2 through √n and none of them divide n, then n cannot be composite, so it is prime.

Here's a more efficent version of our program that stops at √n:

from math import sqrt

n = int(input('Enter n: '))

prime = True
for i in range(2, int(sqrt(n)) + 1):
    if n % i == 0:
        prime = False
        break

if prime:
    print('n is prime')
else:
    print('not prime')

prime factorization

The Fundamental Theorem of Arithmetic states that

Every positive integer has a unique prime factorization.

For example:

24 = 2 ⋅ 2 ⋅ 2 ⋅ 3 = 2³ ⋅ 3¹
30 = 2 ⋅ 3 ⋅ 5 = 2¹ ⋅ 3¹ ⋅ 5¹
64 = 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 = 2⁶
100 = 2 ⋅ 2 ⋅ 5 ⋅ 5 = 2² ⋅ 5²

You can see a proof of this theorem (which is actually not completely trivial) in an introductory number theory course.

We can use trial division to factor an integer. This is similar to our primality testing algorithm, which also used trial division. Given an integer N, we first try dividing N by 2, then by 3 and so on. If n is actually divisible by a number such as 3, then we must repeatedly attempt to divide by that same number. since the same prime factor may appear multiple times in the factorization.

Here is a first program for prime factorization:

n = int(input('Enter n: '))

f = 2
while n > 1:
    if n % f == 0:
        print('factor: ', f)
        n = n // f
    else:
        f += 1

Here's the program in action:

$ py factor.py
Enter n: 60
factor:  2
factor:  2
factor:  3
factor:  5

Study the program to understand how it works. The program tries dividing by all possible values. Once n is 1, we have divided out all factors, so the factorization is complete.

Note that the program will attempt to divide by non-prime factors, such as when i = 4. But n will never be divisible by such values. That's because any non-prime factor i is itself the product of two (or more) smaller primes, and we have already divided those primes out of n, so n cannot possibly be divisible by i.

The program works, but is inefficient because it potentially tests all values from 1 to n. Let's modify it so that we only test for factors up to sqrt(n), just like in our second primality testing program above:

from math import sqrt

n = int(input('Enter n: '))

f = 2
s = ''
while f <= int(sqrt(n)):
    if n % f == 0:  # n is divisible by f
        s += f'{f} * '
        n = n // f
    else:
        f += 1

s += str(n)     # append the last factor
print(s)

This version of the program also prints out all the factors on a single line: