Programming Praxis

In the previous exercise we studied Legendre’s prime-counting function. In today’s exercise we will look at two more prime-counting functions, one from Ernst Meissel in the late 1800s and the other from Derrick Lehmer in the mid 1990s.

Both formulas are based on Legendre’s original formula; in both cases, they simply rearrange the terms of Legendre’s formula to eliminate some work. We won’t try to give derivations, as they are complex and chock-full of Greek letters; if you are interested, Hans Riesel’s book Prime Numbers and Computer Methods for Factorization was the source for all three formulas.

Meissel: , where and

Lehmer: , where , , , and for .

Your task is to implement the prime-counting functions of Meissel and Lehmer, then compare timings with Legendre's prime-counting function of the previous 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

The prime-counting function π(n) computes the number of primes not greater than n, and has been a matter of fascination to mathematicians for centuries. The Prime Number Theorem tells us that π(n) is approximately n / log(n); Carl Fredrich Gauss proposed the prime number theorem in 1792 when he was only fifteen years old, and Jacques Hadamard and Charles-Jean de la Valle Poussin both proved it, independently, in 1896. The first person to make a serious attempt at the calculation, except for trivial attempts that simply enumerated the primes and counted them, was the French mathematician Adrien-Marie Legendre at the end of the eighteenth century; his formula was correct, but he erroneously reported that π(10⁶) = 78526, whereas the correct value is 78498. We will recreate Legendre’s calculation in today’s exercise.

Legendre’s formula works in two parts. First, he defined a function φ(x, a) that counts all the numbers from 1 to x inclusive that are not stricken by sieving with the first a primes. For instance φ(50, 3) = 14, because the numbers 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 and 49 less than or equal to 50 are not divisible by the first three primes 2, 3, or 5. The φ function can be computed by the recurrence equation φ(x, a) = φ(x, a−1) − φ(x/p_a, a−1), where φ(x, 1) is the number of odd integers less than or equal to x and p_a is the ath prime number. The second part of Legendre’s formula uses the φ function to compute the value of π recursively: π(x) = φ(x, a) + a − 1, where a = π(⌊√x⌋).

Your task is to write φ and π functions and recreate Legendre’s calculation of π(1000000). 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 exercise in our on-going series of interview questions:

Write a program that takes a list of integers and a target number and determines if any two integers in the list sum to the target number. If so, return the two numbers. If not, return an indication that no such integers exist.

Your task is to write the indicated 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

In the previous exercise we wrote a function to read JSON input and parse it into an object in the native language. In today’s exercise we write the inverse function.

Your task is to write a function that takes a JSON object and writes it in text format. 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

JavaScript Object Notation, JSON, is a system for passing structured data between computers, similar to XML but far simpler. JSON provides Unicode strings with a limited number of escapes, decimal numbers, the booleans true and false, the null value, arrays, and key/value dictionaries with string keys.

Your task is to write a parser that converts JSON data to an object in your favorite computer language. 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

Vedic arithmetic is a system of arithmetic devised in India for pencil-and-paper calculations. One of the calculations determines if one number is a divisor of another; the divisor must be odd and not divisible by 5; if the divisor is even or divisible by 5, factors of 2 and 5 should be removed before continuing. The calculation is a three-step process:

1) Determine the osculator of the divisor by multiplying it by the smallest number that will make the last digit 9, then strip the last digit 9 and add 1.

2) For each digit in the dividend, strip the last digit, then add that last digit times the osculator to the remaining digits in the dividend, giving a new dividend. Repeat as long as the dividend keeps decreasing.

3) Finally, divide the remaining dividend by the original divisor. If the remainder is 0, then the original divisor evenly divides the original dividend; otherwise not.

Here’s an example. For a divisor of 23, the number 23 is multiplied by 3, giving 69, then the last digit 9 is stripped, giving 6, and 1 is added, giving 7; thus, the osculator for 23 is 7. To test if 13174584 is divisible by 23, strip the 4 from the end of 13174584, multiply the stripped 4 times the osculator 7, giving 28, and add 28 to the stripped dividend 1317458 giving 1317486. Repeat, giving a new dividend of 131748 + 42 = 131790. Repeat again, giving a new dividend of 13179 (you can always drop a trailing 0, because 0 times the osculator is 0). Another iteration gives a new dividend of 1317 + 63 = 1380, from which we drop the trailing 0, giving 138. One final iteration gives 13 + 56 = 69. Now 69 ÷ 23 = 3, so 23 divides 13174584 and we are finished.

It is obviously easier for a computer to just perform the division and check the remainder; this method is intended for pencil-and-paper calculation (or even mental calculation).

Your task is to write a function that implements the Vedic divisibility test. 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

For our final exercise in the big-numbers series, we use the library to implement some algorithms: display the factorials to 50, compute the factors of a number using trial division, determine if a number is prime using the Miller-Rabin algorithm, and compute the factors of a prime using Pollard’s rho algorithm.

Your task is to implement these algorithms using the big-number 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

Drawing programs measure distances in ten-thousandths of an inch, like 73.0185, but carpenters work in feet, inches, and thirty-seconds of an inch, like 6 feet 1 and 1/32 inches.

Your task is to write a program that takes a measurement in decimal notation and returns the measurement in carpenter’s notation; readers unfamiliar with imperial measurements will want to know that there are twelve inches in a foot. 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 complete the big number library that we have been building over the past several exercises with a handful of useful functions. Big-gcd finds the greatest common denominator of two big numbers. Big-expt raises a big number to a power. Big-expm raises a big number to a power, modulo another big number. Big-sqrt calculates the square root of a big number. Big-rand returns a random big number, and optionally resets the seed of the random number generator. Integer->big and big->integer are optional; if the underlying language supports big numbers natively, these functions convert between our big numbers and native big numbers.

Your task is to complete the big number 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 3

We have previously given two algorithms to calculate the day of the week, one in the Standard Prelude and one in the exercise on Zeller’s Congruence. In today’s exercise we give three more algorithms to calculate the day of the week.

Our first method is due to Carl Gauss, and is based on moving January and February to the end of the preceding year, then fitting a straight line through the number of days in each month. Gauss gives the formula where Y is the input year, except that it is reduced by 1 in January and February, d is the day of the month, m is the number of the month, with 1 for March through 12 for February, y is the last two digits of Y, c is the first two digits of Y, and w is the day of the week, with 0 for Sunday through 6 for Saturday. For instance, June 24, 2011 is calculated as 24 + floor(2.6×4−0.2) + 11 + floor(11÷4) + floor(20÷4) – 2×20, modulo 7, which is 5 for Friday.

Our second method is due to Tomohiko Sakamoto, who gives a table of offsets for the days of each month from the day at the start of the year: t = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}. Then Sakamoto subtracts 1 from the input year in January and February and calculates the day of the week with the formula . For instance, June 24, 2011 is calculated as 2011 + floor(2011÷4) − floor(2011÷100) + floor(2011÷400) + t[6−1] + 24 = 2011 + 502 – 20 + 5 + 3 + 24 = 2525, modulo 7, which is 5 for Friday.

Our third method is due to John Horton Conway, and is intended for mental calculation. Conway’s method is based on calculating the anchor day for the requested century, the doomsday for the requested year, and interpolating from various repetitions of the doomsday through the year.

The anchor day is calculated as , where c is the century; note that century years, such as 2000, are part of the succeeding century, so c=21 for the year 2000. For example, the anchor day for the 21^st century is Tuesday, calculated as 5×21 + floor(20÷4), modulo 7, plus Thursday. Anchor days repeat every four centuries, in the cycle Friday, Wednesday, Tuesday, Sunday starting from the year 1800.

The doomsday is calculated by dividing the last two digits of the year by 12 to calculate the quotient and remainder. Then the doomsday is the quotient, plus the remainder, plus the quotient of the remainder divided by 4, plus the anchor day for the century. For example, the doomsday for 2011 is Monday, calculated as 0 + 11 + floor(11÷4) = 13, which is 6 modulo 7, plus the anchor day Tuesday.

Once the doomsday is known, the day of the week is calculated by locating the nearest doomsday in each month, which can be memorized in the following manner: For April, June, August, October, and December, the doomsday is the month number: 4/4, 6/6, 8/8, 10/10, and 12/12. For May, July, September, and November, the doomsday can be calculated by the ditty “I worked 9 to 5 at 7-11” which gives 5/9, 7/11, 9/5, and 11/7. The last day of February is a doomsday, whether a common year or a leap year, and this gives an easy way to calculate the day of the week for March, where doomsday is 3/0 (the “zeroth” day of March). All that’s left is January, for which the doomsday is 1/10 in common years and 1/11 in leap years.

Thus, the day of the week for June 24, 2011 is calculated as 24−6=18 ≡ 4 (mod 7) days past the doomsday, which gives an answer of Friday. Conway claims to be able to calculate any day of the week in two seconds, though I confess I have not been able to make the required calculations reliably except by using pencil and paper to assist.

Your task is to write programs to calculate the day of the week using the three functions described above; for Conway’s algorithm, you should calculated the doomsday for the year rather than the day of the week for the date. 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