Programming Praxis

We examined the Baillie-Wagstaff probabilistic primality checker based on Lucas pseudoprimes in a previous exercise, where we got it wrong; among other things it incorrectly reported that 3825123056546413051 = 149491 × 747451 × 34233211 was prime. We’ll fix that today. Robert Baillie and Samuel Wagstaff Jr. describe the test in their article “Lucas Pseudoprimes” in Mathematics of Computation, Volume 35, Number 152, pages 1391-1417, October 1980; see also Thomas Nicely’s web page devoted to the test. This is the same algorithm used in the PrimeQ function in Mathematica. If at any point the math gets daunting, feel free to skip ahead to the code, which is short and simple.

Lucas numbers are defined by a recurrence formula similar to Fibonacci numbers, where L_n = L_n−1 + L_n−2 with L₁ = 1 and L₂ = 3; the Lucas numbers are 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, … (Sloane’s A000204). Lucas numbers have the rather startling property that, if n is prime, L_n ≡ 1 (mod n). But the converse is not true, and composite numbers n such that L_n ≡ 1 (mod n) are known as Lucas pseudoprimes; the first few Lucas pseudoprimes are 705, 2465, 2737, 3745, 4171, … (Sloane’s A005845).

Lucas numbers are a special case of Lucas sequences. If P and Q are integers such that the discriminant D = P² − 4Q, then the roots of x² − Px + Q = 0 are a = (P + √D) / 2 and b = (P − √D) / 2 (that’s the quadratic equation you learned in middle school). There are two Lucas sequences U_n(P,Q) = (aⁿ − bⁿ) / (a − b) and V_n(P,Q) = aⁿ + aⁿ for n ≥ 0, which can be computed by the recurrence equations U_m(P,Q) = PU_m−1(P,Q) − QU_m−2(P,Q) and V_m(P,Q) = PV_m−1(P,Q) − QV_m−2(P,Q). The Lucas numbers are given by the sequence V(1, -1) and the Fibonacci numbers are given by the sequence U(1, -1).

It is possible to compute the nth element of a Lucas sequence in logarithmic time rather than linear time using a double-and-add algorithm similar to the peasant algorithm for multiplication; such a computation is known as a Lucas chain. The rules are U_2n = U_n V_n, U_2n+1 = U_n+1 V_n − Qⁿ, V_2n = V_n² − 2 Qⁿ, and V_2n+1 = V_n+1 V_n − P Qⁿ. For our purposes, we will be making all computations mod n.

Thus we have a method to determine if a number n is a Lucas pseudoprime. Choose a suitable P and Q, use a Lucas chain to compute U_n(P,Q), and declare n either prime or a Lucas pseudoprime if U_n(P,Q) ≡ 0 (mod n). There are several methods to compute suitable P and Q, of which the most commonly-used is due to John Selfridge: choose D as the smallest number in the sequence 5, -7, 9, -11, 13, -15, 17, … for which the Jacobi symbol (D / n) = -1, then set P = 1 and Q = (1 – D) / 4.

There is a strong version of the Lucas pseudoprimality test that bears the same relationship to the standard version of the Lucas pseudoprimality test described above as Gary Miller’s strong Fermat pseudoprimality test bears to the standard Fermat pseudoprimality test. Represent n as d · 2^s + 1, then compute U_d(P,Q) and V_d(P,Q). Then n is either prime or a Lucas pseudoprime if U_d(P,Q) ≡ 0 (mod n) or if V_{d 2^r}(P,Q) ≡ 0 (mod n) for any r with 0 ≤ r < s.

Finally, the Baillie-Wagstaff test of the primality of n consists of the following steps: 1) if n is not an integer, report a domain error; 2) if n < 2, report n is not prime; 3) if n is a square, report n is not prime; 4) if n is divisible by any primes less than some convenient limit (e.g. 100 or 1000), report n is not prime; 5) if n is not a strong Fermat pseudoprime to base 2, report n is not prime; 6) (optional, added by Mathematica) if n is not a strong Fermat pseudoprime to base 3, report n is not prime; 7) if n is not a Lucas pseudoprime (standard or strong), report n is not prime; 8) otherwise, report n is prime.

The Baillie-Wagstaff pseudoprimality test, whether or not the base-3 test is included and whether the standard or strong Lucas test is chosen, is extremely strong: there are no known errors. Exhaustive checks have been performed to 10¹⁷, and the test has been used for years in several high-quality primality proving programs that would have found an error if one occurred. There is a $620 reward for a counter-example to the test ($500 from Selfridge, $100 from Wagstaff, and $20 from Carl Pomerance), plus the certain fame that will accrue to the finder.

Your task is to write a Baillie-Wagstaff primality checker 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.

Pages: 1 2

I’m not sure where this comes from; it could be an interview question, or some kind of programming puzzle:

Write a function that takes a positive integer n and returns n-squared. You may use addition and subtraction but not multiplication or exponentiation.

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

[ Today’s exercise was contributed by Tom Rusting, who worked as a programmer until the mid 70’s. Being retired, he has now taken up programming again as a hobby. Suggestions for exercises are always welcome, or you may wish to contribute your own exercise; feel free to contact me if you are interested.

Floup is an island-country in the South Pacific with a currency known as the floupia; coins are denominated in units of 1, 3, 7, 31 and 153 floupias. Merchants and customers engage in a curious transaction when it comes time to pay the bill; they exchange the smallest number of coins necessary to complete the payment. For instance, to pay a bill of 17 floupia, a customer could pay three 7-floupia coins and receive single 1-floupia and 3-floupia coins in exchange, a total of five coins, but it is more efficient for the customer to pay a single 31-floupia coin and receive two 7-floupia coins in exchange.

Your task is to write a program that determines the most efficient set of coins needed to make a payment, generalized for any set of coins, not just the set 1, 3, 7, 31 and 153 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

[ Today is the fourth anniversary of Programming Praxis, which published five exercises on February 19, 2009. I remember getting 6 hits that day, all of them from one friend that I told about the blog. I get a few more hits now. Many thanks to all of my readers, whose comments and emails inspire me to continue. — Phil ]

We haven’t done a word puzzle for a while. Here is one from the NPR Sunday Puzzle:

Think of two familiar, unhyphenated, eight-letter words that contain the letters A, B, C, D, E and F, plus two others, in any order. What words are these?

Your task is to write a program to find the two words. 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

Round 1 of the Facebook Hacker Cup 2013 is now complete. In today’s exercise we look at Problem 1:

CARD GAME (20 points)

John is playing a game with his friends. The game’s rules are as follows: There is deck of N cards from which each person is dealt a hand of K cards. Each card has an integer value representing its strength. A hand’s strength is determined by the value of the highest card in the hand. The person with the strongest hand wins the round. Bets are placed before each player reveals the strength of their hand.

John needs your help to decide when to bet. He decides he wants to bet when the strength of his hand is higher than the average hand strength. Hence John wants to calculate the average strength of ALL possible sets of hands. John is very good at division, but he needs your help in calculating the sum of the strengths of all possible hands.

PROBLEM

You are given an array a with N ≤ 10000 different integer numbers and a number, K, where 1 ≤ K ≤ N. For all possible subsets of a of size K find the sum of their maximal elements modulo 1000000007.

INPUT

The first line contains the number of test cases T, where 1 ≤ T ≤ 25

Each case begins with a line containing integers N and K. The next line contains N space-separated numbers 0 ≤ a [i] ≤ 2000000000, which describe the array a.

OUTPUT

For test case i, numbered from 1 to T, output "Case #i: ", followed by a single integer, the sum of maximal elements for all subsets of size K modulo 1000000007.

EXAMPLE

For a = [3, 6, 2, 8] and N = 4 and K = 3, the maximal numbers among all triples are 6, 8, 8, 8 and the sum is 30.

EXAMPLE INPUT

    5
    4 3
    3 6 2 8
    5 2
    10 20 30 40 50
    6 4
    0 1 2 3 5 8
    2 2
    1069 1122
    10 5
    10386 10257 10432 10087 10381 10035 10167 10206 10347 10088

EXAMPLE OUTPUT

    Case #1: 30
    Case #2: 400
    Case #3: 103
    Case #4: 1122
    Case #5: 2621483

Your task is to write a program that solves the Facebook problem 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 seen several flavors of binary search trees, including classic bsts, treaps, red/black trees, and avl trees. For all of them we provided a lookup function that returned a requested key/value pair. In today’s exercise we write functions that return the predecessor and successor of a requested key, allowing a program to walk the tree in order. There are two common variants of these functions, one using parent pointers and one without; our exercise will use the variant without parent pointers, which is generally more useful.

We give the basic logic for the successor function; the predecessor function is similar, but reversed. A recursive function descends the tree searching for the requested key, keeping track of the current tree as the possible successor every time if follows the left sub-tree. If it finds the key, its successor is the minimum element of the right sub-tree, found by chasing left sub-trees until reaching a null node. If the search reaches a null node and hence fails to find the key, the next largest key in the tree is the successor, found in the possible successor that was saved at each recursive call.

Your task is to write predecessor and successor functions for binary search trees. 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

It has been widely reported that a new “biggest prime” was found two weeks ago. The prime, which has 17,425,170 digits, is:

2^57,885,161 − 1

Your task is to write a program that displays all seventeen million digits of the biggest prime. 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 comes to us from the world of recreational mathematics:

Find all possible solutions to the equation 1/a + 1/b + 1/c + 1/d + 1/e = 1 where all of a, b, c, d and e are positive integers.

One solution is the trivial 1/5 + 1/5 + 1/5 + 1/5 + 1/5. Another solution, based on the perfect number 1 + 2 + 4 + 7 + 14 = 28, is 1/2 + 1/4 + 1/7 + 1/14 + 1/28. The minimum distinct solution is 1/3 + 1/4 + 1/5 + 1/6 + 1/20, where all the denominators are distinct and the sum of the denominators 3 + 4 + 5 + 6 + 20 = 38 is minimum over all solutions.

Your task is to write a program to enumerate all possible solutions to the equation. 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

On page 73 of his book Gödel, Escher, Bach: An Eternal Golden Braid, Douglas Hofstadter asks you to think about the following sequence:

1, 3, 7, 12, 18, 26, 35, 45, 56, 69, …

Hofstadter leaves you to figure out the rule that produces the sequence, though he does give some hints in the surrounding text.

Your task is to write a program that produces the first n elements of Hofstadter’s sequence. 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 today our third essay: SRFI-41 Streams. An essay isn’t an exercise; it doesn’t present a task for you to perform, but instead provides extended discussion and complete source code. Though essays may be based on exercises, the idea is that an essay can delve more deeply into a topic than is possible in the limited space and time of an exercise.

Today’s essay describes a data structure that is fundamental to functional programming languages. Streams, also known as lazy lists, are a sequential data structure containing elements computed only on demand. A stream is either null or is a pair with a stream in its cdr. Since elements of a stream are computed only when accessed, streams can be infinite. Once computed, the value of a stream element is cached in case it is needed again. Streams without memoization were first described by Peter Landin in 1965. Memoization became accepted as an essential feature of streams about a decade later. Today, streams are the signature data type of functional programming languages such as Haskell.

Please read the essay, and feel free to comment on it below; comments on the essay itself are closed. Let me know if you see any errors. And feel free to link to the essay on the internet if you know of places where it is appropriate.