## Linked List Exercises

### May 4, 2018

I like to do exercises on linked lists. In languages like C, linked lists provide good drill for students who are uncertain about structures and pointers; in any language, lists provide good drill on recursion. Today’s exercise is about linked lists; we’ve seen some of these before, but it’s good to review:

- Take a list of integers and rearrange it so all the even integers appear before all the odd integers, with both evens and odds appearing in the output in the same order as the input.
- Take a list of integers, split it into two lists each containing alternate elements from the input list, then join the two lists back together.
- Take a list of integers and rearrange it so alternate nodes are each greater than their two adjacent nodes; in other words, the integers are in alternating high-low order.

Your task is to perform the three linked list exercises 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.

## Gauss’s Criterion

### May 1, 2018

Yesterday was the 241st anniversary of the birth of Carl Gauss, who is perhaps the greatest mathematician who ever lived. In his honor, I picked a small task based on some mathematics that he discovered. Gauss’s Criterion states:

Let

pbe an odd prime andba positive integer not divisible byp. Then for each positive integer 2k− 1 <p, letrbe_{k}r≡ ( 2_{k}k− 1)b(modp) with 0 <r<_{k}p, and lettbe the number of evenrs. Then (_{k}b/p) = (-1)^{t}, where (b/p) is the Legendre symbol.

Your task is to write a program to compute Gauss’s criterion, and confirm that it is the appropriate power of the Legendre symbol. 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.

## Sum Square Digits Sequence

### April 27, 2018

Regular readers of this blog know of my affinity for recreational mathematics, and today’s exercise is an example of that.

We looked at happy numbers in a previous exercise. Recently, Fermat’s Library re-published a proof by Arthur Porges, first published in the American Mathematical Monthly in 1945, that the trajectory of the sequence of summing the squares of the digits of a number always ends in 1 (a Happy Number) or a set of eight digits 4, 16, 37, 58, 89, 145, 42, 20 (a Sad Number). So, we look at this task again:

You are given a positive integer. Split the number into its base-ten digits, square each digit, and sum the squares. Repeat until you reach 1 (a Happy Number) or enter a loop (a Sad Number). Return the sequence thus generated.

For instance, 19 is a happy number, with sequence 19, 82, 68, 100, 1, while 18 is a sad number, with sequence 18, 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …

Your task is to compute the sequence described above for a given *n*. 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.

Today’s exercise is a game that mathematicians play; it comes from /u/HarryPotter5777 on Reddit:

You are given a pair of integers. You make a sequence of steps in which one member of the pair is doubled and the other is incremented by one. Your goal is to find a sequence in which the two members of the pair are equal. For instance, the sequence (1 8), (2 9), (4 10), (5 20), (10 21), (11 42), (22 43), (44 44) ends with the two numbers equal, so (1 8) is a valid starting pair.

The question is whether or not it is always possible to find a sequence, regardless of the starting pair, which makes the two numbers equal. /u/shouldertarget gives a hand-waving explanation that the answer is “Yes” later in the Reddit thread mentioned above.

Your task is to write a program that, given a starting pair, derives a sequence that makes the two numbers equal. 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.

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