Sieve Of Euler

February 25, 2011

The ancient Sieve of Eratosthenes that computes the list of prime numbers is inefficient in the sense that some composite numbers are struck out more than once; for instance, 21 is struck out by both 3 and 7. The great Swiss mathematician Leonhard Euler invented a sieve that strikes out each composite number exactly once, at the cost of some additional bookkeeping. It works like this:

First, make a list of numbers from 2, as large as you wish; call the maximum number n.

Second, extract the first number from the list, make a new list in which each element of the original list, including the first, is multiplied by the extracted first number.

Third, “subtract” the new list from the original, keeping in an output list only those numbers in the original list that do not appear in the new list.

Fourth, output the first number from the list, which is prime, and repeat the second, third and fourth steps on the reduced list excluding its first element, continuing until the input list is exhausted.

For example, start with the list 2 3 4 5 … 30. Then the new list is 4 6 8 10 … 60. Subtracting gives the list 2 3 5 7 9 … 29. Now 2 is prime and the process repeats on the list 3 5 7 9 … 29. At the next step, the new list is 9 15 21 27 … 87, subtracting gives the list 3 5 7 11 13 … 29, now 2 and 3 are prime and the process repeats on the list 5 7 11 13 … 29. Likewise for the primes 5 and 7, and since 7 · 7 > 30, the process stops, with the remaining list 11 13 17 19 23 29, so the complete list of primes less than 30 is 2 3 5 7 11 13 17 19 23 29.

Just as in the Sieve of Eratosthenes, you can speed up the Sieve of Euler by considering only odd numbers, by stopping once the first item in the list is greater than the square root of n, and by computing the new list in the second step only as far as n.

Your task is to write a program that implements the Sieve of Euler, then compare its performance to the Sieve of Eratosthenes. 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

Sliding Window Minimum

February 22, 2011








Pages: 1 2

Two Factoring Games

February 18, 2011





Pages: 1 2

Today’s three programming exercises come from the Google Code Jam Qualification Round Africa 2010:


Reverse Words: Given a list of space separated words, reverse the order of the words. Each input string contains L letters and W words. An input string will only consist of letters and space characters. There will be exactly one space character between each pair of consecutive words. For instance, the reverse of “this is a test” is “test a is this”, the reverse of “foobar” is “foobar”, and the reverse of “all your base” is “base your all”.

T9 Spelling: The Latin alphabet contains 26 characters and telephones only have ten digits on the keypad. We would like to make it easier to write a message to your friend using a sequence of keypresses to indicate the desired characters. The letters are mapped onto the digits as 2=ABC, 3=DEF, 4=GHI, 5=JKL, 6=MNO, 7=PQRS, 8=TUV, 9=WXYZ. To insert the character B for instance, the program would press 22. In order to insert two characters in sequence from the same key, the user must pause before pressing the key a second time. The space character should be printed to indicate a pause. For example “2 2″ indicates AA whereas “22” indicates B. Each message will consist of only lowercase characters a-z and space characters. Pressing zero emits a space. For instance, the message “hi” is encoded as “44 444″, “yes” is encoded as “999337777”, “foo  bar” (note two spaces) is encoded as “333666 6660022 2777″, and “hello world” is encoded as “4433555 555666096667775553″.

Your task is to solve the three Code Jam exercises. 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

Sums Of Powers

February 11, 2011

We saw the calculation of the Bernoulli numbers in the previous exercise. In today’s exercise we will study the Bernoulli numbers in their original context in computing the sums of powers. For instance, S10(1000) = 110 + 210 + … + 100010 = 91409924241424243424241924242500, a result calculated by the Swiss mathematician Jakob Bernoulli in “less than half of a quarter of an hour” in the late seventeenth century.

Any discussion of Bernoulli numbers is complicated by the fact that there are several similar sequences that go by that name. The oldest is -1/2, 1/6, 0, -1/30, 0, 1/42, 0, -1/30, 0, 5/66, …; that’s the sequence we calculated previously. The modern version of the sequence prepends a 1, so it’s 1, -1/2, 1/6, 0, -1/30, 0, 1/42, 0, -1/30, 0, 5/66, …. And sometimes the -1/2 is given as +1/2, so the sequence is 1, 1/2, 1/6, 0, -1/30, 0, 1/42, 0, -1/30, 0, 5/66, …. Even worse, sometimes the Bernoulli numbers are numbered counting from zero, though mostly they are numbered counting from one, so you have to be careful when you talk about the Bernoulli numbers.

The particular sequence that we want to look at is the third sequence that starts with 1, 1/2, 1/6, 0, -1/30, …. In 1999, S. Akiyama and Y. Tanigawa found a simple way to compute that sequence in linear time using a dynamic program represented in a triangular matrix:

1/2 1/3 1/4 1/5
1/6 1/6 3/20
0 1/30

In the first row, A0,j is computed as 1 / (j+1). In subsequent rows, Ai,j is computed as (j+1) × (Ai−1,j − Ai−1,j+1). The Bernoulli number Bn is located in the first column at An,0.

Given Bernoulli numbers, sums of powers can be computed by Bernoulli’s formula, where \left( \begin{array}{c} n \\ k \end{array} \right) = \frac{n!}{(n-k)!k!} is the binomial coefficient:

S_m(n) = \frac{1}{m+1} \sum_{k=1}^n \left( \begin{array}{c} m+1 \\ k \end{array} \right) B_k n^{m+1-k}

Your task is to write functions that return a list of Bernoulli numbers up to a requested limit and that compute the sum of powers Sm(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

The First Computer Program

February 8, 2011










Pages: 1 2

Excel Columns

February 4, 2011

The columns in an Excel spreadsheet are “numbered” A through IV, where A corresponds to 1, Z corresponds to 26, AA corresponds to 27, and IV corresponds to 256.

Your task is to write functions that translate back and forth between the two representations. 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

Cuckoo Hashing

February 1, 2011






Pages: 1 2


Get every new post delivered to your Inbox.

Join 669 other followers