## A Programming Puzzle

### June 28, 2013

Today’s exercise is a delightful little programming puzzle:

Write a function

`f`

so that`f(f(n)) = -n`

for all integersn.

When I first saw this puzzle, it took me two days before I had the necessary flash of inspiration, then about two minutes to write. Do yourself a favor and don’t peek at the suggested solution until you figure it out yourself.

Your task is to write function `f`

as 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.

## Swap list nodes

### June 25, 2013

We have today another from our never-ending list of interview questions:

Given a linked list, swap the

kth node from the head of the list with thekth node from the end of the list.

Your task is to write a function to perform the indicated task; be sure to test it thoroughly. 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.

## Multiple Polynomial Quadratic Sieve

### June 21, 2013

We studied the basic quadratic sieve algorithm for factoring integers in two previous exercises. Today we examine the multiple polynomial variant of the quadratic sieve, due to Peter Montgomery, which adds considerable power to the basic algorithm; we will be following Figure 2.2 and the surrounding text from Scott Contini’s thesis.

In the basic quadratic sieve we used a polynomial of the form *g*(*x*) = (*x* + *b*)^{2} – *n* where *b* = ⌈√*n*⌉. The problem with using a single polynomial is that the values of *g*(*x*) increase as *x* increases, making them less likely to be smooth. Eventually, the algorithm “runs out of gas” when the values of *g*(*x*) grow too large.

Montgomery’s suggestion was to use multiple polynomials of the form *g*_{a, b}(*x*) = (*a x* + *b*)^{2} − *n* with *a*, *b* integers with 0 < *b* ≤ *a*. The graph of *g*_{a, b}(*x*) is a parabola, and its values will be smallest when *a* ≈ √(2*n*) / *m*. Thus, we choose *b* so that *b*^{2} − *n* is divisible by *a*, say *b*^{2} − *n* = *a c* for some integer *c*, and *a* = *q*^{2} for some integer *q*. Then we calculate *g*_{a, b}(*x*) / *a* = *a x*^{2} + 2 *b x* + *c*, and, after sieving over the range −*m* .. *m*, when *g*_{a, b}(*x*) is smooth over the factor base we record the relation ((*a x* + *b*) *q*^{−1})^{2} = *a x*^{2} + 2 *b x* + *c*.

Here is our version of Contini’s algorithm:

Compute startup data: Choosef, the upper bound for factor base primes, andm, which is half the size of the sieve. Determine the factor base primesp<fsuch that the jacobi symbol (n/p) is 1 indicating that there is a solution tot^{2}≡n(modp); also include 2 in the factor base. For each factor base primep, compute and storet, a modular square root ofn(modp). Also compute and store the base-2 logarithm of each primel= ⌊log_{2}p⌉ (the floor and ceiling brackets indicate rounding).

Initialize a new polynomial: Find a primeq≈ √( √(2n) /m) such that the jacobi symbol (n/q) is 1, indicating thatnis a quadratic residue modq, and leta=q^{2}(modn). Computeb, a modular square root ofnmoda; you will have to compute the square root ofnmodqthen “lift” the root modq^{2}using Hensel’s Lemma. For each odd primepin the factor base, computesoln1=_{p}a^{−1}(tmem−_{p}b) andsoln2=_{p}a^{−1}(−tmem−_{p}b).

Perform sieving: Initialize a sieve array of length 2m+ 1 to zeros, with indices from −mtom. For each odd primepin the factor base, addlto the locations_{p}soln1+_{p}i pfor all integersithat satisfy −m ≤soln1+_{p}i p≤m, and likewise forsoln2. For the prime_{p}p= 2, sieve only withsoln1._{p}

Trial division: Scan sieve array for locationsxthat have accumulated a value of a least log(m √n) minus a small error term. Trial divideg_{a, b}(x) by the primes in the factor base. Ifg_{a, b}(x) factors into primes less thanf, then save smooth relation as indicated above. After scanning entire sieve array, if there are more smooth relations than primes in the factor base, then go to linear algebra step. Otherwise, go to initialization step to select a new polynomial.

Linear algebra: Solve the matrix as in Dixonâ€™s method and the continued fraction method. For each null vector, construct relation of formx^{2}≡y^{2}(modn) and attempt to factornby computing gcd(x−y,n). If all null vectors fail to give a non-trivial factorization, go to initialization step to select a new polynomial.

Your task is to write a program to factor integers using the multiple polynomial quadratic sieve as 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.

## 3SUM

### June 18, 2013

Today’s exercise is a classic problem of computer science: given an array of positive and negative integers, find three that sum to zero, or indicate that no such triple exists. This is similar to the subset sum problem, which we solved in a previous exercise, but simpler because of the limit to three items. A brute force solution that operates in O(*n*^{3}) time uses three nested loops to select items from the array and test their sum, but an O(*n*^{2}) solution exists. For instance, in the array [8, -25, 4, 10, -10, -7, 2, -3], the numbers -10, 2 and 8 sum to zero, as do the numbers -7, -3, and 10.

Your task is to write a program that solves the 3SUM problem in O(*n*^{2}) 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.

## The Digits of Pi, Again

### June 14, 2013

The ratio of the circumference to the diameter of a circle, known as π, is constant regardless of the size of the circle; that fact has been known to mathematicians for about five thousand years; much of the history of mathematics is intertwined in the history of πi, as approximations of the ratio have improved over time. Much of the history of this blog is also intertwined in the calculation of π; one of the original ten exercises used a bounded spigot algorithm of Jeremy Gibbons to calculate π, and later we used an unbounded spigot algorithm also due to Gibbons; we studied the ancient approximation of 355/113 calculated by Archimedes; we studied two different Monte Carlo simulations of π; and we even had the Brent-Salamin approximation contributed by a reader in a comment.

The development of computers allows us to compute the digits of π to an astonishing accuracy; the current record, unless somebody has bettered it recently, is ten trillion digits. That record was set by the Chudnovsky brothers, two Russian mathematicians living in New York, using an algorithm they developed in 1987. The algorithm is based on a definition of π developed by Ramanujan, and is beautifully described by the two brothers.

Your task is to compute many digits of π using the Chudnovsky algorithm. 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.

## Longest Substring Of Two Unique Characters

### June 11, 2013

Today’s exercise comes from our unending list of interview questions:

Find the longest run of consecutive characters in a string that contains only two unique characters; if there is a tie, return the rightmost. For instance, given input string

`abcabcabcbcbc`

, the longest run of two characters is the 6-character run of`bcbcbc`

that ends the string.

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

## Sets

### June 7, 2013

Sets are ubiquitous in programming; we’ve used sets in several of our exercises. In most cases we made the sets from lists, which is good enough when the sets are small but quickly slows down when the sets get large. In today’s exercise we will write a generic library for sets.

The sets that we will consider are collections of items without duplicates. We will provide an *adjoin* function to add an item to a set if it is not already present and a *delete* function to remove an item from a set if it is present. A *member* function determines if a particular item is present in a set. The three set operations that are provided are *intersection*, *union* and *difference*; we will consider that the universe from which items are drawn is infinite, or at least too large to conveniently enumerate, so we will not provide a *complement* operation. For convenience, we will also provide functions to calculate the *cardinality* of a set and to create a *list* from the items present in the set.

Your task is to write a library for handling sets, based on the description 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.

## Egyptian Fractions

### June 4, 2013

One topic that has always fascinated me is the mathematical sophistication of the ancients. The Pythagorean theorem is twenty-five hundred years old. Euclid’s *Elements* of 300BC remained in use as a geometry textbook for over two millenia, and is still in print today (you can buy the Dover edition for $1). Eratosthenes was sieving prime numbers two centuries before Christ.

Today’s topic is Egyptian fractions, which were mentioned in the Rhind Papyrus of 500BC as an “ancient method” and are thought to date to the time of the pyramids; they survived in use until the 17th or 18th century. Leonardo de Pisa’s famous book *Liber Abaci* of 1215AD, which introduced to European mathematicians the concept of zero, the Hindu-Arabic system of numeration, and the famous rabbit sequence (Leonardo’s nickname was Fibonacci).

An Egyptian fraction was written as a sum of unit fractions, meaning the numerator is always 1; further, no two denominators can be the same. As easy way to create an Egyptian fraction is to repeatedly take the largest unit fraction that will fit, subtract to find what remains, and repeat until the remainder is a unit fraction. For instance, 7 divided by 15 is less than 1/2 but more than 1/3, so the first unit fraction is 1/3 and the first remainder is 2/15. Then 2/15 is less than 1/7 but more than 1/8, so the second unit fraction is 1/8 and the second remainder is 1/120. That’s in unit form, so we are finished: 7 ÷ 15 = 1/3 + 1/8 + 1/120. There are other algorithms for finding Egyptian fractions, but there is no algorithm that guarantees a maximum number of terms or a minimum largest denominator; for instance, the greedy algorithm leads to 5 ÷ 121 = 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225, but a simpler rendering of the same number is 1/33 + 1/121 + 1/363.

Your task is to write a program that calculates the ratio of two numbers as an Egyptian fraction. 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.