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 statisticP(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`that takes integers`

`Combination(n, k)`

`n`

and`k`

as input and returns the combination statisticC(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`(i.e., divisors that are less than`

`n`

`).`

`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`

whosek-th element is thek-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`if`

`true`

nis perfect and`otherwise. Recalling our first attempt at`

`false`

`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^{1}(2^{2} −1)

28 = 2^{2}(2^{3} −1)

496 = 2^{4}(2^{5} −1)

8128 = 2^{6}(2^{7} − 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

*− 1 is 15, which is certainly not prime. But 2*

^{m}^{2}−1 = 3, 2

^{3}− 1 = 7, 2

^{5 }− 1 = 31, and 2

^{7}− 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

*− 1 has a better than typical chance of being prime if*

^{m}*m*is prime. For this reasons, when trying to find the largest known prime number, mathematicians test numbers of the form 2

*− 1.*

^{m}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, wherepis a positive integer that is less than or equal to`n`

. Your code may take a few seconds to call`, 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).`

`ListMersennePrimes(61)`

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^{127} − 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}^{−1} · (2* ^{m} *− 1), and vice-versa: if 2

*− 1 is a Mersenne prime, then the number 2*

^{m}

^{m}^{−1}· (2

*− 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.*

^{m}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`that takes an integer`

`NextTwinPrimes()`

`n`

as input and returns the smallest pair of twin primes that are both larger than`n`

, using`IsPrime()`

as a subroutine.

## 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 statisticsP(1000, 2) andC(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 computeP(1000, 2).

Code Challenge:Improve your implementation of`so that it is efficient enough to quickly compute`

`Combination()`

C(1000, 998).

## 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!