Introduction to Algorithms
Week 3: Exercises

1. Powers and Logs

Is 2ⁿ⁺¹ = O(2ⁿ)?
Is 2²ⁿ = O(2ⁿ)?
Is log₂(n) = O(log₄(n))?

2. Growth Rates

Order these functions by increasing growth rate: N!, 2^N, N¹⁰, N^{log N}, 10^N, N².

3. Three

Consider this program:

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

b = True
while n > 1:
    if n % 3 == 0:
        n //= 3
    else:
        b = False
        break

print(b)

For which values of n will it print 'True'?
What is its best-case and worst-case big-O running time as a function of n?

4. Largest Prime Gap

A prime gap is the difference between two consecutive prime numbers. For example, 7 and 11 are consecutive primes, and the gap between them has size 4.

Write a program that reads an integer N ≥ 3 and prints the largest prime gap among primes that are less than N. The program should print the pair of consective primes along with the gap size.

5. Goldbach's Conjecture

Goldbach's conjecture says that

Every even integer greater than 2 is the sum of two primes.

The conjecture seems obvious, but after more than 350 years it remains unproven.

Write a program that reads an integer N and checks whether Goldbach's conjecture is true for all integers that are ≤ N.

6. Prime Density

Write a program that reads integers a and b and prints the density of primes in the range [a, b], i.e. the fraction of the integers a ≤ n ≤ b that are prime.

7. Prime Experiment

Observe the following facts:

2³ mod 3 = 8 mod 3 = 2
2⁴ mod 4 = 16 mod 4 = 0
2⁵ mod 5 = 32 mod 5 = 2
2⁶ mod 6 = 64 mod 4 = 4
2⁷ mod 7 = 128 mod 7 = 2

Consider the following hypothesis:

For all integers k ≥ 3, 2^k mod k = 2 if and only if k is prime.

Do you believe that this is true, or false? Write a Python program to investigate this question.

8. Smallest Multiple

Solve Project Euler's problem 5:

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Introduction to Algorithms Week 3: Exercises