Chapter 0 Exercises: Fun with Integers

In what follows, “write and implement” means that we suggest that you write the function in pseudocode first, and then implement your function.

To get started, create a folder named hw0 under your go/src directory. Then create a text file named main.go inside this folder. This is the file that you should edit for the purposes of this assignment.

Combinations, permutations, and a short guide to debugging

The number of ways to order n objects is n!, since we have n choices for the object in position 1, n − 1 choices for the object in position 2, and so on. If we only want to order k of the objects, we still have n choices for the object in position 1, n − 1, choices for the object in position 2, but this stops when we have the object in position k, where we have n − k + 1 choices. This is called the permutation statistic P(n, k) and is equal to the product n·(n−1)···(n−k+1). Note that this expression can also be written using factorials as n!/((n − k)!).

Code Challenge: Write and implement a function Permutation(n, k) that takes integers n and k as input and returns the permutation statistic P(n, k).

If we don’t want to order the k objects, but instead are just selecting a subset of k from n objects, then we obtain the combination statistic, denoted C(n,k). There are k! different permutations corresponding to the same selection of objects, and so C(n, k) = P(n, k)/k!. In other words, C(n, k) = n!/((n − k)! · k!).

Code Challenge: Write and implement a function Combination(n, k) that takes integers n and k as input and returns the combination statistic C(n, k).

The following lesson allows you to check your solutions to these challenges. It can also be found using a direct link.

More practice with integer functions

Code Challenge: Write and implement a function Power() that takes two integers a and b as input and returns a raised to the power of b, a^b.

Code Challenge: Write and implement a function SumProperDivisors() . that takes an integer n as input and returns the sum of all “proper” divisors of n (i.e., divisors that are less than n).

Working with arrays and variadic functions

Code Challenge: Write and implement a function FibonacciArray() that takes an integer n as input and returns an array of length n+1 whose k-th element is the k-th Fibonacci number.

Code Challenge: Write and implement a function DividesAll() that takes as input an array of integers a and an integer d. This function should return true if d is a divisor of every value in the array, and false otherwise.

Code Challenge: Write and implement a function MaxIntegerArray() that takes as input an array of integers list and returns the maximum value in the array.

Code Challenge: Write and implement a function MaxIntegers() that takes an arbitrary collection of integers numbers as input and returns the maximum of all the integers.

Code Challenge: Write and implement a function SumIntegers() that takes an arbitrary collection of integers numbers as input and returns the sum of all the integers.

Code Challenge: Write and implement a function GCDArray() that takes an array of integers as input and generalizes the idea in TrivialGCD() to return the greatest common divisor of all of the integers in the array. You may want to use MinArray() as a subroutine.

The following lesson allows you to check your solutions to these challenges. It can also be found using a direct link.

Perfect numbers

Although the Greeks were interested in prime numbers, they were just as intrigued by a collection of numbers that you might not have heard of. A perfect number is an integer n that is equal to the sum of its “proper” divisors (meaning those smaller than n). For example, 6 is perfect because 1 + 2 + 3 = 6, and 28 is perfect because 1 + 2 + 4 + 7 + 14 = 28. Perfect numbers are far rarer than prime numbers; the Greeks only knew of these two as well as 496 and 8128, and only just over 50 perfect numbers have ever been discovered. Surely if we know of so few perfect numbers, they must be finite?

Code Challenge: Write and implement a function IsPerfect() that takes an integer n as input and returns true if n is perfect and false otherwise. Recalling our first attempt at IsPrime(), do you see any ways of making your function more efficient?

The first four perfect numbers, and in fact all known perfect numbers, have something in common: they’re all even! No one has ever found an odd perfect number, and yet no one has ever been able to prove that odd perfect numbers don’t exist. The plot thickens when we notice the following pattern.

6 = 2¹(2² −1)
28 = 2²(2³ −1)
496 = 2⁴(2⁵ −1)
8128 = 2⁶(2⁷ − 1)

Code Challenge: Write and implement a function NextPerfectNumber() that takes an integer n as input and uses IsPerfect() as a subroutine to find the smallest perfect number that is larger than n.

Then use your function to find the fifth perfect number, which was unknown to the Greeks. Can this number be represented as a product of the above form?

Your code may be take several minutes to find this number. If you are up for a challenge, try to look for ways to make your code faster.

The ancient Greeks knew that numbers of the form 2^m − 1 are more likely than others to be prime; such prime numbers are called Mersenne primes. When m = 4, 2^m − 1 is 15, which is certainly not prime. But 2²−1 = 3, 2³ − 1 = 7, 2⁵− 1 = 31, and 2⁷ − 1 = 127 are all prime.

The larger the value of n, the less the likelihood that n will be prime. So when we are looking for large prime numbers, chances are that choosing a random number to test for primality will be composite. It turns out that 2^m − 1 is composite if m is composite, and that 2^m − 1 has a better than typical chance of being prime if m is prime. For this reasons, when trying to find the largest known prime number, mathematicians test numbers of the form 2^m − 1.

Code Challenge: Write and implement a function ListMersennePrimes() that takes an integer n as input and returns an array of all primes of the form 2^p − 1, where p is a positive integer that is less than or equal to n. Your code may take a few seconds to call ListMersennePrimes(61), but in these few seconds you will find every Mersenne prime known until the mid-19th Century (including the largest prime known at that time).

We would ask you to look for larger candidate Mersenne primes, but to do so will lead to integer overflow, as the numbers being tested for primality grow so large that they exceed the storage for an integer variable.

In 1876, Edouard Lucas would demonstrate that 2¹²⁷ − 1 was prime after 19 years of manual computations! The rise of computers has made Lucas’s work seem particularly lonely — in 2018, a computer program discovered the primality of 2^82,589,933 − 1, a number so large that it has over 24 million digits.

The connection between two apparently very different types of numbers is perplexing and leads us to a conjecture. Could it be that every perfect number is formed from a Mersenne prime?

The Euclid-Euler Theorem confirms our intuition and states that every even perfect number must be of the form 2^m⁻¹ · (2^m − 1), and vice-versa: if 2^m − 1 is a Mersenne prime, then the number 2^m⁻¹ · (2^m − 1) must be perfect. As a result of the Euclid-Euler Theorem, we know that if there are infinitely many Mersenne primes, then there are infinitely many perfect numbers. However, no one knows if there are infinitely many Mersenne primes, and so the infinitude of the perfect numbers remains unknown.

The following lesson allows you to check your solutions to these challenges. It can also be found using a direct link.

Twin primes

Twin primes are pairs of prime numbers that are only 2 apart (such as 3 and 5, or 29 and 31). Much like perfect and amicable numbers, no one knows if there are infinitely many pairs of twin primes, although computations have indicated that they do go on forever, leading to the Twin Primes Conjecture that there are infinitely many such pairs.

Code Challenge: Write and implement a function NextTwinPrimes() that takes an integer n as input and returns the smallest pair of twin primes that are both larger than n, using IsPrime() as a subroutine.

The following lesson allows you to check your solutions to these challenges. It can also be found using a direct link.

Challenge exercises: faster combinations and permutations

The exercises in this section are optional if you are interested.

There is a good chance that your implementations of Permutation() and Combination() are not very efficient. For example, recall that the formula for the combination statistic C(n, k) is

C(n, k) = n!/((n − k)! · k!).

Try printing Combination(1000, 998) in func main() and run your code. There is a good chance that your code will keep running for a long time. And yet C(1000, 998) can be computed quickly by hand.

Exercise: Compute the statistics P(1000, 2) and C(1000, 998) by hand. (Hint: what trick can you use to avoid having to multiply many numbers together?)

Code Challenge: Improve your implementation of Permutation() so that it is efficient enough to quickly compute P(1000, 2).

Code Challenge: Improve your implementation of Combination() so that it is efficient enough to quickly compute C(1000, 998).

The following lesson allows you to check your solutions to these challenges. It can also be found using a direct link.

Up next

If you made it through these exercises, we are impressed! The hardest part of learning to program is behind you, and you are well on your way to becoming an expert.

This prologue has been all about numbers, but in the next chapter, we will start working with algorithms that can analyze text. We will then turn these algorithms toward finding hidden messages in the DNA of bacteria that serve to help direct the cell to accomplish its tasks. We hope that you will join us!

Continue to Chapter 1