Learning Journal #2: Puzzles, pt. 1

Rivers and Primes

I enjoy puzzles, particularly logic puzzles. Riddles typically rely on some kind of clever linguistic trick as their core conceit, but logic puzzles lay out all of the information you need from the outset. They provide the tools and the destination, and it’s up to you to take the journey. Here’s one of my favorites:

A farmer is trying to transport a wolf, a goat, and a basket of cabbage across a river. They can only carry one item at a time in their boat. If the wolf and the goat are left alone, the wolf will eat the goat. If the goat and the cabbages are left alone, the goat will eat the cabbages. How can the farmer get all three items across the river?

If this is your first exposure to this puzzle, I’ll leave you to think it through until the end of this article; puzzles are no fun if you just skip straight to the solution. Here’s another:

How can we determine whether or not a number is prime?

You might notice we’ve switched domains fairly radically from rivers and hungry animals to the far more stoic world of numbers. I’d argue that this jump is less significant than the jump from a specific problem to an open-ended one. The river puzzle has one elegant solution, but the problem of determining primality is broad enough to have its own area of study.

Let’s narrow our puzzle down so it’s better-suited for our purpose:

How can we write a program that determines whether or not a number is prime?

That leaves us with one burning question to settle:

“What’s a Prime Number, Anyway?”

Intuitively, most have a visual sense for whether a given quantity is even or odd; if you can pair all of the units up, it’s even; if you have leftovers, it’s odd.

Odd numbers always have a unit left over after being paired up

As you learned arithmetic beyond addition and subtraction, this pairing — and more broadly speaking, grouping — got a name: division. Along with this came the introduction of divisibility, the capacity for a quantity to be broken into groups without leftovers (also called remainders). We say that 12 is divisible by 3 because we can split 12 into groups of 3 (4 groups, specifically) without any remainder. In this new language, we say that a number is even if it’s divisible by 2 and odd if it isn’t.

After becoming comfortable with even and odd numbers, you were likely taught about a new pair of categories, prime and composite. With this pair comes the idea of a factor. A factor is any whole number which divides another whole number; the fact that 12 is divisible by 3 is the same as saying 3 divides 12, so we say that 3 is a factor of 12. Another view I tend to gravitate towards is that factors are the building blocks of whole numbers.

Any whole number can be broken down into factors; 12, for instance, can be broken down into the factors 1, 2, 3, 4, 6, and 12, since those are all of the numbers which divide it. Certain building blocks are more intriguing than others; 1 divides every number, and every number divides itself, so these two aren’t of much interest when breaking a number down. What are interesting, however, are those numbers which can’t be broken down into any factors other than those.

Ignoring the factors 1 and 18, 18 can be broken up until it we hit the factors 2 and 3; these are 18’s prime factors.

We give a special designation to these numerical atoms: prime. Composite numbers, conversely, can be broken into factors other than 1 and the numbers themselves. These may seem removed from the relatively simple conditions of even and odd numbers, but they’re really an extension of them: where even and odd numbers are defined by their divisibility by a single number (namely 2), prime and composite numbers are defined by their divisibility by a class of numbers (the primes).

Finding Building Blocks

Back to the puzzle at hand: now that we have some idea of what a prime is, how can we tell when we’re dealing with one? For small primes, we might have a more intuitive sense of their primality or compositeness: it’s readily apparent that 7 has no factors other and 1 and 7, and 8 can clearly be broken into the factors 4 and 2, but it’s not so clear that a large number like 527 = 17 × 31 on first glance. We need something more systematic than an eyeball test.

A naïve approach might be to make a function isPrime that tests our target number’s divisibility sequentially and exhaustively, excluding 1 and the number itself. In code, this would look like

function isPrime(number) {
  for (let i = 2; i < number; i++) {
    if (number % i == 0) { return false; }
  }
  return true;
}

Here’s the breakdown: let i = 2; i < number sets the boundaries for our testing, excluding 1 and number from the list. The bit number % i == 0 is where the divisibility test occurs; the % is what’s called a modulo operator, and it returns remainders. If dividing number by i leaves a remainder of 0, we know number must be composite, or not prime.

You can try testing this function on a few numbers below. I’ve added a line to print to the console each number that’s been tested. After pressing the green [▶ Run] button, try entering the following into the console and take a look at the output:

>isPrime(9)
>isPrime(25)
>isPrime(13)

Brute force approach to primality testing

You might have noticed that the first two outputs seem a little different from the third; 9 and 25 are composite numbers, and their search stopped after 3 and 5 steps respectively, but 13, a prime number, took 12 whole steps to test. For smaller primes, these extra steps are trivial, this approach has a glaring issue: it doesn’t scale well. Our current algorithm stops fairly early for composites, but when it’s testing a prime, it has to go through every number up to that prime. We can do better, and in the next post, we will!