Programming Praxis

The totient of a number n is the count of the numbers less than n that are coprime to it; two numbers are coprime if they have no common factor other than 1. For instance, the totient of 30 is 8, since the numbers 1, 7, 11, 13, 17, 19, 23 and 29 are coprime to 30. The totient function was discovered by Leonhard Euler, and it pops up in all kinds of strange places in number theory; for instance, the totatives of 30 are the spokes on a 2,3,5 factorization wheel. We have seen the totient function in a previous exercise.

If you want to know the totient of a single number m, the best way to find it is to factor n and take the product of 1 less than each factor; for instance, 30 = 2 * 3 * 5, and subtracting 1 from each factor, then multiplying, gives the totient 1 * 2 * 4 = 8. But if you want to find the totients of all the numbers less than a given n, a better approach than factoring each of them is sieving. The idea is simple: Set up an array X from 0 to n, store i in each X_i, then run through the array starting from 0 and whenever X_i = i loop over the multiples of i, multiplying each by i − 1.

Your task is to write a function that computes all the totients less than n by sieving. 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

The British mathematician John Horton Conway, famous for inventing the cellular automata Game of Life, also invented an esoteric programming language called fractran in which commands are represented as fractions; for instance, the primegame program generates prime numbers:

17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1

Fractran has two rules:

1. Find the first fraction f in the list for which nf is an integer, output nf, and set n ← nf.

2. Repeat the first rule, but halt if no product nf is integral.

For example, given an initial 2, the sequence of values produced by the above program begins 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, …. (A007542).

The program is called primegame because the exponents of each number in the sequence that is a power of 2 form the list of prime numbers. For instance, the number 4 in the sequence is 2², for which the exponent 2 is the first prime. Fifty steps later the sequence takes the value 8 = 2³. After another 211 steps the sequence takes the value 32 = 2⁵. And so on, generating all of the prime numbers in sequence.

Your task is to write a fractran interpreter and use it to generate prime numbers using primegame. 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

A simple word game starts with a word and repeatedly removes a single letter from the word, forming a new word, until there are no letters left. The act of removing a letter is called chopping and the resulting list of words is a chopping chain. For instance:

planet → plane → plan → pan → an → a

Your task is to write a program that takes a word and returns a list of all possible chopping chains that can be formed from the word, given a suitable dictionary. 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 saw the streaming median problem in a recent exercise. Today we look at a slight variant on that problem, the sliding median, which slides a window of width k over an input stream, reporting the median of each successive window.

The streaming median required us to keep the entire input stream in memory. But for the sliding median, we keep only the most recent k items. We keep two data structures. A cyclical queue keeps the most recent input items, in the order in which they are input. An ordered map keeps the input items in sorted order. After reading the first k items, each time we read an item we output the current median, delete the oldest item in the cyclical queue from the ordered map, insert the new item into both the ordered map and the cyclical queue, and go on to the next item.

Your task is to write a program that implements the sliding median calculation. 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

In the previous exercise, we looked at a programming challenge that involved the digits of e. Solving that exercise and clicking on the indicated web site took the solver to this page:

Congratulations. You've made it to level 2. Go to www.Linux.org and enter Bobsyouruncle as the login and the answer to this equation as the password.

f(1)= 7182818284
f(2)= 8182845904
f(3)= 8747135266
f(4)= 7427466391
f(5)= __________

Don’t try to login; the account no longer exists.

Your task is to write a program to find the next number in the sequence. 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

Several years ago, a billboard with this text appeared in the tech centers of Silicon Valley and Route 128:

{ first 10-digit prime found in consecutive digits of e }.com

Your task is to write a program that finds the first 10-digit prime found in consecutive digits of e. 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 gave an algorithm for computing the digits of π in a previous exercise. Today, we look at two algorithms for computing the digits of e.

We begin with an algorithm due to Stanley Rabinowitz and Stan Wagon:

Algorithm e-spigot: compute the first n decimal digits of e:

1. Initialize: Let the first digit be 2 and initialize an array A of length n + 1 to (1, 1, 1, . . . , 1).

2. Repeat n − 1 times:

Multiply by 10: Multiply each entry of A by 10.

Take the fractional part: Starting from the right, reduce the ith entry of A modulo i + 1, carrying the quotient one place left.

Output the next digit: The final quotient is the next digit of e.

We give an example of the calculation for the first ten digits of e on the next page, where we compute the first ten digits of e as 2 7 1 8 2 8 1 8 2 6. As you can see, this algorithm suffers from the fact that the last digit may be wrong (it should be 8, not 6); in fact, as the paper suggests, there are circumstances where several of the last digits may be wrong. The algorithm also suffers from the fact that it is bounded, meaning that the number of digits must be specified in advance, and it needs space proportional to n².

A different algorithm comes from Jeremy Gibbons, and is both unbounded and requires only constant space; Gibbons gave the sequence for π, but Tom Moertel adapts it to e. When I was unable to work out the algorithm from Moertel’s description, I asked Remco Niemeijer, a regular contributor to Programming Praxis, for help, and he responded with this gorgeous hunk of Haskell code, which computes both π and e:

stream :: Integral a => (a, a) -> (a, a, a) -> [(a, a, a)] -> [a]
stream (lo, hi) z ~(x:xs) = if lbound == approx z hi
    then lbound : stream (lo, hi) (mul (10, -10*lbound, 1) z) (x:xs)
    else stream (lo, hi) (mul z x) xs
    where lbound = approx z lo
          approx (a,b,c) n = div (a*n + b) c
          mul (a,b,c) (d,e,f) = (a*d, a*e + b*f, c*f)

main :: IO ()
main = do print $ take 30 stream_pi
          print $ take 30 stream_e

Niemeijer explained that he had adapted the algorithm in Gibbons’ paper as follows:

– unit is a constant used in only one place. Remove the definition and just use the value directly.

– comp is basic 2×2 matrix multiplication. Rename to mul to make purpose clearer.

– extr as defined in the paper didn’t compile for me: it should be fromInteger (q * x) instead of fromInteger q * x. But there’s more to be gained: the only place extr is used is preceded by floor, so essentially we have floor (a / b), which is equal to div a b. Since it’s used to approximate the real value I named it approx.

– The code used 2×2 matrices expressed as a 4-tuple. However, the bottom-left element is always 0. Remove this element everywhere, leaving 3-tuples and making mul and approx simpler.

– For both π and e, the next and safe functions passed to stream are identical save for the bounds used, so pass in the bounds and integrate the functions in stream.

– The y used in stream is the lower bound. Rename accordingly.

– The cons passed to stream is always comp (or in my case mul). Remove the argument and use mul directly.

– prod is also the same for π and e, so remove the argument and inline the function.

– The definition of π from the paper calls stream with some starting arguments. Since e will be doing the same, make a function streamDigits to abstract this out.

– Since stream now takes far fewer parameters, there’s no longer a reason to name them all.

– According to the hulver site, each term in the π function is 2 + k/(2k + 1)x. For e, each term is 1 + (1/k)x (or rather, it defines e − 1 starting from k = 2, but if you start from k = 1 you add the term 1 + 1/1x, which gives you 1 + 1/1*(e-1), which of course is e). So both are of the form a + (n/d)x. The matrix used in lfts is (n, a*d, 0, d). I didn’t like having to do the multiplication myself, so I made streamDigits take a function that produces n, d and a for a given term to stay closer to the mathemetical definition. This function is used to produce the actual matrix.

– Add stream_e and stream_pi functions.

Your task is to write the two spigot functions for e 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 3

Today’s exercise is a fun math problem:

Consider a function f that takes a positive integer n and returns the number of 1s in the decimal representation of all the integers from 0 to n, inclusive. For example, f(13) = 6, for the numbers 1, 10, 11 (twice, for two 1s), 12 and 13. Notice that f(1) = 1. After 1, what is the next largest n for which f(n) = n?

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

In computer science, a map is a data type that associates a value with a key; all keys are unique, and the only comparison allowed is equality (are these two keys equal?). An ordered map extends the rule from equality to order (is one of these keys less than the other?), and if the ordered map also admits ranking the elements of the map (this item is first, that item is second, and so on), it is said to provide order statistics. A basic map is usually implemented with a hash table, and the two ordered variants are usually implemented with some kind of balanced tree (treap, avl, red-black). Maps are sometimes called dictionaries, though which type of map is intended is frequently unspecified, and the word dictionary can refer to either ordered or unordered maps.

Today’s exercise describes an abstract data type that provides an ordered map with order statistics. We provide the basic operations lookup, insert, and delete, and also an update function that either updates an existing value or inserts a new key/value pair in the map. For order statistics we provide the size, nth and rank operators. We also provide the higher-order functions map, fold and for-each, and conversions to and from lists. And finally, we provide an iterator to generate the key/value pairs in the map, one by one, in ascending order.

We use avl trees to implement our map; the code was given in two previous exercises. We also steal the generator code from a previous exercise. The new data type has recently been added to the Standard Prelude.

Your task is to implement an abstract data type of ordered maps with order statistics as 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

One of the on-going themes here at Programming Praxis involves the re-implementation of the text utilities from Unix V7. Today we look at the cat command:

NAME

cat – catenate and print

SYNOPSIS

cat [ –u ] file …

DESCRIPTION

Cat reads each file in sequence and writes it on the standard output. Thus

cat file

prints the file and

cat file1 file2 >file3

concatenates the first two files and places the result on the third.

If no file is given, or if the argument ‘-‘ is encountered, cat reads from the standard input. Output is buffered in 512-byte blocks unless the standard output is a terminal or the –u option is present.

SEE ALSO

pr(1), cp(1)

BUGS

Beware of ‘cat a b >a’ and ‘cat a b >b’, which destroy input files before reading them.

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