What's the number with the biggest Collatz sequence in a range?

Question

I have to write a program using recursion that, given n, returns the minimum value m, 1 ≤ m ≤ n, that generates the longest sequence of Collatz Steps

For example 20, the number that has to return is 18, because 18 and 19 both generate the most amount of steps (20) to 1, but 18 is smaller. We got a couple examples of what correct answers look like:

*Main> longestSequenceTo 13
9
*Main> longestSequenceTo 30
27
*Main> longestSequenceTo 88
73
*Main> longestSequenceTo 1121
871

My biggest issue is that we're not allowed to use lists, and our knowledge of Haskell is very basic still. I've managed to write the collatz conjecture as a function, and I think I know what my condition should be for the recursion on the main function:

collatz :: Integer->Integer
collatz 1 = 0
collatz n | even n = 1 + collatz (div n 2)
          | otherwise = 1 + collatz (3*n+1)

i think my function should look something like:

longestSequence n | collatz n <= collatz (n-1) = 
                  | otherwise = 

my problem is I dont know how to "store" the actual n, instead of getting the number of steps a number has to take to reach 1

Answer 1

In the way you "think your longestSequence n function should look like", you are only comparing the value at n with the value at n-1. The longest sequence could lie somewhere else. Besides, for each n you calculate the collatz length twice. You only need to calculate the length for n and compare it with the maximum value found so far.

Consider the following procedure that will find the maximum sequence length up to n, without using lists:

maxLength n = go 0 1
    where
        go z x  | x==n   = z'
                | True   = go z' x'
            where
                value = collatz x
                z' = if value > z then value else z
                x' = succ x

You keep track of the max value found so far, with the variable z. And you feed the next run with modified values of x and z. The result is obtained when x is equal to n.

But what you are really after is not the length but who produced that length first... Can you come up with the needed changes to z and z' to keep track of both a maximum length and the number n that produced it? Try to finish the function below Hint: z will have the form of a tuple of (value,x):

whoHitsFirstMaxLength n = go ??? 1
    where
        go z x  | x==n   = ???
                | True   = go z' x'
            where
                value = collatz x
                z' = if value > ??? then ??? else z
                x' = succ x

Answer 2

First we name the values you operate on, so we can decide what to do with them in a separate step of our thought process:

longestSequence n =
  let
    this = collatz n 
    that = collatz (n-1) 
  in
     ....

So now we can see you're counting down; let's count up instead:

longestSequence n = go 1
  where
  go k = let
           this = collatz k 
           that = collatz (k+1) 
         in
            ....

but this only gives us the values of Collatz length for two values; we need them all; recursion to the rescue! --

longestSequence n = postprocess $ go 1
  where 
  go k | k > n = (n, -1)
  go k = let
           this = collatz k 
           that = go (k+1) 
         in
            ....
  postprocess x = ...

This has the right structure now. It does the collatz for k, and longestSequence for k+1 (technically, it calls go), so that you can compare these results to create the result for longestSequence for k (technically, this is the result of go).

In other words if you know the number between k+1 and n with the longest sequence (and the length of that sequence), and you know the length of the sequence for k, you can decide which number between k and n has the longest sequence (and also know the length of that sequence), and return that.

I also wrote some more answers about the thought process behind the recursion method of problem solving, see if any of them helps.