Programming Praxis

It is sometimes possible, starting with a prime, to add a digit to the front of the number that forms a new prime. For instance, starting from prime 7, adding 1 forms prime 17, adding 3 forms prime 317, adding 6 forms prime 6317, adding 2 forms prime 26317, and so on.

Your task is to write a program to find the largest prime that can be formed in this way. 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 is our 400th, and our tradition on these anniversaries is to play a game. Today we choose Petals Around The Rose. Here’s a sample game:

Let's play 'Petals Around The Rose.'
The name of the game is significant.
At each turn I will roll five dice,
then ask you for the score, which
will always be zero or an even number.
After you guess the score, I will tell
you if you are right, or tell you the
correct score if you are wrong. The game
ends when you prove that you know the
secret by guessing the score correctly
six times in a row.

The five dice are: 4 2 5 5 4.
What is the score? 6
The correct score is 8.

The five dice are: 2 5 1 3 3.
What is the score? 8
Correct

The five dice are: 2 5 2 5 6.
What is the score? 8
Correct

The five dice are: 6 2 5 3 2.
What is the score? 8
The correct score is 6.

The five dice are: 4 2 1 1 2.
What is the score? 6
The correct score is 0.

The five dice are: 5 6 3 6 6.
What is the score? 6
Correct

The five dice are: 2 6 2 2 4.
What is the score? 6
The correct score is 0.

The five dice are: 3 2 4 2 1.
What is the score? 0
The correct score is 2.

The five dice are: 4 4 2 6 3.
What is the score? 2
Correct

The five dice are: 2 1 5 1 5.
What is the score? 8
Correct

The five dice are: 1 5 5 2 4.
What is the score? 8
Correct

The five dice are: 5 2 4 6 3.
What is the score? 6
Correct

The five dice are: 1 6 1 5 3.
What is the score? 6
Correct

The five dice are: 1 4 3 2 6.
What is the score? 2
Correct

Congratulations! You are now a member
of the Fraternity of the Petals Around
The Rose. You must pledge never to
reveal the secret to anyone.

You can play Petals Around The Rose on the internet, or read about Bill Gates’ encounter with the game.

Your task is to figure out the secret, then write a program to play Petals Around The Rose. 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 we have an exercise, a solution, and a question I don’t know the answer to. The exercise is to write a program that lists the narcissistic numbers in which the sum of the nth powers of the digits of an n-digit number is equal to the number. For instance, 153 is a narcissistic number of length 3 because 1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153. The largest decimal narcissistic number is the 39-digit number that is the title of today’s exercise.

Your task is to write a program to find narcissistic numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

Pages: 1 2

I recently found a book by Niklaus Wirth in a used book store; it’s a fascinating book and has been the source of a few recent exercises:

Niklaus Wirth, Eidgenössische Technische Hochschule, Zürich, Switzerland. Systematic Programming: An Introduction. 1973: Prentice-Hall, Inc. Englewood Cliffs, New Jersey. ISBN 0-13-880369-2.

Most of the book is concerned with teaching the syntax and semantics of Wirth’s language Pascal, but the final chapter is devoted to stepwise program development, where Wirth demonstrates by example four different problems which he solves by developing programs through a succession of stepwise refinements. The last section is a kind of “final exam” for readers; it’s the longest section of the book, by far, and gives a complete, detailed exposition of the solution to the following problem:

Generate a sequence of N characters, chosen from an alphabet of three elements (e.g., 1, 2, 3), such that no two immediately adjacent subsequences are equal.

For instance, the sequence of length N = 5 with the characters “12321” is acceptable, but neither “12323” nor “12123” are.

Your task is to write a program that not only solves the stated problem but also gives all possible solutions, not just a single solution, for any given 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

In his 1973 book Systematic Programming: An Introduction, Niklaus Wirth gives the following problem as exercise 15.12:

Develop a program that generates in ascending order the least 100 numbers of the set M, where M is defined as follows:

a) The number 1 is in M.

b) If x is in M, then y = 2 * x + 1 and z = 3 * x + 1 are also in M.

c) No other numbers are in M.

Wirth also gives the first six numbers in the result sequence: 1, 3, 4, 7, 9, 10….

Your task is to write a program that finds the first n numbers in Wirth’s sequence, and use it to solve Wirth’s exercise. 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 computed the median of five items by sorting them and then taking the third item. Sorting does more work than is necessary; for instance, given the list [1, 2, 3, 5, 4], we don’t need to swap 5 and 4 into their correct positions to determine that 3 is the median as long as we know that both 4 and 5 are greater than 3..

Your task is to write a function that determines the median of five items using the fewest possible comparisons. 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 studied a selection algorithm in a previous exercise. The algorithm is the same as quicksort, except that recursion follows only the partition in which the target of the selection is located. We used a randomized algorithm to select the pivot, which gives an expected O(n) time complexity but a worst-case O(n^2) time complexity. In today’s exercise we examine an algorithm due to Blum, Floyd, Pratt, Rivest and Tarjan from their 1973 paper “Time Bounds for Selection” in Journal of Computer Systems Science that provides guaranteed O(n) time complexity (actually, the time complexity is sub-linear, but the only claim is that it is linear).

The algorithm is the same as the previous exercise except in the selection of the pivot. Instead of a random pivot, the algorithm partitions the input into blocks of five elements, finds the median of each block by comparisons, then chooses the median of the medians (which is computed recursively) as the pivot. Thus, the algorithm is known as “selection by the median of the medians of five.”

Your task is to write a function that selects the kth item from a list. 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 today another question from our inexhaustible set of interview questions; this one comes from Amazon:

Given a million points (x, y), give an O(n) solution to find the 100 points closest to (0, 0).

Your task is to write the requested function. 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 operations of modular arithmetic, and an important step in many algorithms of number theory, is finding modular square roots. In the expression x² ≡ a (mod p), x is a modular square root of a; for instance, 62 is a square root of 2, mod 113, because 62 * 62 = 3844 = 36 * 113 + 2. Like real numbers, modular square roots come in pairs, so -62 ≡ 51 (mod 113) is also a square root of 2.

The usual method for finding modular square roots involves an algorithm developed by Alberto Tonelli in the 1890s; there are several variants, including one due to Daniel Shanks in 1973, one of which we saw in a previous exercise. The particular variant that we will look at today is described at http://www.math.vt.edu/people/brown/doc/sqrts.pdf.

We will assume that the modulus p = s · 2^e + 1 is an odd prime, that the number a for which we seek a square root is coprime to p, and that the Legendre symbol (a/p) is 1, which indicates that the square root exists. Find an n such that n^(p−1)/2 ≡ −1 (mod p); it won’t take long if you start from n = 2 and increase n by 1 until you find one. Then set x ≡ a^(s+1)/2 (mod p), b ≡ a^s (mod p), g ≡ n^s (mod p), and r = e. Next find the smallest non-negative integer m such that b^2m ≡ 1 (mod p), which is done by repeated squarings and reductions. If m is zero, you’re finished; report the value of x and halt. Otherwise, set x to x · g^2r−m−1 (mod p), set b to b · g^2r−m (mod p), set g to g^2r−m (mod p), and set r = m, then loop back and compute a new m, continuing until m is zero.

As an example we find the square root of 2 mod 113. First compute p = 113 = 7 · 2⁴ + 1 and n = 3, then x = 16, b = 15, g = 40, and r = 4. The first computation of m is 2, so set x = 62, b = 1, g = 98, and r = 2. Then the second computation of m is 0, so x = 62 is a square root of 2 (mod 113), and so is 113 – 62 = 51.

Your task is to write a function that computes modular square roots according to the algorithm 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

I receive several emails from my readers each week, and I try to answer every one of them (except those that begin “I really admire your blog. You are obviously a great programmer. It has nothing to do with your recent exercise, but I am a student just learning to program, and I need help with my Java program that doesn’t work. Can you look at this program and tell me what is wrong? And they attach 400 lines of code without even bothering to tell me what is the task, or providing sample input and output, or even their name). I love to hear from my readers; your emails sustain me, and keep me writhing.

I had an email from a reader yesterday asking why I didn’t assign list differencing as a task when I assigned list intersection and union. The answer is: because I forgot!

So today we look at list differencing. Given two lists, their difference is the items in the first list that are not in the second list. For our sample lists A containing 4, 7, 12, 6, 17, 5, and 13 and B containing 7, 19, 4, 11, 13, 2, and 15, the difference A − B is 12, 6, 17, and 5 and the difference B − A is 19, 11, 2, and 15.

Your task is to write three list differencing functions, one each with time complexities O(n²), O(n log n), and O(n), and perform timing tests to confirm the expected time complexities. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution in the comments below.

Pages: 1 2