## Pandigital Numbers

### October 30, 2012

Today’s exercise comes to us from /r/learnprogramming:

A 3-digit number is added to another 3-digit number, and the result is a 4-digit number. If the ten digits involved are all different (the digits 0 through 9), then what is the smallest possible value for any of the three numbers?

Your tasks are to find the smallest number, as requested, and also to find all such triples of numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Pythagorean Triples

### October 26, 2012

Today’s exercise feels like a Project Euler problem:

A pythagorean triple consists of three positive integers

a,bandcwitha<b<csuch thata^{2}+b^{2}=c^{2}. For example, the three numbers 3, 4 and 5 form a pythagorean triple because 3^{2}+ 4^{2}= 9 + 16 = 25 = 5^{2}.The perimeter of a pythagorean triple is the sum of the three numbers that make up the pythagorean triple. For example, the perimeter of the 3, 4, 5 pythagorean triple is 3 + 4 + 5 = 12. There are 17 pythagorean triples with perimeter not exceeding 100. Ordered by ascending perimeter, they are: 3, 4, 5; 6, 8, 10; 5, 12, 13; 9, 12, 15; 8, 15, 17; 12, 16, 20; 7, 24, 25; 15, 20, 25; 10, 24, 26; 20, 21, 29; 18, 24, 30; 16, 30, 34; 21, 28, 35; 12, 35, 37; 15, 36, 39; 9, 40, 41; and 24, 32, 40.

How many pythagorean triples exist with perimeter not exceeding one million?

Your task is to write a program to compute the count of pythagorean triples with perimeter not exceeding one million. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Universal Hash Function

### October 23, 2012

Recently, when writing a program that shall remain anonymous, I needed a hash table with keys that could be either strings or integers. That may sound weird to you — it felt weird enough to me that I rearranged things so that all the keys had the same type. But the experience got me thinking about a universal hash function that could be used with keys of any type.

Your task is to write a hash function, suitable for your normal programming environment, that can take a value of any type and return a thirty-two bit integer suitable for use in a hash table. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Prime Partitions

### October 19, 2012

Today’s exercise is my penance for a wrong answer at /r/math.

A partition of a number is a way to add numbers to equal the target number; for instance, 1+1+2+3+5 is a partition of 11. We studied partitions in two previous exercises. If all the numbers used in the summation are prime, it is known as a prime partition; for instance, 2+2+2+2+3 = 2+3+3 = 2+2+2+5 = 3+3+5 = 2+2+7 = 11 are the 6 prime partitions for 11. The number of prime partitions of a number is a function known by the Greek letter kappa in number theory, so κ(11)=6. You can see the sequence of prime partitions at A000607.

The usual computation of the number of prime partitions is done in two parts. The first part is a function to compute the sum of the prime factors of a number; for instance, 42=2·3·7, so `sopf(42)=12`

. Note that `sopf(12)=5`

because the sum is over only the distinct factors of a number, so even though 12=2·2·3, only one 2 is included in the calculation of the sum. You can see the sequence of the sums of the distinct primes dividing *n* at A008472.

Given the function to compute the sum of the prime factors of a number, the number of prime partitions can be calculated using the following formula:

Your task is to write a function that computes the number of prime partitions of a number; use it to calculate κ(1000). When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Version Control

### October 16, 2012

We looked at the `make`

programmer’s tool in a previous exercise, and today we look at another programmer’s tool, a version control system. Version control systems allow programmers to keep multiple versions of text files in an economical manner, and there are many of them available: git, subversion, rcs, and the grand-daddy of all of them, sccs.

Our version control system provides three commands. `Put`

takes a single filename argument, stores the file in a *history* file, and removes the original file from the file system; the history file has the same name as the original file with an added suffix `.hist`

. `Get`

takes a filename argument plus an optional version argument and writes to the file system the requested version of the file, defaulting to the current version of the file if no version number is given; versions are numbered 0 for the current version, 1 for the previous version, 2 for the version before that, and so on. `Dir`

takes a single filename argument and shows a directory listing all available versions of a file. Unlike the bigger version control systems, there are no branches, only a single trunk of history.

The key to the version control system is the history file, which stores the most recent version of the file in its entirety, preceeded by a header line. Then follows a succession of *deltas*, one for each historical version, each preceeded by its own header line. Here’s a sample history file primes.ss.hist:

`@@@ phil Mon Oct 15 18:52:22 CDT 2012 Factorization by trial division`

(define (primes n)

(let ((bits (make-vector (+ n 1) #t)))

(let loop ((p 2) (ps (list)))

(cond ((< n p) (reverse ps))

((vector-ref bits p)

(do ((i p (+ i p))) ((< n i))

(vector-set! bits i #f))

(loop (+ p 1) (cons p ps)))

(else (loop (+ p 1) ps))))))

`(define (factors n)`

(let loop ((n n) (f 2) (fs (list)))

(cond ((< n (* f f))

(reverse (cons n fs)))

((zero? (modulo n f)

(loop (/ n f) f (cons f fs)))

(else (loop n (+ f 1) fs)))))

@@@ phil Mon Oct 15 18:50:32 CDT 2012 Fix typo s/vectr/vector

10,17d

@@@ phil Mon Oct 15 18:49:57 CDT 2012 Sieve of Eratosthenes

7c

(vectr-set! bits i #f))

.

The header line that preceeds each delta, including the current file version, starts with three asterisks. Then comes the name of the user that created the delta, and the date and time when it was created. The rest of the line is a comment written by the user when the delta is added to the history file.

Deltas are computed by the Unix `diff`

command with the -e option (we wrote our own version in a previous exercise) comparing the old and new versions and applied by the Unix `ed`

command by applying edit commands to the newest version to recreate older versions. We also use the Unix `wc`

command to count the lines in a delta.

Your task is to write a version control system as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Birthday Paradox

### October 12, 2012

In the study of probability, the Birthday Paradox states that in a group of 23 people, there is a 50% chance that two will have the same birthday; in a group of 57 people, the odds rise to 99%.

Your task is to simulate the birthday paradox over many trials and verify the odds. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Two Word Games

### October 9, 2012

It’s been a while since we played word games. We have two today:

1) Find all the words in a dictionary that contain exactly five vowels (a, e, i, o and u) in ascending order.

2) Find all the words in a dictionary of length at least six that contain letters in strictly ascending alphabetical order.

These games are easy to play using regular expressions, so you should solve them without regular expressions, using only simple string manipulations. If your system doesn’t provide a dictionary, you can find one at http://icon.shef.ac.uk/Moby/mwords.html.

Your task is to play the two games. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## AKS Primality Prover, Part 2

### October 5, 2012

In the previous exercise we wrote some auxiliary functions needed for the implementation of the AKS primality prover. Today we will implement the AKS algorithm:

AKS Primality Prover: Given an integer

n> 1, determine if it is prime or composite.

1. Ifn=afor integers^{b}a> 0 andb> 1, output COMPOSITE.

2. Find the smallestrsuch that ord_{r}(n) > (log_{2}n)^{2}.

3. If 1 < gcd(a,n) <nfor somea≤r, output COMPOSITE.

4. Ifn≤r, output PRIME.

5. For eachafrom 1 to floor √φ(r) · log_{2}n), if (x+a)^{n}&neq;x+^{n}a(modx− 1,^{r}n), output COMPOSITE.

6. Output PRIME.

Here ord_{r}(*n*) is the multiplicative order of *n* modulo *r*, both logarithms are to the base 2, φ(*r*) is Euler’s totient function, and the polynomial modular exponentiation is done as in the previous exercise.

Your task is to write a program to prove primality using the AKS algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## AKS Primality Prover, Part 1

### October 2, 2012

In the previous exercise, we looked at Pocklington’s algorithm for proving the primality of a number *n*; the algorithm depends on at least a partial factorization of *n*−1. In today’s exercise we look at an algorithm of Manindra Agrawal, Neeraj Kayal, and Nitin Saxena of the Indian Institute of Technology in Kanpur, which does not rely on *n* to be of any special form, is purely deterministic, of provable polynomial time, not conditional on the Riemann Hypothesis, and unfortunately very slow.

The entire mathematical community was astonished in 2002 when Agrawal, Kayal and Saxena published their algorithm. In the first place, Kayal and Saxena were undergraduate students at the time; Agrawal was their professor. And in the second place, their proof is simple, not relying on any complicated math; the general reaction among mathematicians was “How could we have missed that? What else have we missed?” The three won numerous awards, and their algorithm has been thoroughly studied and analyzed.

We will look at the AKS algorithm in the next exercise. Today, we write two functions that will be needed to implement the AKS algorithm.

The first function computes the *multiplicative order* of *n* modulo *r*, written as ord_{r}(*n*), which is the smallest number *k* such that *n*^{k} ≡ 1 (mod *r*). The algorithm is straight forward: starting from *k* = 2, increment *k* until you find the answer. The multiplicative order exists only when *n* and *r* are co-prime.

The second function computes the modular exponentiation of a polynomial; it’s not hard to write, but requires some explanation. To compute the modular exponentiation of a polynomial is simple; it uses the same square-and-multiply algorithm that is used for the modular exponentiation of an integer, which is part of our Standard Prelude and is described in Algorithm 3.C of the essay Programming with Prime Numbers. All we need is the modular multiplication of two polynomials, which we will explain by example.

Consider the problem of squaring polynomial *x*^{3} + 4*x*^{2} + 12*x* + 3 modulo (x^{5} − 1, 17). Polynomial multiplication is exactly the same as grade-school multiplication, except there are no carries, so the process looks like this:

` 1 4 12 3`

1 4 12 3

--- --- --- ---

3 12 36 9

12 48 144 36

4 16 48 12

1 4 12 3

--- --- --- --- --- --- ---

1 8 40 102 168 72 9

Thus, *x*^{3} + 4*x*^{2} + 12*x* + 3 squared is *x*^{6} + 8*x*^{5} + 40*x*^{4} + 102*x*^{3} + 168*x*^{2} + 72*x* + 9. To reduce the result modulo *x*^{5} − 1 we divide using the grade-school long-division algorithm and take the remainder, which gives *x* + 8 with a remainder of 40*x*^{4} + 102*x*^{3} + 168*x*^{2} + 73*x* + 17:

` 1 8`

+ --- --- --- --- --- --- ---

1 0 0 0 0 -1 | 1 8 40 102 168 72 9

1 0 0 0 0 -1

--- --- --- --- --- ---

8 40 102 168 73 9

8 0 0 0 0 -8

--- --- --- --- --- ---

40 102 168 73 17

We can confirm the calculation by multiplying and adding the remainder:

` 1 0 0 0 0 -1`

1 8

--- --- --- --- --- ---

8 0 0 0 0 -8

1 0 0 0 0 -1

--- --- --- --- --- --- ---

1 8 0 0 0 -1 -8

40 102 168 73 17

--- --- --- --- --- --- ---

1 8 40 102 168 72 9

Then we simply reduce each of the coefficients of the remainder modulo 17, giving the result 6*x*^{4} + 0*x*^{3} + 15*x*^{2} + 5*x* + 0. The whole computation can be organized as shown below. Note how the division and reduction modulo *x*^{5} − 1 is accomplished, eliminating the high-order coefficients and adding them back to the low-order coefficients; we are relying here on the simple form of the polynomial modulus, and would have to do more work if it was more complicated:

` 1 4 12 3 multiplicand`

1 4 12 3 multiplier

--- --- --- ---

3 12 36 9 3 * 1 4 12 3 * x^0

12 48 144 36 12 * 1 4 12 3 * x^1

4 16 48 12 4 * 1 4 12 3 * x^2

1 4 12 3 1 * 1 4 12 3 * x^3

--- --- --- --- --- --- ---

1 8 40 102 168 72 9 1 4 12 3 * 1 4 12 3

-1 -8 1 8 reduce modulo x^5 - 1

--- --- --- --- --- --- ---

40 102 168 73 17 reduce modulo 17

6 0 15 5 0 final result

Your task is to write functions that compute the multiplicative order of *n* modulo *r* and the modular exponentiation of polynomials. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution in the comments below.