Programming Praxis

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.

Pages: 1 2

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.

Pages: 1 2

We have a simple exercise for a Friday afternoon:

Write a program that determines if an input number n is 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.

Pages: 1 2

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: Integer n > 0.

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

1. Generate a seqneuce n ≥ s₁ ≥ s₂ ≥ … ≥ s_i = 1 by choosing s₁ ∈ {1, 2, …, n} and s_i+1 ∈ {1, 2, … s_i}, until reaching 1.
2. Let r be the product of the prime s_i‘s.
3. If r ≤ n, output r with probability r / n.
4. 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.

Pages: 1 2

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.

Pages: 1 2

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.

Pages: 1 2

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 = k 2ⁿ + 1 with k odd and 2ⁿ > k. Choose an integer a so that the Jacobi symbol (a, N) is -1. Then N is prime if and only if a^(N−1)/2 ≡ -1 (mod N).

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.

Pages: 1 2

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 (lambdas) 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 factorialfunction. 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 lambdas, 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.

Pages: 1 2