Euler #5: Smallest Multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Woo-hoo! Another problem that can be solved entirely on paper without any pesky coding!

The solution uses what I call “base-prime”. In our decimal system we know and love, the place values are 1, 10, 100, and so on. In binary, they’re the powers of 2. In base-prime, the place values are the primes. It’s a compact representation of a number’s prime factorization.

For example, let’s take the prime factorization of 210. It is 7^1 \times 5^1 \times 3^1 \times 2^1. The base-prime representation of 210 would be 1111. Another example: 1400. It has the prime factors 7^1 \times 5^2 \times 3^0 \times 2^3. In base-prime, 1400 becomes 1203.

This system does run into some problems with digit symbols once we go beyond primes raised to the 9th power. Fixes include borrowing from hexadecimal or using commas to separate places.

Now comes the cool part. Represent all numbers from 1 to 20 in base-prime and align them like we would for an addition problem.

Base prime representations of the numbers 2-20

Now, in each column, take the highest number and write it below. This creates a new base-prime number: 11111124. Convert it back to boring ol’ base-10. Bam! That’s the answer. Let’s see…11111124=19\times17\times13\times11\times7\times5\times3^2\times2^4=232792560.