Collatz Sequence

excerpt: How to write recursive algorithm using the recurrence relation. tags: modulo-operator recurrence-relation reducing-the-input-value counter

A Collatz sequence in mathematics can be defined as follows. Starting with any positive integer:

if n is even, the next number in the sequence is n / 2 if n is odd, the next number in the sequence is 3n + 1

It is conjectured that every such sequence eventually reaches the number 1. Test this conjecture.

Implementation

Recursive Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def collatz(n)
  if n == 1
    return true
  end
  
  if n % 2 == 0
    return collatz(n/2)
  else
    return collatz((3 * n) + 1)
  end 
end

Iterative Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def collatz(n)
  while n != 1
    if n % 2 == 0
      n = n / 2
    else
      n = (3 * n) + 1
    end 
  end  

  n
end

Problem Variation

Count the number of steps required to reach 1 in the Collatz sequence.

Iterative Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def collatz(n)
  count = 0

  while n != 1
    count += 1

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

p collatz(33)

Recursive Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def collatz(n)
  if n == 1
    return true
  end
  
  @count += 1
  
  if n % 2 == 0
    return collatz(n/2)
  else
    return collatz((3 * n) + 1)
  end 
end

Building Blocks

Modulo Operator
Recurrence Relation
Reducing the Input Value
Counter