Crunching numbers: Algorithms I wrote for Project Euler🧮💻

At some point a few years ago, I discovered Project Euler. Every now and then I get back to it and try to solve the next few problems and forget about it again. I have a repository with most solutions written in plain ol' JavaScript.

The header image is related: It's Mr. Leonard Euler, a Swiss mathematician. Project Euler is named after him.

Project What?

Project Euler is a massive collection of mathematics problems that get harder and harder, the further you progress. As of today, there's 750 problems, and new ones get added every so often. Most of them are solvable with programming and decently designed algorithms.

As an example, let's have a look at the first problem:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Sounds doable with a for-loop, right? It is, but that's another story.

Divide into smaller problems

A strategy that I apply to everyday software tasks is dividing a problem into smaller problems and trying to solve each and every one of those to get closer to a solution of the original problem.

This strategy pays off on Project Euler, too: The problem I mentioned above could for example be solved by first writing a function that checks of a number is a multiple of 3 or 5 and calling this function in a for-loop.

At some point I started to encounter the same sub-problems and steps in various problems and decided to start writing those out as their own functions in order to reuse them. No need to reinvent the wheel over and over again, right?

Let me show you some of the gems:

The stuff I wrote for Project Euler

n!

Ok, let's start with an all-time classic: Factorials! A perfect example for recursive functions. A factorial is basically short for a multiplication of all natural numbers before and the number itself. For example, 5! = 5 * 4 * 3 * 2 * 1 = 120

The function itself is rather simple in terms of code:

const factorial = n => {
  if (n === 0) {
    return 1
  }

  return n * factorial(n - 1)
}

And here we see the classic pattern of recursion: The function is calling itself as long as n is larger than 0. It leverages the fact that n! = n * (n-1)!

What do 2, 3, 5, 7, 13 have in common?

Right, they're prime! But what about 7319? Well, let's check using a simplistic approach: Divide it by every number up to 7319, until there's a divisor. But wait, that's too much. I only need to check the first sqrt(7319) numbers, right? After all, 2 * 50 === 50 * 2, so there's no need to check everything twice.

Let's code that:

const isPrime = n => {
  for (let i = 2; i * i <= n; i++) {
    if (n % i === 0) {
      return false
    }
  }

  return true
}

There's some optimization potential, I know, but since the scripts I write usually run for a minute or two anyways, there's not much optimization necessary.

What's so special about a taco cat?

Matthew Inman, creator of "The Oatmeal", is famously using the word taco cat in many of his works. Taco cat is a plaindrome, a word that is the same backwards and forwards. Constructing such a number is also straight forward: 12321 is a number palindrome. A way to check if a given string is a palindrome is to reverse the string and see if it's the same:

const isPalindrome = (str) => {
  const lc = str.toString().toLowerCase()
  return lc === lc.split('').reverse().join('')
}

This little function also works with numbers!

Use all the digits!

But only once. A number that does that is called a pandigital number. The most straight-forward example being 1234567890. So, how can we check if a number uses all the digits, but only once? A simplistic approach would be to sort the digits and compare:

const isPandigital = (nr, includeZero) => {
  return nr.toString()
    .split('')
    .sort()
    .join('') === (includeZero ? '0123456789' : '123456789')
}

Some additional checks beforehand might be helpful, though. A pandigital number not only uses all the digits once, but it always has 9 (or 10, if 0 is included) digits.

Last but not least: What's 2 * 3 * 5 * 7 * 13?

That's 2730. But those are not the only numbers 2730 can be divided by (10 works, 273, works too), but its prime factors. Each and every number is made up of so called prime factors. If it's not, then it's prime itself. And prime factors are, well, prime. How can we find the prime factors of any number? We can try to find them by increasing the number we try to divide the current number with.

We start with 2 as a potential prime factor. Is 2730 dividable by 2? Yes! So, let's do just that: 2730 / 2 = 1365. Is 1365 dividable by 2? No. Let's try 3: 1365 / 3 = 455, so 3 is also a prime factor. Is 455 dividable by 3? No, so let's try 4, which also won't work. The next number is 5, and indeed: 455 / 5 = 91, and so on. And that's the code for it:

const getPrimeFactors = n => {
  const factors = []
  let divisor = 2

  while (n >= 2) {
    if (n % divisor === 0) {
      factors.push(divisor)
      n = n / divisor
    } else {
      divisor++
    }
  }

  return factors
}

Not the most efficient solution, but it works, nevertheless.

Takeaway thoughts

I love Project Euler. It makes me think outside the box and makes me think about problems I likely never encounter in my day-to-day job.

I'm sure there's a lot of potential improvements that can be done to these little functions, but they do the job: Providing a solution for the piece of a larger problem.

---

I hope you enjoyed reading this article as much as I enjoyed writing it! If so, leave a ❤️ or a 🦄! I write tech articles in my free time and like to drink coffee every once in a while.

If you want to support my efforts, buy me a coffee ☕ or follow me on Twitter 🐦! You can also support me directly via Paypal!