Collatz sequence longest steps-CodePudding

I have to write a program that given n natural number verifies that for all 1 ≤ k ≤ n, the number k satisfy the Collatz Conjecture, and returns the minimum value m, 1 ≤ m ≤ n, that generates the longest sequence of steps from a1 = m up to 1. For example:

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

This is the code I've written so far:

longestSequenceTo :: Integer -> Integer 
longestSequenceTo n = longestSequenceToAux n 1

longestSequenceToAux :: Integer -> Integer -> Integer 
longestSequenceToAux n m | satisfyCollatzAux (m) < satisfyCollatzAux (m 1) = longestSequenceToAux n (m 1) 
                         | satisfyCollatzAux (m) > satisfyCollatzAux (n) = longestSequenceToAux (n-1) m
                         | otherwise = n

satisfyCollatzAux :: Integer -> Integer
satisfyCollatzAux n | n == 1 = 0
                      | mod n 2 == 0 = satisfyCollatzAux (div n 2)   1
                      | mod n 2 == 1 = satisfyCollatzAux (3*n   1)   1

This code run the examples above, but it doesn't for all n numbers. It is mandatory to use recursion.

For example 20, the number that has to return is 18, because 20 has 7 steps to get to 1 and 18 has 20 steps to 1. But there is a problem with 19, it has the same steps to 1 like 18.

CodePudding user response：

Your algorithm is not doing what you expect. Consider the first 20 numbers:

a   collatz(a)  n   m   1st guard  2nd guard    otherwise
1     1        20   1   TRUE       FALSE
2     2        20   2   TRUE       FALSE
3     8        20   3   FALSE      FALSE        >>> n = 20
4     3             
5     6             
6     9             
7    17             
8     4             
9    20             
10    7             
11   15             
12   10             
13   10             
14   18             
15   18             
16    5             
17   13             
18   21             
19   21             
20    8

Your algorithm stops at n=20, m=3, returning the value of n in your function, which is 20.

It's evident looking at these numbers that you want to get a=18, which is the smallest number that produces the longest sequence (21).

Using recursion, a function that calculates the maximum value could be something like this:

myMax mx [] = mx
myMax mx (x:xs) | mx > x    = myMax mx xs
                | otherwise = myMax x  xs

Where the variable mx is storing the maximum value found so far. The difference in your case is that you need to save not only the maximum value of the collatz length, but also the number a that produced it. So, your storing value mx should be a tuple of (a, value). See if you can do the changes.

If you want to call your function like longestSequenceTo n, you need to 1) expand your a values to something like [1..n] 2) apply your SatisfyCollatzAux function to each a value, 3) find your maximum (a, value) using a recursion function similar to the one above.

CodePudding user response：

Always break problems down into smaller ones.

First define a function to calculate how many steps the Collatz formula takes to reach 1 for any given number.

collatzSteps :: (Integral a1, Num a2) => a1 -> a2
collatzSteps = collatzSteps' 0
  where
    collatzSteps' c n 
      | n == 1         = c
      | n `mod` 2 == 0 = collatzSteps' (c 1) (n `div` 2)
      | otherwise      = collatzSteps' (c 1) (n * 3   1)

Next we define a function that will recursively iterate over a range from 1 to n. Each iteration if the Collatz steps for n are greater than the maxSteps argument, we call the function recursively, updating that curMax. When n is greater than the limit, we return the current smallestNum.

longestSequenceTo :: Integral a1 => a1 -> a1
longestSequenceTo n = aux (0, 0) 1 n
  where
    aux curMax@(smallestNum, maxSteps) n limit 
      | n > limit        = smallestNum
      | maxSteps < steps = aux (n, steps) (n 1) limit
      | otherwise        = aux curMax (n 1) limit 
          where steps = collatzSteps n

Prelude> longestSequenceTo 13
9
Prelude> longestSequenceTo 30
27
Prelude> longestSequenceTo 88
73
Prelude> longestSequenceTo 1121
871