A Prime Number Puzzle
November 28, 2014
Today’s exercise comes from the world of recreational mathematics.
For each number n from 1 to 9 inclusive, find a number m that begins with the digit n, has n digits, has each two-digit sequence within m a different prime number, and is as small as possible.
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.
Thou Impertinent Urchin-Faced Miscreant!
November 25, 2014
In 1968, Newsweek published an article “How to Win at Wordsmanship” by Philip Broughton. You pick a random number from 000 to 999, then look up a three word phrase in a table coded by the three digits of the random number:
Column 1 | Column 2 | Column 3 |
0. integrated | 0. management | 0. options |
1. total | 1. organizational | 1. flexibility |
2. systematized | 2. monitored | 2. capability |
3. parallel | 3. reciprocal | 3. mobility |
4. functional | 4. digital | 4. programming |
5. responsive | 5. logistical | 5. concept |
6. optional | 6. transitional | 6. time-phase |
7. synchronized | 7. incremental | 7. projection |
8. compatible | 8. third-generation | 8. hardware |
9. balanced | 9. policy | 9. contingency |
For instance, the random number 031 leads to the phrase “integrated reciprocal flexibility,” which you can use in a technical conversation or report. Broughton said “No one will have the remotest idea of what you are talking about, but the important thing is that they’re not about to admit it.”
Since then, many buzz-phrase generators have been developed, including corporate-speak “holistically embrace customer-directed imperatives” and the Shakespearean insult generator that gave us the title of our exercise. We have a couple of word lists on the next page, or you can Google for “buzz-phrase generator” to find lots of them on the web, but it’s most fun to build your own.
Your task is to write a program that generates random buzz-phrases. 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.
An Array Of Zeroes
November 21, 2014
Beware! Today’s exercise, which derives from an interview question asked at Facebook, is trickier than it looks:
You are given an array of integers. Write a program that moves all non-zero integers to the left end of the array, and all zeroes to the right end of the array. Your program should operate in place. The order of the non-zero integers doesn’t matter. As an example, given the input array [1,0,2,0,0,3,4], your program should permute the array to [1,4,2,3,0,0,0] or something similar, and return the value 4.
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.
Damm’s Algorithm
November 18, 2014
We studied Hans Peter Luhn’s algorithm for generating check digits in a previous exercise. Today, we look at an alternate check digit algorithm developed by H. Michael Damm. Both algorithms are useful for creating checked identification numbers, suitable for credit cards or other identity numbers.
Damm’s algorithm is based on table lookup. It is initialized with a current check digit of 0. Then, each digit of the number, from left to right (most-significant to least-significant) is looked up in a two-dimensional table with the current check digit pointing to the row and the digit of the number pointing to the column, using this table:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
0 | 0 | 3 | 1 | 7 | 5 | 9 | 8 | 6 | 4 | 2 |
1 | 7 | 0 | 9 | 2 | 1 | 5 | 4 | 8 | 6 | 3 |
2 | 4 | 2 | 0 | 6 | 8 | 7 | 1 | 3 | 5 | 9 |
3 | 1 | 7 | 5 | 0 | 9 | 8 | 3 | 4 | 2 | 6 |
4 | 6 | 1 | 2 | 3 | 0 | 4 | 5 | 9 | 7 | 8 |
5 | 3 | 6 | 7 | 4 | 2 | 0 | 9 | 5 | 8 | 1 |
6 | 5 | 8 | 6 | 9 | 7 | 2 | 0 | 1 | 3 | 4 |
7 | 8 | 9 | 4 | 5 | 3 | 6 | 2 | 0 | 1 | 7 |
8 | 9 | 4 | 3 | 8 | 6 | 1 | 7 | 2 | 0 | 9 |
9 | 2 | 5 | 8 | 1 | 4 | 3 | 6 | 7 | 9 | 0 |
For instance, given the input 572, the check digit is 4 and the output is 5724. The check digit is computed starting with 0, then row 0 and column 5 gives a new check digit of 9, row 9 and column 7 gives a new check digit of 7, and row 7 and column 2 gives a final check digit of 4. Notice that leading zeroes do not affect the check digit.
Checking goes the same way, and is successful if the final check digit is 0. Given the input 5724, the initial check digit is 0, then row 0 and column 5 gives a new check digit of 9, row 9 and column 7 gives a new check digit of 7, row 7 and column 2 gives a new check digit of 4, and row 4 and column 4 gives a final check digit of 0.
Your task is to write functions that add a check digit to a number and validate a number to which a check digit has been added. 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.
Dawkins’ Weasel
November 14, 2014
In his book The Blind Watchmaker, Richard Dawkins says:
I don’t know who it was first pointed out that, given enough time, a monkey bashing away at random on a typewriter could produce all the works of Shakespeare. The operative phrase is, of course, given enough time. Let us limit the task facing our monkey somewhat. Suppose that he has to produce, not the complete works of Shakespeare but just the short sentence ‘Methinks it is like a weasel’, and we shall make it relatively easy by giving him a typewriter with a restricted keyboard, one with just the 26 (capital) letters, and a space bar. How long will he take to write this one little sentence?
(All of our quotes are shamelessly stolen from Wikipedia.) Then Dawkins suggests that this is a bad analogy for evolution, and proposes this alternative:
We again use our computer monkey, but with a crucial difference in its program. It again begins by choosing a random sequence of 28 letters, just as before … it duplicates it repeatedly, but with a certain chance of random error – ‘mutation’ – in the copying. The computer examines the mutant nonsense phrases, the ‘progeny’ of the original phrase, and chooses the one which, however slightly, most resembles the target phrase, METHINKS IT IS LIKE A WEASEL.
Then he discusses a computer program that simulates his monkey, which he says took half an hour to run because it was written BASIC; when he rewrote his program in Pascal the runtime dropped to eleven seconds. His program used this algorithm:
- Start with a random string of 28 characters.
- Make 100 copies of the string (reproduce).
- For each character in each of the 100 copies, with a probability of 5%, replace (mutate) the character with a new random character.
- Compare each new string with the target string “METHINKS IT IS LIKE A WEASEL”, and give each a score (the number of letters in the string that are correct and in the correct position).
- If any of the new strings has a perfect score (28), halt. Otherwise, take the highest scoring string, and go to step 2.
Your task is to write a program to simulate Dawkins’ monkey. 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.
Favorite Color
November 11, 2014
A text file consists of records with fields. Each field is a name/value record of the form name: value
with the field name followed by a colon, a space, and the value. Records consist of one or more fields separated by a blank line. In a particular database one field is named favoritecolor
.
Your task is to write a program that determines the maximal favorite color; in other words, what color is named the most times as the favorite color. 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.
Gaussian Integers, Part 2
November 7, 2014
We continue today with our study of Gaussian integers.
The greatest common divisor of two Gaussian integers is computed by Euclid’s algorithm: repeatedly replace dividend and divisor with divisor and remainder until the divisor is zero, at which point the dividend is the greatest common divisor. One Gaussian integer divides another if the remainder is zero, and two Gaussian integers are co-prime if their greatest common divisor is one of the four units.
If a Gaussian integer is not a unit, it is either prime or composite. A Gaussian integer a + b i is prime if either a or b is zero and the other is a prime congruent to 3 (modulo 4), or if both a and b are non-zero and the norm is prime.
If a Gaussian integer is composite, it can be factored by the following algorithm described by Jim Lewis: Factor the norm. For each norm factor of 2, add a factor 1 + i to the list of output factors. For each two norm factors p that is congruent to 3 (modulo 4), add a factor p + 0 i to the list of output factors. Otherwise, norm factor p is congruent to 1 (modulo 4): find k such that k ^{2} = −1 (mod p), then add gcd(p, k + i) to the list of output factors. After considering all the norm factors, the original Gaussian integer divided by all the output factors will be a unit; if it is 1, then you are finished, otherwise add to the list of output factors the unit that remains after the division. To find k, choose some integer n between 2 and p −1, inclusive; if n ^{(p −1)/2} = −1, which will be true about half the time, then k = n ^{(p −1)/4}.
Your task is to write functions for greatest common divisor, identifying primes, and factoring composites for Gaussian integers. 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.
Gaussian Integers, Part 1
November 4, 2014
Gaussian integers are complex numbers of the form a + b i where both a and b are integers. They obey the normal laws of algebra for addition, subtraction and multiplication. Division works, too, but is a little bit complicated:
Addition: (a + b i) + (x + y i) = (a + x) + (b + y) i.
Subtraction: add the negative: (a + b i) − (x + y i) = (a − x) + (b − y) i.
Multiplication: cross-multiply, with i ^{2} = −1: (a + b i) × (x + y i) = (a x − b y) + (a y + b x) i.
Quotient: multiply by the conjugate of the divisor, then round: (a + b i) ÷ (x + y i) = ⌊(a x + b y) / n⌉ + ⌊(b x − a y) / n⌉ i, where n = x ^{2} + y ^{2}.
Remainder: compute the quotient, then subtract quotient times divisor from dividend.
Your task is to write a small library of functions for operating on Gaussian integers. 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.
Belphegor Primes
October 31, 2014
Belphegor is one of the Seven Princes of Hell, charged with helping people make ingenious inventions and discoveries. Simon Singh gave the name Belphegor’s Prime to the number 1000000000000066600000000000001, which is the Number of the Beast, 666, from the Apocalypse, surrounded on each side by an unlucky 13 zeroes. Generally, Belphegor numbers B_{n} = (10^(n+3) + 666)*10^(n+1) + 1 have a 1, followed by n zeroes, followed by 666, followed by n zeroes, followed by 1. There are eight known Belphegor primes, with n ∈ {0, 13, 42, 506, 608, 2472, 2623, 28291} (A232448). You can read more about Belphegor primes at Cliff Pickover’s page.
Your task is to write a program that enumerates the Belphegor primes. 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.
Number Of Divisors In A Range
October 28, 2014
We have today an interview question that was posted to the internet by a candidate who didn’t get the job, and wondered what he had done wrong. I’ll paraphrase his question:
The interview question was to find the number of integers between x and y that are divisible by n; you may assume that x, y and n are all positive and that x < y. I know the simple way to solve this is to loop over the range from x to y, like this:
for(int i=x;i<=y;i++) if(i%n ==0) counter++;
but that is very slow when the range is large, for instance x = 0 and y = 3000000000.
There must be some method that lets me reduce the number of iterations and optimize the code. Can someone please help me with that?
Your task is to help the candidate get the job by proposing a better algorithm to solve the problem. 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.