CODEWITHSUNDEEP
algorithmperformancebig-odynamic-programmingmemoization
Frank P.
Frank P.

Reputation: 513

Project Euler #14: Collatz Conjecture - What are some algorithms to utilize memoization/speed effectively?

Link to problem: https://projecteuler.net/problem=14

So I've solved this problem using a fairly 'trivial' implementation of memoization in R. Basically, I just count up from 1:1,000,000 and count the number of collatz application it takes to get to 1. If I encounter a number less than the current iteration, I just add that number's 'chain' to the current sequence.

R Code:

collatz <- function(n) {

  if(n %% 2 == 0) return(n / 2)
  else return(3 * n + 1)

}

chains <- rep(0, 1e6)

for(i in 1:length(chains)) {

  n <- i
  iter <- 0

  while(n != 1) {

    n <- collatz(n)
    iter <- iter + 1

    if(n < i) {
      iter <- iter + chains[n]
      break
    }

  }

  chains[i] <- iter

}

which.max(chains)

Now this code runs relatively fast, even for R, but the more I think about this problem, the more interesting I find it.

It seems there's a ton of different ways to approach it for efficiency in terms of space and runtime. Maybe loop backwards? Maybe run through the odd numbers or even numbers first, and then do the other half? Maybe keep intermediate results and not just the terminal chain length when incrementing? There may also be some ideas that are more 'mathematical' in nature rather than directly related to dynamic programming. Has anybody given thought to this problem/algorithm and can provide some other potentially more efficient implementations?

Upvotes: 3

Views: 548

Answers (1)

Tony Tuttle
Tony Tuttle

Reputation: 632

You are doing your memoizing in strict 1:1000000 order. There is no reason, however, to not memoize the first time you see a value. For example, starting with 3 gives the sequence 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1. You can memoize 10, 5, 16, 8, 4 in addition to just memoizing 3.

This will reduce the number of operations, perhaps substantially. Continuing the example above, memoizing 4 the first time you saw it saved the 2 steps it would have required to memoize it later, and memoizing 5 saved another 3 steps. It seems like these saved steps should snowball quite quickly.

Upvotes: 6

Related Questions