Longest Collatz sequence in PHP

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 


Author, Copyright and citation

Author

Sylwester Wojnowski

Author of the above article, Sylwester Wojnowski, is sWWW admin and owner.He enjoys doing Maths and studying algorithms, writing code in scripting and command languages, Thrash Metal music and playing electric guitar.

Copyrights

©Copyright, 2020 Sylwester Wojnowski. This article may not be reproduced or published as a whole or in parts without permission from the author. If you share it, please give author credit and do not remove embedded links.

Computer code, if present in the article, is excluded from the above and licensed under GPLv3.

Citation

Cite this article as:

Wojnowski, Sylwester. "Longest Collatz sequence in PHP." From sWWW - Code For The Web . https://wojnowski.net.pl//main/index/longest-collatz-sequence-in-php