Introduction to Algorithms

Week 2: Exercises

These are optional exercises for practicing the concepts we learned this week.

1. Smallest Power

Write a program that reads an integer N and prints the smallest power of 2 that is ≥ N.

2. Largest Power

Write a program that reads an integer N ≥ 1 and prints the largest power of 2 that is ≤ N.

3. Digit Sum

Write a program that reads an integer and prints the sum of its digits.

4. Bases

Calculate by hand:

• What is 110100₂ in base 10? What is AB₁₆ in base 10?

• What is 95₁₀ in base 2? In base 16?

• In hexadecimal, what is the smallest and largest value that can be stored in a byte?

5. Hexadecimal

Write a program that reads an integer and prints it in hexadecimal (i.e. base 16).

6. Reverse the Digits

Write a program that reads an integer N and prints out N with its digits reversed. Do not use any strings (except for reading the input) or lists. You must reverse the digits using arithmetic operations only.

7. Fermat Primes

For any n ≥ 0, the Fermat number F_n =

F_n = + 1

The first few Fermat numbers are F₀ = 2, F₁ = 5, F₂ = 17, F₃ = 257, which are all prime.

Fermat conjectured that all Fermat numbers are prime. Use Python to investigate the truth of this claim.