Sieving A Polynomial
May 30, 2017
I watch Stack Overflow and Reddit for questions about prime numbers. Most of the questions are basic, many are confused, a few are interesting, and some are just bizarre. A recent question falls in the latter category:
I need to make a list of the prime factors with multiplicity of all the numbers up to 300,001 that are equivalent to 1 modulo 4. My strategy is to make a list of the numbers 1 modulo 4, then calculate the factors of each. I don’t know how to calculate factors, but I know it’s complicated, so I figure somebody has already built a factoring program and put it on the web. Does anybody know a web API that I can call to determine the factors of a number?
For instance, if we limit the numbers to 50, the desired output is:
5 (5) 9 (3 3) 13 (13) 17 (17) 21 (3 7) 25 (5 5) 29 (29) 33 (3 11) 37 (37) 41 (41) 45 (3 3 5) 49 (7 7)
Calling a web API 75,000 times is a spectacularly wrong way to build the list, but I pointed the questioner to Wolfram|Alpha. Long-time readers of this blog know how to solve the problem directly, which we will do in today’s exercise.
Your task is to write a program to factor all the numbers up to 300,001 that are equivalent to 1 modulo 4. 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.
Hill Cipher
May 26, 2017
The Hill Cipher was invented by Lester Hill in 1929. A block cipher based on modular matrix multiplication, it was rather advanced for its time. The diffusion inherent in the algorithm makes it difficult to break manually, though it is easy to work back to the key if you have some known plaintext.
The Hill Cipher uses arithmetic, so you will need to convert the alphabetic plaintext to numbers using a polybius square, a straddling checkboard, or the simple expedient of mapping A to 0, B to 1, and so on, until Z is 25, which we will adopt here. Our alphabet has 26 characters, which can be a problem since 26 = 2 × 13 is composite; the alphabet size becomes the modulus of the cipher system, and some keys won’t work, though it is easy to find keys that do. If you’re worried, add characters to the alphabet until it has a prime number of elements; for instance, you might choose a 29-character alphabet with the letters A to Z, a space character, a period, and a slash for a digit shift.
Let’s look at an example. We will send the message PROGRAMMINGPRAXIS with blocksize 3. The plaintext is padded with a Z, forming a 6 × 3 matrix:
P R O 15 17 14
G R A 6 17 0
P = M M I = 12 12 8
N G P 13 6 15
R A X 17 0 23
I S Z 8 18 25
We must choose a key that is invertible; that is, a key that has an inverse (some textbooks call such keys non-singular). For a normal matrix to be invertible, the discriminant must be non-zero. Since we are using modular arithmetic instead of normal integer arithmetic, we have the additional requirement that the determinant and modulus must be coprime. If the first key you choose doesn’t work, try another. The key that we choose, and its mod 26 inverse, are:
G Y B 6 24 1 8 5 10 I F K
K = N Q K = 13 16 10 inverse = 21 8 21 = V I V
U R P 20 17 15 21 12 8 V M I
Encryption is performed by modular matrix multiplication, with C = P × K (mod 26):
15 17 14 19 12 5 T M F
6 17 0 6 24 1 23 0 23 X A U
C = 12 12 8 * 13 16 10 = 24 18 18 = Y S S
13 6 15 20 17 15 14 13 12 O N M
17 0 23 16 19 24 Q T Y
8 18 25 2 21 17 C V R
So the ciphertext is TMFXAUYSSONMQTYCVR.
Decryption is also performed by modular matrix multiplication, with P = C × Kinv (mod 26):
19 12 5 15 17 14 P R O
23 0 23 8 5 10 6 17 0 G R A
P = 24 18 18 * 21 8 21 = 12 12 8 = M M I
14 13 12 21 12 8 13 6 15 N G P
16 19 24 17 0 23 R A X
2 21 17 8 18 25 I S Z
Your task is to write a program that performs encryption and decryption using the Hill Cipher. 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.
Matrix Determinant And Inverse
May 23, 2017
Today’s exercise is preliminary to the exercise we will have later this week. You are to write programs that calculate the determinant and inverse of a matrix. I won’t go into the math involved behind the matrix arithmetic, as there are many sources on the internet that know far more about the process than I. Google for “matrix determinant” or “matrix inverse”; I used YouTube for my instruction.
Your task is to write programs that calculate the determinant and inverse of a matrix. 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.
Just Showing Off
May 19, 2017
As I have mentioned on several previous occasions, I frequently receive email from students asking for homework help, which I routinely ignore. Less frequently, I receive email from someone who tells me that Scheme is a horrible programming language, they don’t understand it, it is unreadable, there are too many parentheses, blah, blah, blah, and wouldn’t it be better if I wrote my blog in C#. (I don’t know what’s wrong with C# people, but I get more of them than any other language zealots.) Usually I ignore them, too, but the other day I engaged one of those correspondents who singled out macros as a particular wart on the face of Scheme. So I wrote to him and gave him this macro, which I used to calculate fibonacci numbers; the whole story is on the next page:
(define-syntax define-memoized
(syntax-rules ()
((define-memoized (f arg ...) body ...)
(define f
(let ((cache (list)))
(lambda (arg ...)
(cond ((assoc `(,arg ...) cache) => cdr)
(else (let ((val (begin body ...)))
(set! cache (cons (cons `(,arg ...) val) cache))
val)))))))))
When I showed him how to speed up the calculation of fibonacci numbers by memoizing sub-computations, he grudgingly agreed there might be something there, but it wouldn’t translate to C# (I didn’t disagree with that comment).
Your task is to write a program that shows off some special feature of your favorite programming language; tell the story how it makes your language better than any others, and give a real-life example. 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.
License Plates
May 16, 2017
A license plate number has form ABC-123, three letters followed by three digits. You are to store the set of license plate numbers, assume you will have about a hundred thousand of them, and be able to answer queries like:
* Is license plate PLB-123 a member of the set?
* How many license plates begin with the letters PLB?
* What is the list of license plates that begin with the letters PLB?
Your task is to write programs to store and query a list of license plate numbers. 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.
Division By Repeated Subtraction
May 12, 2017
I traded several emails this week with a programming student who was having trouble with this assignment:
Write a function that divides two numbers and returns their quotient. Use recursive subtraction to find the quotient.
The student went on to explain that he thought he needed to use a counter variable that he incremented each time the function recurred, but he didn’t know how to do that because the function could only take two arguments; it had to be of the form (define (divide a b) ...).
Your task is to write the function, and explain to the student how it works. 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.
Distinct Characters
May 9, 2017
We’ve done similar exercises in the past:
Write a program to determine if all the characters in a string are distinct. For instance, the word “Programming” has two m and two g, so all the characters are not distinct, but the word “Praxis” has six distinct characters.
Your task is to write a program to determine if all the characters in a string are distinct; you should provide three solutions, one that takes time O(n²), one that takes time O(n log n), and one that takes time O(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.
Calculating Derivatives
May 5, 2017
I’ve seen this before, and when I ran across it again a few days ago decided to share it with all of you. This is why I like Scheme so much:
In mathematics, the derivative of a function f(x) is 
Petite Chez Scheme Version 8.4
Copyright (c) 1985-2011 Cadence Research Systems
> (define dx 0.0000001)
> (define (deriv f)
(define (f-prime x)
(/ (- (f (+ x dx)) (f x))
dx))
f-prime)
> (define (cube x) (* x x x))
> ((deriv cube) 2)
12.000000584322379
> ((deriv cube) 3)
27.000000848431682
> ((deriv cube) 4)
48.00000141358396
Those results are reasonably close to the actual derivative of 
Your task is to write a function to calculate derivatives in your favorite language. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution in the comments below.
Base Conversion
May 2, 2017
I continue cleaning out my list of saved homework questions:
Given a number represented as a string in base 2, convert the number to a string in base 4. For instance, the number 110110002 = 31204.
Your task is to write a program that converts numbers from base 2 to base 4; for extra credit, write a program that converts from any base to another. 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 