Project Euler - Problem 15 - Solution Explained

Lattice paths

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

The Permutation Solution (Brute Force)

This problem states that the only two directions we can travel, starting from the origin, are right and down. If we were to transcribe the traversal in plain english, the six paths that we can travel in a 2 x 2 grid are as follows:

1. Right, Right, Down, Down
2. Right, Down, Right, Down
3. Right, Down, Down, Right
4. Down, Right, Right, Down
5. Down, Right, Down, Right
6. Down, Down, Right, Right

There are a few observations we can make about the transcribed lists above:

• Every list has $2$ down turns and $2$ right turns.
• Every list has $2+2$ items total.
• No two lists are repeated exactly. The primary difference between them is the order in which the turns appear.

We can generalize our observations to state: To determine the number of paths in any $g\times g$ grid, we need only to find the number of distinct permutations of a list that has a total of $2g$ items, contains $g$ right turns, and contains $g$ down turns

The intuition behind the algorithm I used to find all of the permutations can be found here. In fact, the function I use in this solution named nextPermutation is borrowed from the same source.

In the solution below, we are manually constructing an array of "rights" and "downs." Than we are manually permuting the list in lexicographical order while we increment a counter. After we run through all distinct permutations, the counter is then logged to the console.

DISCLAIMER: If you actually try to run the code, it will take a very, very long time to reach the solution. I recommend altering the gridSize variable to 4, it will log 70 to the console (which is the correct answer).

const gridSize = 20;
const route = [];
let count = 0;

/**
 * Permutes array in lexicographical order.
 * @param {number[]}
 * @returns {boolean} If false, no other permutations remain.
 * @author Project Nayuki
 * @see https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
 */
function nextPermutation(array) {
 // Find non-increasing suffix
 var i = array.length - 1;
 while (i > 0 && array[i - 1] >= array[i])
  i--;
 if (i <= 0)
  return false;
 
 // Find successor to pivot
 var j = array.length - 1;
 while (array[j] <= array[i - 1])
  j--;
 var temp = array[i - 1];
 array[i - 1] = array[j];
 array[j] = temp;
 
 // Reverse suffix
 j = array.length - 1;
 while (i < j) {
  temp = array[i];
  array[i] = array[j];
  array[j] = temp;
  i++;
  j--;
 }
 return true;
}

for (let i = 0; i < gridSize; i += 1) {
  route.push(0); // 0 represents "right."
}

for (let i = 0; i < gridSize; i += 1) {
  route.push(1); // 1 represents "down."
}

count += 1;

while(nextPermutation(route)) {
  count += 1;
}

console.log(count);

It should be clear to everyone, by running the code above, that the permutation approach is not the correct answer. There is, however, a way to solve this problem by analyzing it mathematically.

The Combination Math Solution

If we start to think in terms of 'combination' instead of 'permutation', a mathematical solution opens itself to us. The following (binomial coefficient) equation can help us:

$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$

The intuition behind the equation can be gleamed here:

Let's think again, about the transcribed list of routes of a 2 x 2 grid (in the previous section).

If we began with an empty list with 4 empty slots:

<empty>, <empty>, <empty>, <empty>

Let's ask ourselves, "How many ways can we insert 2 right turns into such a list?" The answer happens to be 6. You can insert them in the following ways:

1. Right, Right, <empty>, <empty>
2. Right, <empty>, Right, <empty>
3. Right, <empty>, <empty>, Right
4. <empty>, Right, Right, <empty>
5. <empty>, Right, <empty>, Right
6. <empty>, <empty>, Right, Right

Notice how this looks a lot like the lists in the previous section. We can omit the down turns and still arrive at the correct answer because we can assume the remaining empty slots represent down turns. This means we need to choose 2 slots out of 4 possible options; in other words, $k = 2$ and $n = 4$. Let's apply our understanding to the binomial coefficient equation:

$$\binom{4}{2} = \frac{4!}{2!(4-2)!} = \frac{4\cdot 3\cdot 2\cdot 1}{2\cdot 1\cdot (2\cdot 1)} = \frac{\not 4\cdot 3\cdot 2\cdot 1}{\not 4} = 6$$

We can generalize this example to assume that $k = g$ and $n = 2g$. We should also process the binomial coefficient equation in such a way that it can be coded efficiently. We can use the Multiplicative formula (Note: The $\underline{k}$ exponent in the numerator of the first expression is a falling factorial):

$$\binom {n}{k} = \frac{n^{\underline{k}}}{k!} = \frac{n(n-1)(n-2)\cdots (n-(k-1))}{k(k-1)(k-2)\cdots 1}=\prod_{i=1}^k \frac{n+1-i}{i}$$

We can implement the above solution, like so:

const gridSize = 20;

function choose(n, k){
  let product = 1;
  for (let i = 1; i <= k; i += 1) {
    product *= (n + 1 - i) / i;
  }
  return product;
}

console.log(choose(2 * gridSize, gridSize));

Project Euler - Problem 14 - Solution Explained

Longest Collatz sequence
The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

The Naive Approach

The first thought I had when I read this problem was "This is easy." Of course, I could easily use the brute force solution:

const limit = 1000000;
let maxChain = 0;
let answer;

function Collatz(num) {
  let count = 0;
  while(num != 1) {
    if (num % 2 === 0) {
      num /= 2;
      count += 1;
    } else {
      num = 3 * num + 1;
      count += 1;
    }
  }
  count += 1;
  return count; 
}

for (let i = 1; i < limit; i++) {
  const chain = Collatz(i);
  if (chain > maxChain) {
    maxChain = chain;
    answer = i;
  }
}

console.log(answer);

The second thought I had was: "It can't possibly be this easy..."

The more I stared at the question, the more opportunities I found for optimization.

The Actual Approach

Optimization #1: Constraining the Bounds

Let's look at line #20 in the naive approach. Do we really need to search through almost 1 million positive integers to find our solution? The Collatz Conjecture states that the Collatz sequence for any positive integer $x$, after some number of steps, will eventually reach $1$. In other words:

$$x\to \cdots \to 1$$

Consider for a moment the Collatz sequence for the positive integer $2x$. We know for a fact that $2x$ must, by definition, be even. After all, it can be evenly divided by 2. From the question, we know that the handling of an even number is $n\to n/2$. Since we are assuming $n = 2x$, the Collatz sequence for $2x$ looks like this:

$$2x\to x\to \cdots \to 1$$

We can infer from this thought experiment that $\text{Collatz}(2x) = \text{Collatz}(x) + 1$, which means that $\text{Collatz}(2x) > \text{Collatz}(x)$ regardless of the value of $x$.

How does this fact help us? Look again at line #1 of the naive approach. If we assume that our answer is under our limit variable, than the lowest value that our solution could possibly be is limit / 2, since any value under that has a corresponding $2x$ above limit / 2.

Here is an example: For this problem, $\text{limit} = 1000000$ and $\text{limit}/2 = 500000$. That means that $\text{Collatz}(300000)$ could not possibly be the answer, because $\text{Collatz}(600000)$ is sure to be greater. It makes no sense for us to bother trying to calculate any number below $\text{limit}/2$.

We can then change line #20 of the Naive Approach to the following:

for (let i = Math.floor(limit / 2); i < limit; i++) {

Optimization #2: Double-stepping during Odd Number Handling

Let's look back at lines #12 & #13 in the naive approach. The problem states that if $n$ is odd, $n\to 3n+1$. It's interesting to note that, within the context of $n$ being odd, $3n+1$ will always yield an even number. To prove this, let's think about a hypothetical number $e$ which represents any even natural number. This means that $e-1$ represents any odd natural number. Let's now assume that $n=e-1$ and run it through our odd number handling equation.

$$3\times n+1$$ $$3\times (e-1)+1$$ $$3e-2$$ $$e+ e+ e - 2$$

We can see that when any odd number is run through the $3n+1$ equation, it reduces to a term for which every component is divisible by 2. Since, in our implementation, only odd numbers are run through $3n+1$ we can assume that it will produce an even number and apply the even number handling equation immediately (thereby saving an iteration). This means we change line #12 and #13 to read:

num = (3 * num + 1) / 2
count += 2;

Optimization #3: Re-using Past Work

If you think about the problem just a little bit, a glaring realization will pop up. You will realize that the naive approach is repeating work it has already done. Let's list the Collatz sequences for 4 and 5:

$$4\to 2\to 1$$ $$5\to 16\to 8\to ( 4\to 2\to 1 )$$

Once the Collatz sequence for 5 gets to 4, all the naive approach does is repeated. This is happening for almost 1 million integers. We can save all this time if we could store the Collatz chain length for all numbers that we previously calculated and reference it when calculating a new number.

Javascript's array object is a perfect data-structure to use to accomplish this. The index of the array represents the number to be checked and the value stored represents the length of Collatz chain for that index. To help conceptualize what that might look like, here is the contents of the array in question for numbers $1\to 10$.

Index	Value
0	0
1	1
2	2
3	8
4	3
5	6
6	9
7	17
8	4
9	20
10	7

With each iteration, we can check if we've calculated the length of the Collatz chain of that number before, and if so, we can add that chain to the one we've calculated so far... and we're done! We can move on to the next number.

There is just one caveat. There are some chains that produce numbers in excess of 3 million. An array with that many indexed values may be a bit much for our computer to handle. It would make sense for us to focus on storing the chain lengths of those numbers that are below our limit variable, since those will be referenced most often.

To implement this optimization, we are going to add a variable named _cache in the global scope that we initialize to the value of [0, 1]. The 0th index will never be used, but it's important to include the 1st index by default. The _cache variable can be passed into the function as an arguement by altering line #5 of the Naive Approach like so:

function Collatz(num, cache = _cache) {

The while-loop will still terminate once num variable reaches 1 if we alter the beginning of the while-loop to look like this:

while(true) {
  if (cache[num]) {
    count += cache[num];
    break;
  }
  // ...
}

Optimization #4: Deducing Future Work

We saw from the previous section that every Collatz sequence contains a sub-sequence of another number. We saw that it's possible for us to cache the Collatz sequence length in an array. What I will try to suggest in this section is that we should not only cache the Collatz length of the number we are evaluating, but we can cache the Collatz length of all of the other numbers in the sequence in a way that would save many iterations of our while-loop (on line #7 of the Naive approach).

Let's look at some of the sub-sequences in the Collatz sequence for 13:

$$13\to (40\to 20\to 10\to 5\to 16\to 8\to 4\to 2\to 1)$$ $$13\to 40\to (20\to 10\to 5\to 16\to 8\to 4\to 2\to 1)$$ $$13\to 40\to 20\to (10\to 5\to 16\to 8\to 4\to 2\to 1)$$ $$13\to 40\to 20\to 10\to (5\to 16\to 8\to 4\to 2\to 1)$$

Notice that the above sequence also contains the sequence for 40. Assuming we are iterating from $1\to \text{limit}$, than when we arrive at 13, we will not yet have evaluated 40. When we actually do get to 40, we will have to evaluate 40 from scratch (assuming we are using the naive approach). This is unnecessary, since we have already processed it. In fact, it can be calculated mathematically. We can see from the above example that $\text{Collatz}(40) = \text{Collatz}(13) - 1$. In fact, every number in the sequence can be calculated this way:

Sequence	Calculation	Collatz Length
13	$\text{Collatz}(13)-0$	10
40	$\text{Collatz}(13)-1$	9
20	$\text{Collatz}(13)-2$	8
10	$\text{Collatz}(13)-3$	7
5	$\text{Collatz}(13)-4$	6
16	$\text{Collatz}(13)-5$	5
8	$\text{Collatz}(13)-6$	4
4	$\text{Collatz}(13)-7$	3
2	$\text{Collatz}(13)-8$	2
1	$\text{Collatz}(13)-9$	1

We can see from the table above, that every number in the sequence can be calculated mathematically. We need only 3 pieces of information:

• The first number in the sub-sequence. So we know which index to cache the sub-sequence length. We can use the num variable from within the while-loop to access that information.
• The collatz length of the parent sequence. This is calculated and stored in the count variable after the while-loop (line #17 in the Naive approach).
• The position of the first sub-sequence number in the parent sequence. We can use count variable from within the while-loop because it is updated as the while-loop progresses.

It's important for us to restrict which numbers are calculated in this way. Firstly, in the Collatz sequence for 13, the numbers 40 and 20 represent future work but numbers below 16 have already been calculated and cached so we need not repeat that work. Secondly (and most importantly), we must restrict numbers that are so large that they become troublesome to store. Remember from the previous section that we are storing these numbers in an array. Some sequences produce numbers that are in excess of 3 million. Having an array that stores that many items will absolutely cause difficulties. In my solution, I've restricted storage to numbers under our limit variable.

To implement this optimization, we need to add a variable within our Collatz function. We will call it stack and intialize it to an empty array. The stack array will hold all the future work that we will calculate mathematically after the while loop is concluded.

We can now extend the if-statement from the previous section to store the information we need. We can then apply the mathematics once the while loop concludes:

while(true) {
  if (cache[num]) {
    // ...
  } else if (num < limit) {
    stack.push({
      num,
      position: count
    })
  }
  // ...
}

for (let entry of stack) {
  let {num, position} = entry;
  cache[num] = count - position;
}

Putting it all together!

const _cache = [0, 1];

const limit = 1000000;
let maxChain = 0;
let answer;

function Collatz(num, cache = _cache) {
  let count = 0;
  const stack = [];

  while(true) {
    if (cache[num]) {
      count += cache[num];
      break;
    } else if (num < limit) {
      stack.push({
        num, 
        position: count,
      });
    }
    if (num % 2 === 0) {
      num /= 2;
      count += 1;
    } else {
      num = (3 * num + 1) / 2;
      count += 2;
    }
  }

  for (let entry of stack) {
    const {num, position} = entry;
    cache[num] = count - position;
  }

  return count;
}

for (let i = Math.floor(limit / 2); i < limit; i++) {
  const chain = Collatz(i);
  if (chain > maxChain) {
    maxChain = chain;
    answer = i;
  }
}

console.log(answer);

Project Euler - Problem 12 - Solution Explained

Highly Divisible Triangular Number
The sequence of triangle numbers is generated by adding the natural numbers.  So the 7^th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?

I broke this problem down into mini-problems.  All of which were related to one primary concern: A triangular number with 500 factors is probably really really big.  Those mini-problems are as follows:

1. How do I convert $n$ to its corresponding triangular number without having to sum up all the preceding numbers in the series?
2. How do I calculate the number of factors of $n$ without actually having to figure out what each of those factors are?
3. Is there any way to run my functions on $n$ instead of its corresponding triangular number?

Once I solved the mini-problems, solving the actual problem was quite trivial.

1. Converting $n$ to it's corresponding triangular number.

Luckily, there is a well known formula for converting numbers to their corresponding triangular number.  The intuition behind the formula can be found here.  If $n$ represents any integer and $T(n)$ represents it's corresponding triangular number, then: $$T(n) = \dfrac {n\times (n+1)}{2}$$ The formula allows us to avoid having to use the addition operation for every integer preceding the one we're interested in.  Implementing the equation is also fairly straight forward.

function tri(num) {
  return (num * (num + 1)) / 2;
}

2. Counting the factors of $n$.

I did find an easy way to count the factors of $n$ without ever having to find what it's factors actually are.  The intuition behind the method can be found here.  If $n$ represents any integer, $D(n)$ represents the number of factors of $n$, while $P(n)$ represents the prime composition of $n$, and $p$ represents some prime number with exponent $x$ then: $$P(n)=p_1^{x_1}\times p_2^{x_2}\times p_3^{x_3}\times \dots$$$$D(n) = (x_1 + 1) \times(x_2 + 1) \times(x_3 + 1) \times \dots$$ I must admit, coming up with an algorithm to implement the above method was a lot more difficult than I was anticipating.  The algorithm is implemented below and it may not be immediately obvious how it's works.  I have annotated it as best I can.  I needed a list of prime numbers which I previously calculated for problem #7.  If you plan on implementing this algorithm, you can find a list of prime numbers here.

function factorCount(num) {
  let count = 1;
  for (let prime of primes) {     // See note A.
    if ((prime * prime) > num) {  // See note B.
      count *= 2;                 // See note C.
      break;
    }
    let exponent = 0;             // See note D.
    while (num % prime == 0) {    // See note E.
      exponent++;
      num /= prime;
    }
    if (exponent > 0) {           // See note F.
      count *= exponent + 1;      // See note G.
    }
    if (num == 1) {               // See note H.
      break;
    }
  }
  return count;                   // See note I.
}

Notes on the above algorithm.

1. I needed a list of prime numbers to implement this algorithm.  In this example, the global constant primes represents an array of prime numbers in ascending order, starting at 2, and ending at 104743.
2. First, we need to establish an exit condition so that we won't need to iterate over the entire list of primes.  Since we only need to search from $1 \longrightarrow \sqrt{n}$ to find factors of $n$, the very first prime whose square is greater than $n$ tells us that we no longer need to evaluate any primes at that point or beyond.
3. We double the count since every factor of $n$ has a co-factor after $\sqrt{n}$.
4. We must now determine the exponent of the prime we are evaluating. We start our exponent counter at 0.
5. So long as $n$ is divisible by our prime, we can increment our counter while dividing out the prime.  To help visualize this: Imagine that $n=8$ and we are evaluating the prime $p=2$.  To get our exponent, we progressively divide $n/p$ while also increasing our exponent counter by 1 each time the division occurs.  At the end of this process, our exponent counter will equal 3.  This makes sense because $8 = 2\times 2\times 2 = 2^3$
6. Before we proceed, we need to check if the counter moved at all.  This tells us whether $n$ was divisible by the prime. If it wasn't divisible, we cannot apply the method.
7. Now that we have determined the exponent.  We can finally apply the method!
8. Lastly, we need to break out of the loop if $n=1$.  Think back to the $n=8$, $p=2$ example (from note E).  When all of the $p$'s are divided out of $n$, $n=1$.  At that point, there is no sense trying to evaluate the next prime.
9. Since the variable count now equals the number of factors of $n$, we can return it.

3. Working with $n$ instead of $T(n)$.

Let's say that $n$ is any positive integer, $T(n)$ is the corresponding triangular number of $n$, and $D(n)$ is the number of factors of $n$.  Than, this Euler problem is asking us to find the $T(n)$ for which $D(T(n)) > 500$.  The question is, how do we find $D(T(n))$ efficiently?
Since $T(n)$ is many, many times larger than $n$, we can speed up our calculation dramatically if we could just work with $n$.  The strategy is to use $T(n) = \dfrac {n\times (n+1)}{2}$ to find $D(T(n))$ in terms of $n$.  If we do the math, then: $$D(T(n)) = D\left (\dfrac {n\times (n+1)}{2}\right )=$$$$D\left (\dfrac {n}{2}\right )\times D(n+1)\implies \text{if }n\text{ is even}$$$$D(n)\times D\left (\dfrac {n+1}{2}\right )\implies \text{if }n\text{ is odd}$$If we use our factorCount function above to represent the $D(n)$ the resulting code can take any integer and spit out the number of factors of it's corresponding triangular number.  The code is as follows:

function triFactorCount(num) {
  let term1, term2;
  if (num % 2 == 0) {
    term1 = factorCount(num / 2);
    term2 = factorCount(num + 1);
  } else {
    term1 = factorCount(num);
    term2 = factorCount((num + 1) / 2);
  }
  return term1 * term2;
}

Putting it all together!

This is my solution to Project Euler, Problem 12.  I'll be using the tri and triFactorCount functions as they've been defined above.

let num = 1;

while (triFactorCount(num) < 500) {
 num++;
}

console.log(tri(num));