Programming Praxis

We have seen several different sieves that enumerate the prime numbers not greater than n due to Eratosthenes, Atkin, Euler and Sundaram. In the 1980s, Paul Pritchard, an Australian mathematician, developed a family of sieve algorithms based on wheels, eventually finding an algorithm with O(n / log log n) time complexity and O(√n) space complexity. We examine a simple version of Pritchard’s wheel sieve in today’s exercise.

We begin with some definitions. M_k is the product of the first k primes; for instance, M₇= 2×3×5×7×11×13×17=510510. The totatives of M_k are those numbers from 1 to M_k that are coprime to M_k (that is, they have no factors in common). It is easy to determine the totatives of M_k by sieving: make a list of the integers from 1 to M_k, then for each of the primes that form the product M_k, strike out from the list the prime and all of its multiples; for instance, with M₃=2×3×5=30, sieving with 2 strikes out 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28 and 30, sieving with 3 strikes out 3, 6, 9, 12, 15, 18, 21, 24, 27, and 30, and sieving with 5 strikes out 5, 10, 15, 20, 25 and 30, leaving the totatives 1, 7, 11, 13, 17, 19, 23 and 29. A factoring wheel W_k contains the gaps between successive totatives, wrapping around at the end; for instance, W₃ consists of the gaps 6, 4, 2, 4, 2, 4, 6 and 2, corresponding to the gaps 7−1, 11−7, and so on, ending with 29−23 and 31−29 when the wheel wraps around at the end.

Pritchard’s wheel sieve uses wheels repeatedly to strike out composite numbers from the sieve. It operates in two phases: a setup phase and a processing loop.

The setup phase first computes a parameter k such that M_k < n / log_e n < M_k+1, then computes the wheel W_k and forms the set S from 1 to n by rolling the W_k wheel. The setup phase also computes the list of m primes not greater than the square root of n.

We compute the primes not greater than 100 as an example. We compute k=2, since 100/log(100) is 21.714724 which is between M₂=6 and M₃=30. The W₂ wheel is {4 2} and the set S is {1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97}; although there is only one set S, we will refer to this set as S₂, since it is the result of rolling the W₂ wheel. Finally, the square root of 100 is 10, and the m=4 primes less than 10 are {2 3 5 7}.

The processing loop iterates from k+1 to m. At each loop we will strike some of the elements of S, reducing S from S_k to S_k+1. Each time through the loop we first identify p, the smallest member of S that is greater than 1, and strike it from the set S. We also strike from S the successive multiples p(s'−s) less than n, where s'−s are the successive gaps in S. Finally, we increment k by 1 and repeat the loop as long as k≤m.

In our example computing the primes not greater than 100, i will take the values 3 and 4. The first time through the loop, p = 5, the gaps are 5−1=4, 7−5=2, 11−7=4, 13−11=2, 17−13=4 and 19−17=2, and the numbers that are stricken are 5, 5+4×5=25, 25+2×5=35, 35+4×5=55, 55+2×5=65, 65+4×5=85, and 85+2×5=95, leaving S₃ = {1 7 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89 91 97}. The second time through the loop, p = 7, the gaps are 7−1=6, 11−7=4, 13−11=6, 17−13=4, and 19−17=2, and the numbers that are stricken are 7, 7+6×7=49, 49+4×7=77, and 77+2×7=91, leaving S₄ = {1 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97}.

Once k>m and the final S has been computed, the list of primes is returned, consisting of the primes less than the square root of n followed by the elements of S excluding 1. Thus the primes not greater than 100 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97.

This version of Pritchard’s sieve has time complexity and space complexity both equal to O(n), where the standard sieve of Eratosthenes has time complexity O(n log log n). The improvement comes from the fact that Pritchard’s sieve strikes each composite only once, whereas Eratosthenes’ sieve strikes each composite once for each of its distinct prime factors; for instance, Eratosthenes’ sieve strike 15 twice, one for the factor of 3 and once for the factor of 5. But despite the improvement in the asymptotic complexity, Eratosthenes’ sieve is fast because its inner loop consists only of addition, while Pritchard’s sieve is slower because its inner loop consists of a subtraction to compute the gap in the wheel, a multiplication to extend that gap by the current sieving prime, and an addition to add the gap to the previously-stricken element. Thus, in practice, Eratosthenes’ sieve is faster than Pritchard’s.

Your task is to write a program to compute the primes not greater than n using Pritchard’s wheel sieve. 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 had fun drawing a fractal snowflake last week. In today’s exercise, we will write a full library for turtle graphics. Our goal is to provide the commands described in Brian Harvey’s book about Logo. The turtle is a robotic device that moves and draws on a graphical output device (paper, screen) with a coordinate system that has x running west (negative) to east (positive) and y running south (negative) to north (positive); the ordinal compass points are 0 north, 90 east, 180 south and 270 west. Most commands ignore the global coordinate system in favor of commands from the turtle’s point of view, so instead of saying “turn to 135 degrees” a typical command is “turn right 45 degrees,” so that a shape can be drawn without knowledge of its global coordinates. The turtle commands are:

clearscreen — initialize the graphics system and place the turtle in the center of the graphical output pointing north

penup — remove the pen from the drawing surface

pendown — place the pen on the drawing surface

forward n — move the turtle forward n steps, drawing a line if the pen is down

back n — move the turtle back n steps, drawing a line if the pen is down

left n — rotate the turtle n degrees left from its current heading

right n — rotate the turtle n degrees right from its current heading

setpos x y — move the turtle from its current position to the indicated coordinates, drawing a line if the pen is down

setheading n — rotate the turtle from its current heading to the indicated heading

pos — report the current position by its x and y coordinates

heading — report the current heading in degrees

Your task is to write a turtle graphics library. 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 comes from our file of interview questions:

Given a list, return the first half of the list as one list and the second half of the list as a second list. For instance, given the input list {1 2 3 4}, output the two lists {1 2} and {3 4}. If the input list has an odd number of items, the middle item can go to either list, so that the input list {1 2 3 4 5} can result in the output lists {1 2} and {3 4 5} or the output lists {1 2 3} and {4 5}.

Your task is to write the function that splits a list in two halves. 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 tradition here at Programming Praxis of celebrating milestones by having a party, and parties require games. Today, for our three-hundredth exercise we will write a cheating version of the hangman from a previous exercise.

The idea is simple. Instead of choosing a single answer at the beginning of the game, choose a length, and make a list of all possible answers. Each time the player guesses a letter, delete as few words from the possible-answer list as possible consistent with the guesses the player has made; most of the time another body part will be added to the gibbet.

Your task is to write a referee for the game of cheating hangman. 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

It’s Christmas time, and that means winter, and that means snow (sometimes, but probably not this year), so today’s exercise is to draw Koch’s Snowflake. This famous fractal is built from an equilateral triangle, as shown upper left. At each step each side is modified by removing its center third and replacing it with two legs of another equilateral triangle. Thus, at upper right, each of the three legs has been replaced four line segments that form a new shape. Carrying on, the fractal becomes more and more detailed at the edges of the triangle; eventually, the perimeter of the triangle is infinite, though its area is 8/5 the area of the original triangle. Mathematically, the Koch Snowflake can be encoded as a Lindenmayer system with initial string F++F++F, rewriting rule F → F-F++F-F, and angle 60 degrees (in the Lindenmayer notation, F means move forward, + is a right turn and - is a left turn).

Your task is to write a program to draw the Koch Snowflake. 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 today’s exercise we implement the classic Unix V7 game hangman for guessing words. The player is given a series of blanks, one per letter of a word to be guessed. At each turn the player guesses a letter; if it is in the word, all occurrences of the letter are filled in the appropriate blank, but if the guess is wrong, another body part — traditionally, the head, torso, two arms and two legs, for a total of six — is added to the gibbet. The player wins by guessing all the letters of the word before the hangman adds all the pieces of his body.

Your task is to implement the interactive game of hangman. 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 an election, the winner is required to have the majority of the votes. For instance, with the set of votes {A A A C C B B C C C B C C}, the winner is C with 7 of 13 votes. Some elections have no winner; with the set of votes {A B C A B C A}, A gets a plurality of the votes but not a majority, so there is no winner. You can think of voting as a political election, or as redundant hardware in a critical system where a failure of one component must not lead to failure of the overall system.

Your task is to write a function that determines the winner of a vote, or indicates that no candidate reached a majority. 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

When I was a kid, telephones had rotary dials, not push buttons, and exchanges had names; my grandmother was in the Underhill 8 exchange. If you were calling someone in the same exchange as you were, you only had to dial the last four digits of the number. Long distance calling generally involved a human operator.

Modern American telephone numbers have ten digits, segmented as a three-digit area code, a three-digit exchange code, and a four-digit number. Within an area code, you need only dial (the verb hasn’t changed, even though telephones no longer have a dial) the seven-digit exchange code and number; otherwise, you must dial the complete ten-digit number, often with a prefix.

Our exercise today asks you to validate a telephone number, as if written on an input form. Telephone numbers can be written as ten digits, or with dashes, spaces, or dots between the three segments, or with the area code parenthesized; both the area code and any white space between segments are optional. Thus, all of the following are valid telephone numbers: 1234567890, 123-456-7890, 123.456.7890, (123)456-7890, (123) 456-7890 (note the white space following the area code), and 456-7890. The following are not valid telephone numbers: 123-45-6789, 123:4567890, and 123/456-7890.

Your task is to write a phone number validator that follows the rules given above; your function should either return a valid telephone number or an indication that the input is invalid. Be sure to write a proper test suite. 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

At McDonalds’ Restaurants, the Chicken McNugget meals are available in sizes of 6 McNuggets, 9 McNuggets, or 20 McNuggets. A number is a McNugget number if it can be the sum of the number of McNuggets purchased in an order (before eating any of them). Henri Picciotto devised the math of McNugget numbers in the 1980s while dining with his son at McDonald’s, working the problem out on a napkin.

Your task is to determine all numbers that are not McNugget numbers. 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 1653 Blaise Pascal published his treatise Traité du triangle arithmétique describing his triangle computing the binomial coefficients, which are used in the study of probability; Pascal gets credit for the name even though both the coefficients and their arrangement in a triangle were known before him.

To compute the triangle, start with a row containing only 1. Then each succeeding row is built by adding the two numbers triangularly above the current number, assuming a temporary 0 at each end of the prior row.

Your task is to write a program to neatly display Pascal’s Triangle. 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