App developer

The Collatz Conjecture: Revisited

I was digging through some of the older posts on this site and I came across the The Collatz Conjecture. I wrote it around four years ago, during the Swift 2.2 days. I thought I’d try making it a bit more efficient. As a reminder, here’s the problem statement:

  • create an array to capture the sequence of numbers returned by the Collatz function1.

My original solution was 21 lines of code. The new solution I’ve come up with is just under half of that and just as expressive (I think).

The gist:

  • Extend Array when the only elements are UnsignedIntegers with a new mutating function, called collatzify.
  • The collatzify function will check if the array is empty (1), and will do nothing if it is
  • If the only value in the array is 1, the function mutates the array to [1,4,2,1] (2)
  • Otherwise, while the last element in the array isn’t 1, the function recursively adds to the array by applying the collatz function to the last element. (3)
extension Array where Element: UnsignedInteger {
    
    /// Takes the last value in the array and then populates the rest of the collatz sequence.
    mutating func collatzify() {
        if !self.isEmpty { // 1
            if self.count == 1 && self.last == 1 {
                self = [1,4,2,1] // 2
            } else {
                while self.last != 1 {
                    self.append( self.last! % 2 == 0 ? self.last! / 2 : (self.last! * 3) + 1) // 3
                }
            }
        }
    }
    
}

// Usage:
var sequence:[UInt] = [7]
sequence.collatzify() // [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Performance wise—as measured by XCTestCase—this solution is over 90% faster that the original: 0.000017s vs. 0.000388s.

  1. The Collatz conjecture is a conjecture in mathematics that concerns a sequence defined as follows: start with any positive integer n. Then each term is obtained from the previous term as follows: if the previous term is even, the next term is one half the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that no matter what value of n, the sequence will always reach 1.—Wikipedia ↩︎