Almost Primes

April 19, 2019

Today’s exercise was inspired by a task at Rosetta Code:

An integer n > 1 is a k-almost-prime if it is the product of k primes. Further, a k-almost prime is squarefree if all k primes are distinct.

You can learn more about k-almost-primes and their uses in number theory at Wikipedia or MathWorld.

Your task is to write programs that calculate the first ten k-almost-primes and squarefree k-almost-primes for 1 ≤ k ≤ 5. 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.

Advertisements

Pages: 1 2

The Last Prime Digit

April 16, 2019

Over at NumberPhile, Dr Grimes (can you look at him and not smile?) discusses the pattern in the last digits of successive prime numbers. It’s not what you think.

Your task is to write a program that mimics the calculations made by Dr Grimes. 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

Here are three simple math problems. They are intended to be solved analytically, with number theory, without using a computer or a calculator. But I cheated. All three problems come from the YouTube channel Mind Your Decisions, where you will find lots of similar problems.

  1. Solve for x and y where both are integers: 615 + x2 = 2y
  2. Find a three-digit number abc = 100a + 10b + c with none of the digits 0 such that abc = a! + b! + c!
  3. Find a three-digit number pie = 100p + 10i + e with none of the digits 0 such that √pi + e = √ pie

Your task is to solve the three problems; you can write programs to solve them, if you wish, but it is fun to solve them by hand. When you are finished, you are welcome to or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Grep-CSV

April 9, 2019

Regular readers of this blog know that. in my day job, I frequently process input files from vendors; almost always, they were created in Excel and arrive in CSV format. Sometimes I have to peek inside the files, looking for invalid data, and I have commonly used grep for that task. Sometimes grep gives me unwanted records, because there is a match in some field that is not the field of interested, and I just ignore the extra records. But the other day I had a mess, with lots of unwanted records, so I used awk to parse out the fields and find the records of interest.

I realized as I was performing that task that it would be useful to have a version of grep that understood the CSV file format. So I wrote grep-csv that takes a field number (counting from 1, like awk) and a regular expression and returns the matching rows of a CSV file.

Your task is to write a grep-csv 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.

Pages: 1 2

Destructuring-Bind

April 5, 2019

We implemented Chris Okasaki’s physicist’s queues in the previous exercise. As I implemented them in Scheme, I struggled to maintain Okasaki’s clear, consise coding style, which relies heavily on pattern matching. There are several pattern-matching libraries available for Scheme, but they are rather heavy (the one I use, by Friedman, Hilsdale and Dybvig, is over six hundred lines of code). Our Standard Prelude has a simple pattern matcher, but it doesn’t fit properly with a simple binding. I finally came up with a strange method using let-values ... apply values that makes the code concise at the cost of forcing readers to think through an uncommon idiom. What I wanted was something similar to the destructuring-bind macro of Common Lisp.

So I wrote one.

Your task is to write a macro similar to the destructuring-bind macro of Common Lisp and add it to your favorite programming 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.

Pages: 1 2

One of my favorite programming textbooks is Chris Okasaki’s Purely Functional Data Structures, which I pick up and re-read every year or so. Today’s exercise asks you to
implement Okasaki’s physicist’s queues, which you can read about in either his book (Figure 6.3 on page 73) or his thesis (Figure 3.4 on page 31). Queues provide two constructors empty and snoc, two accessors head and tail, and a single predicate isEmpty; it is an error if either head or tail are applied to an empty queue. This version comes from the book:

structure PhysicistsQueue : QUEUE
struct
    type alpha Queue = α list × int × α list susp × int × α list

    val empty = ([], 0, $[], 0, [])
    fun isEmpty (_, lenf, _, _, _) = (lenf = 0)

    fun checkw ([], lenf, f, lenr, r) = (force f, lenf, f, lenr, r)
      | checkw q = q
    fun check (q as (w, lenf, f, lenr, r)) =
        if lenr < lenf then checkw q
        else let val f' = force f
             in  checkw (f', lenf + lenr, $(f' @ rev r), 0, []) end

    fun snoc ((w, lenf, f, lenr, r), x) =
        check (w, lenf, f, lenr + 1, x :: r)

    fun head ([], lenf, f, lenr, r) = raise EMPTY
      | head (x :: w, lenf, f, lenr, r) = x
    fun tail ([], lenf, f, lenr, r) = raise EMPTY
      | tail (x :: w, lenf, f, lenr, r) =
            check (w, lenf - 1, $tl (force f), lenr, r)
end

Your task is to implement Okasaki’s physicists queues. 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