M4 Macros
January 30, 2015
I’ve always had a love/hate relationship with m4 macros. For programming languages that don’t offer macros, or have only a limited form of macros (like C), m4 can be a godsend. Used to their fullest potential, m4 macros enable programmers to write programs that write programs, which can lead to extremely high productivity. And m4 macros aren’t limited to use in programming; I used m4 macros recently when writing my security camera essay (which is what inspired me to write this exercise).
If you’re interested in learning about m4, the original tutorial by Brian Kernighan and Dennis Ritchie is a fine introduction for casual use, the manual for Gnu m4 is complete and definitive, and this short essay by Ken Turner is a little bit insane.
Your task is to use m4 to write some program or transform some text; the purpose is to introduce you to m4 (or re-introduce you if it’s been a long time since your last use), so any task will do. 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.
Sum Of Four Primes
January 27, 2015
Today’s exercise comes from one of those competitive programming websites. I never participate in the coding frenzy at those sites, because the competitiveness at extracting every last millisecond from the run time or deleting every unneeded character from the program text ruins the pleasure, but some of the problems are fun:
Given a positive integer 7 < n ≤ 10000000, find four prime numbers with sum n. For instance, 46 = 11 + 11 + 17 + 7.
Your task is to write a program to find four primes that sum to n. 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.
Fibonacci Conjecture
January 23, 2015
The sequence of Fibonacci numbers is defined as F0 = 0, F1 = 1, Fn = Fn−2 + Fn−1. It has been conjectured that for any Fibonacci number F, F2 + 41 is composite.
Your task is to either prove the conjecture to be true or find a counter-example that demonstrates it is false (hint: this is not a blog about proving math theorems). 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.
Largest Forward Difference
January 20, 2015
In an array of integers, the forward difference between any two elements is the rightmost integer less the leftmost integer. The largest forward difference is the greatest value of all forward differences between elements of the array. If there are no positive forward differences, the largest forward difference is taken to be zero, as if an integer is subtracted from itself.
For instance, in the array [1,5,7,2,9] the largest forward difference is 9 – 1 = 8, and in the array [4, 3, 2, 1] the largest forward difference is 0.
Your task is to write a program that finds the largest forward difference in an array. 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.
Gödel Numbering
January 16, 2015
Gödel numbering is a system that assigns a natural number to each symbol and expression in a logical system, invented in 1931 by Kurt Gödel for the proofs of his incompleteness theorems. Consider the logical system where symbols are letters and expressions are words; for instance, the word PRAXIS consists of six symbols P, R, A, X, I, and S. Gödel numbering would assign numbers to the letters, say A=1 … Z=26, then assign each letter as the exponent of the next prime, so PRAXIS would be numbered 216 × 318 × 51 × 724 × 119 × 1319 =
83838469305478699942290773046821079668485703984645720358854000640
The process is reversible; factor the Gödel number and decode the exponents.
Your task is to write functions that encode strings as Gödel numbers and decode Gödel numbers as strings. 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.
Essay: Building A Security Camera With A Raspberry Pi
January 13, 2015
We have today our fourth essay: Building a Security Camera with a Raspberry Pi. 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.
My daughter recently had a thief enter her apartment and steal her laptop computer. Later, when I asked her what she wanted for Christmas, her answer was immediate: a security camera, so in case she is robbed again she will have pictures of the thief to give to the police. But commercial security cameras are expensive, often several hundred dollars, and many are tied to security services with expensive monthly fees, which she wasn’t interested in paying. So I built a security camera using a Raspberry Pi, and wrote this essay describing how I did it.
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.
One-Time Pad
January 9, 2015
In a previous exercise Ben Simon showed us how to use a trigraph for secret communication. For illustration, he used a one-time pad based on a simple random number generator, but that is not sufficient for proper cryptographic secrecy. In today’s exercise we build a secure one-time pad.
We need two things. One is a cryptographically-secure source of random bits. Solutions include counting the clicks of a geiger counter or reading the background radiation, but being a software guy rather than a hardware guy I suggest the Blum-Blum-Shub cryptographically-secure random number generator of a previous exercise. The second is a way to convert bits to letters. The method we choose is to take 26 consecutive bits from the Blub-Blub-Shum generator, form them into a number, and take the result mod 26, discarding the four largest numbers from the set in order to make all letters equally likely to be chosen, which is similar to the calculation of a previous exercise. Given those two things, it is easy to generate random letters and build a pad of any desired size.
Your task is to write a program to generate one-time pads. 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.
Lucas-Carmichael Numbers
January 6, 2015
We start the new year with a simple task from number theory. A Lucas-Carmichael number is a positive composite integer n, odd and square-free, such that p + 1 divides n + 1 for all prime factors p of n. For instance, 2015 is a Lucas-Carmichael number because 2015 = 5 × 13 × 31 and 5 + 1 = 6, 13 + 1 = 14, and 31 + 2 = 32 all divide 2015 + 1 = 2016. The restriction that n be square-free prevents the cubes of prime numbers, such as 8 or 27, from being considered as Lucas-Carmichael numbers.
Your task is to write a program to find all the Lucas-Carmichael numbers less than a million. 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.
Programming Praxis 