Previous Table of Contents Next


Problems: Creating Expressions

Now here are some sequences. Show expressions that generate them. Do not use procedures, and make the expressions as concise as possible.

31.  An infinite sequence consisting of randomly selected characters.
Solution: |?&cset. In this expression, &cset produces a cset of all 256 characters. The random-selection operation converts this cset to a string and selects a one-character substring at random. Repeated alternation causes the operation to repeat indefinitely.
32.  An infinite sequence consisting of the squares of the positive integers: 1, 4, 9, 16, ….
Solution: The general approach to the problem of generating a sequence of values based on the sequence of positive integers is to generate the positive integers and then apply a function to the results to get the desired sequence. One model for this is
    i := 0 & |(i +:= 1) & f(i)

where f(i) produces the desired value (which need not be an integer, of course). This also can be written as
    (i := 0, |(i +:= 1), f(i))

For the squares, this becomes
    (i := 0, |(i +:= 1), i ^ 2)
33.  An infinite sequence consisting of the Fibonacci numbers: 1, 2, 3, 5, 8, 13, 21, 34, ….
Solution: The Fibonacci numbers are defined by the recurrence relation
    f (i )  = 1            i = 1, 2
    f (i )  = f (i – 1) + f (i – 2)    i > 2

It is easy to formulate a recursive procedure based on this recurrence relation, but because procedures are not allowed in solutions to these exercises, a recursive approach cannot be used. An iterative procedure suggests a method:
    procedure fibseq()


       suspend (i | j) := 1


       repeat {
          i :=: j
          suspend j +:= i
          }


    end

It takes a little cleverness to get from this procedure to a procedure-free expression:
    ((i | j) := 1) | |((i :=: j) & (j +:= i))

There are more parentheses here than are necessary to make the grouping clear. The expression (i | j) := 1 initializes the two variables and also produces the first two values in the Fibonacci sequence. The remainder of the expression mimics the iterative procedure, using repeated alternation and conjunction in place of repeat and the two expressions in the procedure.
34.  An infinite sequence consisting of the factorials of the positive integers: 1, 2, 6, 24, 120, 720, ….
Solution: (i := 1) & |(i *:= seq. The repeated alternation can be moved inside the parentheses because all that is necessary is for the variable to be generated repeatedly, yielding (i := 1) & (|i *:= seq()).
35.  An infinite sequence consisting of the “triangular numbers,” which have the form i(i + 1)/2, yielding: 1, 3, 6, 10, 15, 21, ….
Solution: The triangular numbers are an instance of the polygonal numbers, the two-dimensional part of the more general figurate numbers (Beiler, 1966). As the name suggests, these numbers have geometrical interpretations. The first four triangular numbers are given by the number of nodes in the following figures:


The sequence for the triangular numbers can be produced simply by using the formula i(i + 1)/2, incrementing i at each step as in previous expressions. There is an easier approach, however, and one that’s recommended for unknown sequences: Take the first difference of successive terms and see if it suggests something. In the case here, the first difference yields 2, 3, 4, 5, 6, …. In other words, if t(i) is the ith triangular number, then
    t(i) = t(i – 1) + i

From this, a sequence to generate the triangular numbers is just
    (i := 1) | (i +:= seq(2))
36.  An infinite sequence consisting of the prime numbers: 2, 3, 5, 7, 11, 13, ….
Solution: Although there is no known method for computing primes efficiently in sequence, a brute-force method is simple: Just generate all the integers and filter out those that are not prime. The trivial observation that 2 is the only even prime leads to the following expression:
    2 | ((i := seq(3, 2)) & (not(i = (2 to i) * (2 to i))) & i)

The second operand of the conjunction, not(i = (2 to i) * (2 to i)), fails if i cannot be represented as the product of two integers. Otherwise, the result of the expression is just i, the third operand of the conjunction. It is, of course, not necessary to check all the way to i * i. A much better test is
    not(i = (k := (3 to sqrt(i) by 2)) * (i / k))
37.  An infinite sequence consisting of n copies of each positive integer n: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ….
Solution: This one is entirely different from the preceding exercises. This solution uses limitation in combination with repeated alternation:
    i := seq() & (|i \ i)
38.  A sequence consisting of strings representing the times in minutes in the 24-hour day, starting at midnight and ending at the minute before midnight: “00:00”, “00:01”, … “00:59”, “01:00”, … “23:59”.
Solution: The solution to this problem has two components: a generator for the hours and a generator for the minutes. 0 to 23 generates the hours, and 0 to 59 generates the minutes, but the values need to be padded with zeros:
    right(0 to 23, 2, “0”)
    right(0 to 59, 2, “0”)

All that remains is a concatenation with colons added as separators:
    right(0 to 23, 2, “0”) || “:” ||
       right(0 to 59, 2, “0”)


Previous Table of Contents Next