Longest Collatz sequence in PHP

Created:08 Feb 2020 23:30:22 , in  Maths

This article is a result of a fairly well known computer programming problem I came across online some time ago. Essence of the problem was about finding the longest Collatz sequence, that is the largest number of terms for a number less than N, with N being 1 000 000.

For positive integer n, Collatz sequence is defined as follows: n / 2 for even numbers and 3n + 1 for odd ones. A Collatz sequences have different lengths depending on what the initial n is. Also, it is thought that each Collatz sequence eventually ends with number 1.

Collatz sequences in PHP

What follows is my solution to the described problem and given as a class written in PHP programming language. The class contains a small bonus, which is related to the problem, that is, a recursive method for finding all numbers for a Collatz sequence for number n inclusive. An example usage included below.

/**
 * SWWWCollatz: Find Collatz sequence and a number with the longest Collatz seqeunce less than N
 * Author: Sylwester Wojnowski
 * Licence : GNU
 */
class SWWWCollatz{

  // maximum number to consider + 1
  private $max = 0;

  /** 
   * Recursively finds sequence of Collatz numbers for a given n
   *  Arguments: 
   *    n int - number Collatz sequence to be found for
   *    sequence array - holds resulting Collatz sequence
   */
  public static function sequence($n,$sequence = []){
    if($n < 1){
      throw new Exception('n must be greater than 0');
    }

    $sequence[] = $n;    

    if($n === 1){ 
      return $sequence;  
    } 

    if($n % 2 == 0){  
      $n /= 2;
    } else {
      $n = (3 * $n) + 1;    
    }
    
    return self::sequence($n,$sequence);
  }

  public function __construct($max){

    if((int)$max < 1){
      throw new Exception('Maximum number $max must be greater than 0');
    }
    
    $this -> max = $max;
  }
 
  /** 
   * Find number with the longest Collatz sequence for a number less than $max
   *  Arguments: 
   *    n int - number Collatz sequence to be found for
   *    sequence array - holds resulting Collatz sequence
   */   
  public function getNumWithLongestSeq(){
    return $this -> collatzNumberWithLongestSeq($this -> max);
  }

  // returns a number below max with the longest Collatz sequence
  protected function collatzNumberWithLongestSeq($max){
    $largest = 0;
    $largest_i = 0;
    $i = 1;

    while($i < $max){
      $current = $this -> collatzCount($i);

      if($current > $largest){
        $largest = $current;
        $largest_i = $i;
      }  

      $i++; 
    }
    // search for the largest value in sequences and return it 
    return $largest_i; 
  } 

  // get numbers of items in sequence for a number n
  protected function collatzCount($n){
    $sequence = [];   
    while($n > 0){ 
      $sequence[] = $n;

      if($n === 1){
        return count($sequence); 
      }      

      if($n % 2 == 0){  
        $n /= 2;
      } else {
        $n = (3 * $n) + 1;    
      }
    }
  }

}

SWWWCollatz class usage

Finding Collatz sequence terms.

If n is 10:

WWWCollatz::sequence(10); 
=> [10,5,16,8,4,2,1] 

Finding number less than n with the longest sequence

Below maximum term, n, is set to be 10, and it is n = 9, which produces the longest Collatz sequence.

$collatz = new SWWWCollatz(10);
$collatz -> getNumWithLongestSeq();
=> 9

Longest Collatz sequence for n equals to 1 000 000

It takes about a minute to get the result for this one.

$collatz = new SWWWCollatz(1000000);
$collatz -> getNumWithLongestSeq();
=> 837799

Conclusion

Here you have it. A tool for playing with Collatz sequence using both tiny and large starting numbers. I hope the article and the code will prove useful.

This post was updated on 09 Feb 2020 02:19:14

Tags:  php