Programming Praxis

Some programmers write variable names in camelCase, each word starting with a capital letter, while other programmers separate words with underscores like_this.

Your task is to write programs that convert between the two forms. 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’ve seen this problem several times on Stack Overflow and other message boards:

Write a program to find the nearest prime number to a given real number. You may limit the search to the hundred smallest primes.

Your task is to write the program to find the nearest prime number. 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 oldest algorithm for factoring integers, still used today, is trial division, which takes time proportional to the square root of the number being factored. In the 17th century, Pierre de Fermat invented a different algorithm, based on finding a difference of squares, that also takes time proportional to the square root of the number being factored, but works well when a number’s two factors are both near the square root of the number; we studied Fermat’s algorithm in a previous exercise. In today’s exercise we will study a factoring algorithm due to R. Sherman Lehman that modifies Fermat’s algorithm so it takes time proportional to the cube root of the number being factored. Lehman’s algorithm suffers the same problem as Fermat’s — it is slow unless the two factors are near each other — but in cases where it is appropriate, it is much faster than Fermat’s algorithm.

Let’s begin by recapping Fermat’s algorithm. It starts by taking the smallest integer larger than the square root of the number n being factored, call that number a, then increases a by 1 until b = a² − n is a square, at which point we have n = a² − b² = (a − b) (a + b) = n by algebraic identity. Pomerance likes to use the example 8051 = 90² − 7² = (90 − 7) (90 + 7) = 83 × 97; he tells the story of an arithmetic contest in his school days that he lost because he didn’t recognize the difference of squares. Here is how Crandall and Pomerance give Fermat’s algorithm in their book Prime Numbers: A Computational Perspective:

Algorithm 5.1.1 (Fermat method). We are given an odd integer n > 1. This algorithm either produces a nontrivial divisor of n or proves n prime.

1. [Main loop]
    for (⌈√n⌉ ≤ a ≤ (n + 9) / 6) {
        if (b = √(a2 − n) is an integer) return a − b
    }
    return "n is prime"

In their book, Crandall and Pomerance prove the odd termination condition of the loop.

There are tricks, both mathematical and computational, that can speed up Fermat’s algorithm, but in general you will have to accept that it is pretty slow, because no matter what you do you have to count from √n to n, which is a long way.

One useful trick is to multiply n by a multiplier. Crandall and Pomerance give the example of n = 2581. Fermat’s algorithm has us start with a = 51 and take 9 square roots, finding a difference of squares when a = 59, so that 59² − 2581 = 900 = 30² and 2581 = (59 − 30) (50 + 30) = 29 × 89. But if we take the multiplier k = 3, then kn = 3 × 2581 = 7743, Fermat’s algorithm starts with a = 88, and on the first iteration through the loop b = 88² − 7743 = 1, the factorization of kn = (88 − 1) (88 + 1) = 87 × 89, and the factorization of n = gcd(87, n) × gcd(89, n) = 29 × 89.

Of course, there is no way to know a priori that multiplier k = 3 leads to a quick factorization. Lehman’s method systematizes the search for a good multiplier. Here is how Crandall and Pomerance give Lehman’s algorithm:

Algorithm 5.1.2 (Lehman method). We are given an integer n > 21. This algorithm either provides a nontrivial factor of n or proves n prime.

1. [Trial division]
Check whether n has a nontrivial divisor d ≤ n^1/3, and if so, return d.

2. [Loop]

    for (1 ≤ k ≤ ⌈n1/3) {
        for (⌈√(4kn⌉)⌉ ≤ a ≤ ⌊√(4kn) + n1/6 / (4√k)⌋) {
            if (b = √(a2 − 4kn) is an integer) return gcd(a + b, n)
        }
    }
    return "n is prime"

Again, Crandall and Pomerance prove the odd termination condition in their book, and also the odd input condition n > 21. They also prove that Lehman’s algorithm takes time proportional to the cube root of the number being factored. Lehman’s algorithm is of historical importance, as it was the first factoring algorithm to take less than time proportional to the square root of the number being factored, but it is was never used in practice, as Jon Pollard’s rho algorithm was published shortly after Lehman’s algorithm, and it has both a better time complexity, taking time proportional to the fourth root of the number being factored, and is also significantly faster in practice.

Your task is to implement the factoring algorithms of Fermat and Lehman; you might want to do some timing experiments to compare them to each other and to naive trial division. 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 a simple matter of counting:

Suppose you can take either one or two steps at a time. How many ways can you travel a distance of n steps? For instance, there is 1 way to travel a distance of 1 step, 2 ways (1+1 and 2) to travel two steps, and 3 ways (1+1+1, 1+2 and 2+1) to travel three steps.

Your task is to write a program to count the number of ways to travel a distance of n steps, taking 1 or 2 steps at a time. 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 task looks like homework:

Make a list of n-digit phone numbers according to the following rules:

1) First digit must not be zero.
2) First digit may be four, but no digits after the first may be four.
3) Any two consecutive digits must be different.
4) The user may specify any set of digits that may not appear in the phone number.

For instance, if n = 3 and the digits 1, 3, 5, 7, and 9 don’t appear in the output, the desired list of three-digit numbers starting with 2, 4, 6, or 8 followed by 0, 2, 6 or 8 without consecutive duplicates is: 202 206 208 260 262 268 280 282 286 402 406 408 420 426 428 460 462 468 480 482 486 602 606 608 620 626 628 680 682 686 802 806 808 820 826 828 860 862 868.

Your task is to write a program that generates phone numbers according to the rules given 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

We have an exercise today from the realm of recreational mathematics, based on a video from Numberphile. The two numbers 714 = 2 × 3 × 7 × 17 and 715 = 5 × 11 × 13 have, between them, the first seven prime numbers as their factors (baseball fans will understand the name of this exercise, others will have to watch the video). So the first exercise is to find other pairs of consecutive numbers that have as their factors all and only the first n primes, for some n.

Carl Pomerance, the speaker in the Numberphile video, credits one of his students for first noticing that the sums of the prime factors of 714 and 715 are equal: 2 + 3 + 7 + 17 = 5 + 11 + 13 = 29. So the second exercise is to find other pairs of consecutive numbers whose factors sum to the same number. This exercise can be divided into two parts: numbers where repeating factors are added in to the sum and numbers where only the distinct factors are added in to the sum.

Your task is to complete the three exercises; they will make much more sense if you watch the video. 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 a programming interview question from a programmer who very obviously didn’t get the job:

Given a C-style null-terminated string, move all the spaces in the string to the beginning of the string, in place, in one pass.

The candidate claimed it couldn’t be done, and apparently got into an argument with the interviewer, and took to the internet after the interview to vindicate himself about the “unfair question.”

Your task is to either write the requested program, or demonstrate that it cannot be done. 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 task is simple:

You are given a file containing one name per line in the format last name comma first name, optionally followed by another comma and a numeral (like Sr., or Jr., or IV), and are convert it to a file containing the names, one name per line, in the format first name, last name and numeral with no commas. You may assume the input is correctly formatted, with optional spaces after each of the two commas.

Your task is to convert a file of names to the correct format. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Consider a two-dimensional matrix containing integer entries in which all rows and all columns are sorted in ascending order; for example:

 1 12 43 87
 9 25 47 88
17 38 48 92
45 49 74 95

Your task is to write a program that takes a matrix as describe above, and a target integer, and determines if the target integer is present in the matrix. 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