Project Euler Problems 1 to 100 - Problem 14: Longest Collatz sequence

[BilboIsNuts]

Tell us what’s happening:

Hello everyone! Im trying to solve problem number 14 of the Euler Project. We are asked to write a function that takes an integer number n as argument and returns the length of the longest Collatz sequence generated by starters that are stricly lesser t an n.

The Collatz sequence is generated by starting from any positive number and, if the number is even you halve it, otherwise you triple it and then add one. Eventually you will reach one and the sequence is complete.

I tried a recursive approach just to practice recursion but it seems like i’m not getting the results I want. Chat gpt suggest that it’s due to the recursive approach itself, but I wanted to ask the community if that makes sense. If you would like to provide a sanity check on my approach I`d appreciate it a lot.

Thanks in advance and have a good day.

Your code so far

function countCollatz(n){
  let counter=0;
  function getCollatz(n){
    counter++;
    if(n==1){
       return n;
    }
    else{
      if (!(n%2)){
        //console.log(n)
        return getCollatz((n/2))
      }
      else{
         //console.log(n)
         return getCollatz((3*n+1));
      }
    }
  }
  getCollatz(n);
  return counter;
}

function longestCollatzSequence(n){
  let max=1;
  for(let cand=1; cand<n; cand++){
    let test=countCollatz(cand);
    if(test > max)
      max=test;
  } 
  return max;
}

console.log(longestCollatzSequence(5847))
console.log(countCollatz(9));

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/115.0.0.0 Safari/537.36

Challenge: Project Euler Problems 1 to 100 - Problem 14: Longest Collatz sequence

Link to the challenge:

freeCodeCamp.org

[sanity]

What are the results you’d expect? In other words - what this function should return?

If you are asking if recursion can be used for getting Collatz sequence, or length of it, the answer is yes. However it might have troubles with the last test case, similarly to other not very efficient solutions.

Note also that usually recursion is getting to the right result by returning something from the recursive calls and kind of putting things together. Rather than depending on variables outside of the function scope.

[BilboIsNuts]

The text of the problem:

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 the given limit, produces the longest chain?

Note: Once the chain starts the terms are allowed to go above limit.

I must see which starter (that must be strictly below a certain n passed as an argument) gives the longest sequence . It seems the first test is simply wrong: if you start from the number 9 you get a Collatz sequence that is 20 terms long (9, 28, 14, 7, 22 ,11, 34, 17, 52, 26 ,13, 40 20 , 10 , 5, 16, 8, 4, 2, 1).
There’s also the chance that what the author of the problem is asking is the longest sequence shorter than n that is produced, in which case I guess a rephrasing of the problem is warranted.

TLDR Either I am misinterpreting the question or at least one of the test is wrong, you count the number of elements of te Collatz sequence startin a 9 you get a 20 numbers long sequence, which is greater than the 9 expected as an answer.

[sanity]

That sounds correct. Now, what is returned by function from the first post?

[BilboIsNuts]

The function longestCollatzSequence(14) returns 20, which is the number of terms of the longest Collatz sequence generated from starters ranging from 1 to 13 . I checked this manually, also, the function countCollatz(starter) works as expected and correctly count the number of terms in a Collatz sequence that begins with the starter number passed as an argument.

But right now I’m realizing that I read the question poorly: I am asked to return the starter that gives the longest Collatz sequence, not the length of such sequence. If I make some adjustments like so:

function longestCollatzSequence(n){
  let cand=1;
  let result=1;
  for(let max=1; cand<n; cand++){
    let test=countCollatz(cand);
    if(test > max){
      max=test;
      result=cand;
    }
  } 
  return result;
}

I pass all tests except for the last one, probably because the recursive approach is not efficient enough to run before timeout. Thanks for your gentle guidance, you helped me realize my own mistake instead of simply pointing it out