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.

Advertisements

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 ≤ rn.

  1. Generate a seqneuce ns1s2 ≥ … ≥ si = 1 by choosing s1 ∈ {1, 2, …, n} and si+1 ∈ {1, 2, … si}, until reaching 1.
  2. Let r be the product of the prime si‘s.
  3. If rn, 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

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.

Pages: 1 2

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.

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 2n + 1 with k odd and 2n > 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