Introduction to Algorithms

Week 2: Exercises

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

1. Counting in Binary

Write a program that reads an integer N (in decimal), and prints out all values from 0 to N in binary representation, with one number per line.

2. Zeroes versus Ones

Let's say that a number is

• light if its binary representation has more 0s than 1s

• heavy if its binary representation has more 1s than 0s

• balanced if its binary representation has the same number of 0s and 1s

Write a program that reads a decimal integer and reports whether it is light, heavy, or balanced.

3. Base 7 to Base 3

Write a program that reads a number written in base 7, and writes the number in base 3.

4. 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. Hint: extract N's digits in order from least significant to most significant; use those to build an integer K in which the least significant digit of N becomes the most significant digit of K.

5. A Large Prime

The largest known prime number is

2^82,589,933 − 1

How many digits does this number have, approximately?

6. Prime Optimization

The primalty testing program that we wrote in class tests all values from 2 up to √n to see if they are divisors of n.

a) It is unnecessary to test half of those values for divisibility. Why?

b) Make the program more efficient by changing it so that it does not test those unnecessary values.

7. Bertrand's postulate

Bertrand's postulate, first proven in 1852, states that for every integer n > 1 there is at least one prime p such that

n < p < 2n

Write a program that reads an integer n and prints

• some prime number p in the range n < p < 2n

• the count of prime numbers p in the range n < p < 2n

8. Nth Prime

Write a program that reads an integer n and prints the nth prime number.

9. 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.

10. Primes with Odd Digits

Write a program to determine how many 3-digit primes exist that have only odd digits.

11. Largest Prime Factor

Write a program that reads an integer n and prints its largest prime factor.

12. Most Repeated Factor

Write a program that reads an integer n and prints its prime factor that occurs the most times in n's prime factorization. (If more than one prime factor has a maximum number of occurrences, print the largest such factor.)

13. Fermat Numbers

As we discussed in the lecture, the Fermat numbers F_n are defined as

F_n = 2^{2^n}

Write a program that loops forever, printing out each Fermat number in term and also printing its prime factorization.