## Random Number Test

### July 7, 2017

We’ve built several random number generators: [1], [2], [3], [4], [5], [6], [7], [8], [9] (I didn’t realize it was so many until I went back and looked). In today’s exercise we look at a way to test them. There are several well-known random-number testers, including Donald Knuth’s spectral test and George Marsaglia’s diehard test, but our test will be much simpler. Specifically, we test two things:

1) The numbers generated have an equal number of 0-bits and 1-bits.

2) The maximum run of consecutive 1-bits is consistent with probability theory.

Your task is to write a simple random number tester. 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 Chains

### July 4, 2017

We studied word chains in a previous exercise; for instance, you can convert HEAD to TAIL by the word chain HEAD, HEAL, TEAL, TELL, TALL, TAIL in which each word differs from its predecessor by a single letter. Today’s exercise is similar, but asks you to find the chain from one prime number to another, with all intermediate numbers also prime, by changing one digit at a time; for instance, the chain 71549, 71569, 71069, 11069, 10069, 10067 converts 71549 to 10067.

Your task is to write a program to find prime chains. 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.

## Maximum Product Of Three, Revisited

### June 30, 2017

Today’s exercise is simply stated:

Write a program that finds the maximum product of three numbers in a given array of integers.

We studied that problem in a previous exercise, where unfortunately we got it wrong. Here is the suggested solution from that exercise:

(define (max-prod-three xs) (let ((len (length xs)) (xs (sort < xs))) (cond ((< len 3) (error 'max-prod-three "insufficient input")) ((= len 3) (apply * xs)) ((positive? (car xs)) (apply * (take 3 (reverse xs)))) ((negative? (last xs)) (apply * (take 3 (reverse xs)))) ((and (negative? (car xs)) (positive? (cadr xs))) (apply * (take 3 (reverse xs)))) ((and (negative? (cadr xs)) (negative? (caddr (reverse xs)))) (* (car xs) (cadr xs) (last xs))) ((and (negative? (cadr xs)) (positive? (caddr (reverse xs)))) (max (apply * (take 3 (reverse xs))) (* (car xs) (cadr xs) (last xs)))) (else (error 'max-prod-three "missed case")))))

Your task is to write a correct program that finds the maximum product of three numbers in a given array of integers; you might start by figuring out what is wrong with the previous program. 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.

## What Is S?

### June 27, 2017

We have something different today. Given this code:

int s = 0; for (int i=0; i<x; i++) for (int j=i+1; j<y; j++) for (int k=j+1; k<z; k++) s++;

What is *s*? What is a closed-form formula for computing *s*?

Your task is to compute *s*. 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.

## Leading Digits Of Powers Of 2

### June 23, 2017

John D. Cook, a programmer who writes about mathematics (he would probably describe himself as a mathematician who writes about programming) recently wrote about the distribution of the leading digits of the powers of 2, observing that they follow Benford’s Law, which we studied in a previous exercise.

Your task is to write a program that demonstrates that the distribution of the leading digits of the powers of 2 follows Benford’s Law. 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.

## Mangarevan Counting

### June 20, 2017

Six hundred years ago, the people of the French Polynesian island of Mangareva developed a mixed-radix counting system that combined binary and decimal elements to count from 1 to 799. They had no zero. The digits 1 through 9 had their normal decimal value. Digits K, P, T and V had values 10, 20, 40 and 80, respectively, so they increased in a binary progression. A number *N* was represented as *N* = *n*V + T + P + K + *m*, where *n* and *m* were digits; note that T, P and K did not have modifiers. Thus, 73 is represented as TPK3, 219 is represented as 2VTK9, and 799 is represented as 9VTPK9 in Mangarevan. You might enjoy this article in *Nature* and this article in the *Proceedings of the National Academy of Sciences*. Arithmetic is interesting: 1VPK9 + 1 = 1VT, and 3VPK3 + 2VTK9 = 6VK2.

Your task is to write programs that translate to and from Mangarevan counting 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.

## A Scheme Idiom

### June 16, 2017

While I was reading some Scheme code recently, I discovered a delightful little Scheme idiom that could simplify some coding tasks. It looks like this:

> (define (make-accum n) (case-lambda (() n) ((m) (set! n (+ n m)) n))) > (define a (make-accum 20)) > a #<procedure> > (a) 20 > (a 10) 30 > (a) 30

Variable *a* is a accumulator; `define`

it to set its initial value, fetch its current value by calling it as a function, and increment it by calling it with a value. This works because function `make-accum`

returns a function, defined by `case-lambda`

, with a semantics that varies based on its arity: with no arguments, the function returns the value stored in the closure, and with a single argument, it increments the value stored in the closure and returns the new value. The actual value is stored inside the function closure so it is only available through the defined interface, making it “safer” in some sense. And the concept works for other data types than accumulators, as the solution page will show.

Your task is to describe a useful idiom in your favorite programming language. 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.

## Climb To A Prime

### June 13, 2017

The British mathematician John Horton Conway, famous for inventing the Game of Life cellular automaton, made this conjecture:

Select a number, then compute its prime factors, with multiplicity; for instance, 90 = 2 × 3

^{2}× 5. Then “bring down” the exponent and write the resulting digits, forming a new number; for instance, the exponent of 2 in the above factorization is brought down, forming the number 2325. Repeat the process with the new number, and again, and so on; for instance, starting from 90, the chain is 90, 2325, 35231, 72719, where the chain terminates. I conjecture that the process will eventually terminate with a prime number.

At his YouTube channel, Numberphile revealed that the conjecture is false. The number 13532385396179 = 13 × 53^{2} × 3853 × 96179, so at each step it replaces itself, resulting in an infinite loop that will never reach a prime, thus disproving the conjecture. The discoverer of that number, James Davis, is entitled to a $1000 prize from Conway.

Your task is to write a program that calculates the climb to a prime for a given input number. 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.

## Generating Large Random Primes

### June 9, 2017

We studied Pocklington’s Criterion, which lets us quickly find large random primes, in a previous exercise. That algorithm generates a *certified* prime — a number that is proven to be prime — rather than a *probable* prime according to some pseudoprimality test.

Even though it’s not hard to generate a certified large prime, most cryptographic applications accept probable primes, primarily because it is much faster to generate a probable prime than a certified prime. Wikipedia explains the algorithm:

For the large primes used in cryptography, it is usual to use a modified form of sieving: a randomly chosen range of odd numbers of the desired size is sieved against a number of relatively small primes (typically all primes less than 65,000). The remaining candidate primes are tested in random order with a standard probabilistic primality test such as the Baillie-PSW primality test or the Miller-Rabin primality test for probable primes.

Your task is to write a program that implements the Wikipedia algorithm for generating large random probable primes. 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.

## Matrix Rotation

### June 6, 2017

We have a two-part exercise today, based on a Microsoft interview question.

First, write a program to rotate an *m* × *n* matrix 90° to the right, as shown below; your solution should touch each matrix element only once:

a b c d e f m j g d a A = g h i rot(A) = n k h e b j k l o l i f c m n o

Second, write a program to rotate a square matrix with *n* rows and columns *in-place*. where the source and target matrices are the same matrix and there is no intermediate matrix (be sure your solution works for both even and odd *n*):

a b c d e u p k f a f g h i j v q l g b B = k l m n o rot(B) = w r m h c p q r s t x s n i d u v w x y y t o j e

Your task is to write the two programs that rotate matrices. 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.