## Recognizing Fibonacci Numbers

### April 20, 2018

We have a simple exercise for a Friday afternoon:

Write a program that determines if an input number

nis a Fibonacci number.

Your task is to write a program that determines if a number is a Fibonacci 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 Random Factored Numbers, Easily

### April 17, 2018

Sometimes it is convenient to have large random composite numbers with known factorization, particularly for testing prime number programs. Eric Bach gives a fast but complicated method. Adam Kalai gives a simpler method that’s not so fast:

Input: Integern> 0.

Output: A uniformly random number 1 ≤r≤n.

- Generate a seqneuce
n≥s_{1}≥s_{2}≥ … ≥s= 1 by choosing_{i}s_{1}∈ {1, 2, …,n} ands_{i+1}∈ {1, 2, …s}, until reaching 1._{i}- Let
rbe the product of theprimes‘s._{i}- If
r≤n, outputrwith probabilityr/n.- Otherwise, RESTART.

Your task is to implement Kalai’s method of generating random composite numbers with their factorization. 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.

## Third Biggest Number

### April 13, 2018

Today’s exercise is for all the beginning programming students who read this blog:

Write a program to read ten numbers input by the user and write the third largest of those ten numbers.

Your task is to write the program 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.

## Square Square

### April 10, 2018

We have today an opportunity for some code golf:

Write a program to find a four-digit positive integer that, when multiplied by itself, contains the original four-digit number in the last four digits of the product.

Your task is to write a program to find the desired number. If you wish, you can take it as a challenge to use the minumum number of symbols in your 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.

## Proth Primes And Sierpinski Numbers

### April 6, 2018

One of the neat things about mathematics is that, throughout history, many contributions to mathematics have been made by self-taught amateur mathematicians. About 150 years ago, a French farmer named François Proth (1852–1879), who lived near Verdun, proved this theorem:

Let

N=k2^{n}+ 1 withkodd and 2^{n}>k. Choose an integeraso that the Jacobi symbol (a,N) is -1. ThenNis prime if and only ifa^{(N−1)/2}≡ -1 (modN).

Primes of that form are known as Proth primes. Testing for a Proth prime is easy: choose *a* ∈ {3, 5, 7, 17} so that the Jacobi symbol is -1 and perform the modular multiplication. The game that recreational mathematicians play is to fix *k* and iterate *n* and see which *k* are fertile in producing primes; for instance, *k* = 12909 produces 81 primes before *n* = 53118.

Sierpinski numbers have the same form as Proth numbers, but “opposite” in the sense that there are *no* primes for a given *k*. The smallest known Sierpinski *k* is 78557; the only smaller *k* for which the Sierpinski character is not known are 10223, 21181, 22699, 24737, 55459 and 67607.

Your task is to write a program that identifies Proth primes and use it to find fertile *k* and Sierpinski *k*. 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.

## Continuation Passing Style

### April 3, 2018

Continuation passing style is a programming style in which the *continuation* of a function — what happens when the function returns — is made explicit. *Wikipedia* has a good explanation of continuation passing style. For example, the normal factorial function looks like this:

(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))

When it is written in continuation passing style, all of the continuations (`lambda`

s) are made explicit:

(define (factorial& n k) ((cps =) n 0 (lambda (b) (if b (k 1) ((cps -) n 1 (lambda (n-1) (factorial& n-1 (lambda (f) ((cps *) n f k)))))))))

Here *k* is the continuation of the `factorial`

function. The `=`

, `-`

and `*`

operators must be written in continuation passing style; function `cps`

, which we will see momentarily, converts an operator from normal style to continuation passing style. The three `lambda`

s, with arguments *b*, *n-1* and *f*, are intermediate steps in the expansion of the tree representation of the code. You can call the continuation-passing style version of the factorial function like this, where the continuation is the identity function:

> (factorial& 5 (lambda (x) x)) 120

Of course, the `factorial`

functions shown above are non-tail recursive, meaning that the stack grows with each recursive call. Here is a tail-recursive version of the factorial function:

(define (factorial n) (fact n 1))

(define (fact n a) (if (= n 0) a (fact (- n 1) (* n a))))

Parameter *a* of the auxiliary function is an accumulator, initialized to 1 when the auxiliary function is called. Here is the continuation passing style version of the tail-recursive function:

(define (factorial& n k) (fact& n 1 k))

(define (fact& n a k) ((cps =) n 0 (lambda (b) (if b (k a) ((cps -) n 1 (lambda (n-1) ((cps *) n a (lambda (n*a) (fact& n-1 n*a k)))))))))

> (factorial& 5 (lambda (x) x)) 120

Now `fact&`

is in tail position and the function consumes bounded stack space, which is what we want. The only thing left is to specify that mysterious `cps`

function:

(define (cps f) (lambda args (let ((f-args (but-last args)) (k (last args))) (k (apply f f-args)))))

The `cps`

function takes a function *f* and returns a new function that takes *args*, which includes the arguments to *f* plus the continuation, and calls the continuation *k* on the result of applying *f* to its non-continuation arguments.

Writing in continuation passing style obviously isn’t the most transparent thing in the world, and it’s not something most people do. But compilers work beautifully with continuation passing style, because everything, even the control flow, is explicit. Many functional languages are compiled by transforming the program to continuation passing style, and there is even a book, by Andrew Appel, about using continuations to compile programs.

There’s more to continuation passing style than we have discussed here. A huge advantage of continuation passing style is that, since the continuation is explicit, you can give a function more than one continuation, say *k-pass* and *k-fail*, and have the program choose which one to execute. Explicit continuations also make it easy to perform tail-call elimination in those cases where it is possible and to handle multiple-value returns. And compilers are able to aggressively optimize programs written in continuation passing style because everything the compiler needs to know about a function is available in the continuation.

Your task is to experiment with continuation passing style and to write at least one function, anything you like, in continuation passing style. 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.

## Snooker

### March 30, 2018

I lived in London during the 1980s, and like many people I was mesmerized by the snooker match between Dennis Taylor and Steve Davis. Davis was widely expected to win, and indeed he won the first game of the match, and carried his lead all the way to the end of the second day, when Taylor potted the final black ball and took the lead for the very first time over the two-day match, winning the world championship.

Snooker is scored by points for the balls of various colors: there are 15 red balls, each worth 1 point, plus one ball each of yellow, green, brown, blue, pink and black worth, respectively, 2, 3, 4, 5, 6 and 7 points. Players accumulate points in a break by potting balls one after another until they make a miss. As long as there is a red ball on the table, the player must pocket a red ball first; then, after making a red, the player can attempt to make a “colored” ball (other than red). If a color is potted, it is returned to the table (put on its spot) as long as there is a red on the table; once all the reds are potted, the colors must be potted in ascending point order, and are not respotted. A perfect game requires the player to pot 36 balls in order — 15 reds, each with a black, followed the colors in order — and earns 147 points. Perfect games are not common, but neither are they uncommon; in ranked match play, there are typically one or two perfect games per year.

Your task, which comes from an interview question, is to write a program that calculates the sequence of scores from a game of snooker; for a perfect game, the sequence is 1, 8, 9, 16, 17, 24, 25, 32, 33, 40, 41, 48, 49, 56, 57, 64, 65, 72, 73, 80, 81, 88, 89, 96, 97, 104, 105, 112, 113, 120, 122, 125, 129, 134, 140, 147 (A241263). 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.

## Elsie Four

### March 27, 2018

It’s been a while since we did any cryptography. Alan Kaminsky developed an algorithm that he claims is suitable for hand operation but is also quite secure. You can read about the cipher and Kaminsky’s cryptanalysis of it at the link.

Your task is to implement Kaminsky’s Elsie Four cipher. 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.

## Stable Sort

### March 23, 2018

A sorting algorithm is *stable* if items with equal keys appear in the output in the same order they appear in the input. In many cases the stability of a sorting algorithm doesn’t matter; in other cases it is critical. Some sorting algorithms, such as merge sort, are inherently stable (unless you muck up the implementation), which other sorting algorithms, such as quick sort, are inherently unstable. It is always possible to turn an unstable sort into a stable sort by adding an index to the data and using the index to break ties.

Your task is to write a program that converts an unstable sorting algorithm into a stable sorting 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.

## Television Time

### March 20, 2018

Today’s exercise is an interview question:

There is a room with a television and people come in and out of the room to watch it; the television is on only when there is at least one person in the room. For each person that enters the room, we record the start and end time, represented as a two-element array containing the starting time (inclusive) and ending time (exclusive), with times as integers (you can think of hours, or minutes, or any interval you like). We want to know how long the television is on. For instance, given the list of intervals (1 4), (6 8), (2 4), (7 9), the television is on at times 1, 2, 3 from the first interval, times 6 and 7 from the second interval, times 2 and 3 from the third interval, and times 7 and 8 from the first interval, a total of 6 times the television is on (at times 1, 2, 3, 6, 7 and 8).

Your task is to write a program that takes a list of intervals and returns the number of times at which the television is on. 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.