<?php

/**
 * Number_Theory
 *
 * @author Alix Axel
 */

class Number_Theory
{
    private $Math = null;

    /**
     * Returns an array containing the Collatz trajectory of number.
     *
     * @param mixed $number
     * @return array
     */
    function Collatz_Trajectory($number)
    {
        if ($this->Math->Compare($number, '<', 1))
        {
            return false;
        }

        $result = array();

        $result[0] = $number;

        for ($i = 1; $this->Math->Compare($number, '!=', 1); $i = $this->Math->Add($i, 1))
        {
            if ($this->Math->Compare($this->Math->Modulo($number, 2), '==', 0))
            {
                $number = $this->Math->Divide($number, 2);

                $result[$i] = $number;
            }

            else
            {
                $number = $this->Math->Add($this->Math->Multiply($number, 3), 1);

                $result[$i] = $number;
            }
        }

        return $result;
    }

    /**
     * Returns an array containing the divisors of number.
     *
     * @param mixed $number
     * @return array
     */
    function Divisors($number)
    {
        $result = array(1);

        $i_limit = $this->Math->Divide($number, 2);

        for ($i = 2; $this->Math->Compare($i, '<=', $i_limit); $i = $this->Math->Add($i, 1))
        {
            if ($this->Math->Compare($this->Math->Modulo($number, $i), '==', 0))
            {
                $result[] = $i;
            }
        }

        return $result;
    }

    /**
     * Returns an array containing the factorization of number.
     *
     * @param mixed $number
     * @return array
     */
    function Factor($number, $reset = true)
    {
        static $factors = array();

        if ($reset === true)
        {
            $factors = array();
        }

        if ($this->Is_Prime($this->Math->Integer($number)))
        {
            if (!isset($factors[$number]))
            {
                $factors[$number] = 1;
            }

            else
            {
                $factors[$number] = $this->Math->Add($factors[$number], 1);
            }
        }

        else
        {
            $i_limit = $this->Math->Ceil($this->Math->Root($number));

            for ($i = 2; $this->Math->Compare($i, '<=', $i_limit); $i = $this->Math->Add($i, 1))
            {
                if ($this->Is_Prime($this->Math->Integer($i)))
                {
                    if ($this->Math->Compare($this->Math->Modulo($number, $i), '==', 0))
                    {
                        if (!isset($factors[$i]))
                        {
                            $factors[$i] = 1;
                        }

                        else
                        {
                            $factors[$i] = $this->Math->Add($factors[$i], 1);
                        }

                        $this->Factor($this->Math->Divide($number, $i), false);

                        break;
                    }
                }
            }
        }

        return $factors;
    }

    /**
     * Returns an array containing the first Fibonacci numbers.
     *
     * @param mixed $number
     * @return array
     */
    function Fibonacci($number)
    {
        $number = $this->Math->Absolute($this->Math->Integer($number));

        if ($this->Math->Compare($number, '<', 1))
        {
            return false;
        }

        $result[0] = 0;
        $result[1] = 1;

        for ($i = 2; $this->Math->Compare($i, '<=', $number); $i = $this->Math->Add($i, 1))
        {
            $result[$i] = $this->Math->Add($result[$this->Math->Subtract($i, 1)], $result[$this->Math->Subtract($i, 2)]);
        }

        return $result;
    }

    /**
     * Returns the Greatest Common Divisor of two arbitrary precision numbers.
     *
     * @param mixed $number1
     * @param mixed $number2
     * @return mixed
     */
    function GCD($number1, $number2)
    {
        $number1 = $this->Math->Absolute($this->Math->Integer($number1));
        $number2 = $this->Math->Absolute($this->Math->Integer($number2));

        if (($this->Math->Compare($number1, '==', 0)) && ($this->Math->Compare($number2, '==', 0)))
        {
            return false;
        }

        if (($this->Math->Compare($number1, '==', $number2)) && ($this->Math->Compare($number1, '>=', 1)))
        {
            return $number1;
        }

        return $this->Math->Compare($number2, '<', $number1) ? $this->GCD($this->Math->Subtract($number1, $number2), $number1) : $this->GCD($number1, $this->Math->Subtract($number2, $number1));
    }

    /**
     * Finds whether the number is a perfect number.
     *
     * @param mixed $number
     * @return bool
     */
    function Is_Perfect($number)
    {
        $divisors = $this->Divisors($number);

        $result = 0;

        foreach ($divisors as $divisor)
        {
            $result = $this->Math->Add($result, $divisor);
        }

        if ($this->Math->Compare($result, '==', $number))
        {
            return true;
        }

        return false;
    }

    /**
     * Finds whether the number is a prime number.
     *
     * @param mixed $number
     * @return bool
     */
    function Is_Prime($number)
    {
        $number = $this->Math->Absolute($this->Math->Integer($number));

        $small_primes = array(2, 3, 5, 7, 11);

        foreach ($small_primes as $small_prime)
        {
            if (($this->Math->Compare($number, '!=', $small_prime)) && ($this->Math->Compare($this->Math->Modulo($number, $small_prime), '==', 0)))
            {
                return false;
            }
        }

        if ($this->Math->gmp_enabled === true)
        {
            return gmp_prob_prime($number) ? true : false;
        }

        else
        {
            $pseudoprimes = array(1387, 2047, 2701, 3277, 4033, 4369, 4681, 5461, 7957, 8321, 10261, 13747, 14491, 15709, 18721, 19951, 23377, 29341);

            if (in_array($number, $pseudoprimes))
            {
                return false;
            }

            else
            {
                if ($this->Math->Compare($this->Math->Modulo($this->Math->Subtract($this->Math->Power(2, $number), 2), $number), '==', 0))
                {
                    return true;
                }

                else
                {
                    return false;
                }
            }
        }
    }

    /**
     * Finds whether the number is a prime number with the Wilson test.
     *
     * @param mixed $number
     * @return bool
     */
    function Is_Prime_Wilson($number)
    {
        $number = $this->Math->Absolute($this->Math->Integer($number));

        if ($this->Math->Compare($this->Math->Modulo($this->Math->Add($this->Math->Factorial($this->Math->Subtract($number, 1)), 1), $number), '==', 0))
        {
            return true;
        }

        return false;
    }

    /**
     * Returns the Least Common Multiple of two arbitrary precision numbers.
     *
     * @param mixed $number1
     * @param mixed $number2
     * @return mixed
     */
    function LCM($number1, $number2)
    {
        return $this->Math->Multiply($number2, ($this->Math->Divide($number1, $this->GCD($number1, $number2))));
    }

    /**
     * Finds the next prime number.
     *
     * @param mixed $number
     * @return mixed
     */
    function Next_Prime($number)
    {
        $number = $this->Math->Integer($number);

        if ($this->Math->gmp_enabled === true)
        {
            return gmp_strval(gmp_nextprime($number));
        }

        $number = $this->Math->Add($number, 1);

        while ($this->Is_Prime($number) === false)
        {
            $number = $this->Math->Add($number, 1);
        }

        return $number;
    }

    /**
     * Number_Theory Constructor.
     *
     * @return Number_Theory
     */
    function Number_Theory()
    {
        require_once('Math.php');

        $this->Math = new Math();
    }

    /**
     * Returns an array containing the first rows of Pascal Triangle.
     *
     * @param mixed $rows
     * @return array
     */
    function Pascal_Triangle($rows)
    {
        $result = array();

        for ($i = 1; $this->Math->Compare($i, '<=', $rows); $i = $this->Math->Add($i, 1))
        {
            for ($j = 1; $this->Math->Compare($j, '<=', $i); $j = $this->Math->Add($j, 1))
            {
                if (($this->Math->Compare($i, '==', 1)) || ($this->Math->Compare($i, '==', 2)))
                {
                    $result[$i][$j] = 1;
                }

                else
                {
                    if (($this->Math->Compare($j, '==', 1)) || ($this->Math->Compare($j, '==', $i)))
                    {
                        $result[$i][$j] = 1;
                    }
                }

                if (($this->Math->Compare($i, '>', 2)) && ($this->Math->Compare($j, '>', 1)) && ($this->Math->Compare($j, '<', $i)))
                {
                    $result[$i][$j] = $this->Math->Add($result[$this->Math->Subtract($i, 1)][$this->Math->Subtract($j, 1)], $result[$this->Math->Subtract($i, 1)][$j]);
                }
            }
        }

        return $result;
    }

    /**
     * Finds whether the number is a perfect square number.
     *
     * @param mixed $number
     * @return bool
     */
    function Perfect_Square($number)
    {
        if ($this->Math->gmp_enabled === true)
        {
            return gmp_perfect_square($number);
        }

        if ($this->Math->Is_Integer($this->Math->Root($number, 2)))
        {
            return true;
        }

        return false;
    }

    /**
     * Returns an array containing the number raised to all powers between from and to.
     *
     * @param mixed $number
     * @param mixed $from
     * @param mixed $to
     * @return array
     */
    function Powers_Of($number, $from = 0, $to = 10)
    {
        $result = array();

        for ($i = $from; $this->Math->Compare($i, '<=', $to); $i = $this->Math->Add($i, 1))
        {
            $result[$i] = $this->Math->Power($i, $number);
        }

        return $result;
    }

    /**
     * Returns an array containing the Proth Gilbreath Triangle of the sequence.
     *
     * @param array $sequence
     * @return array
     */
    function Proth_Gilbreath_Triangle($sequence)
    {
        $result = array();

        if (!is_array($sequence))
        {
            return false;
        }

        $total_rows = count($sequence);

        for ($row = $total_rows; $this->Math->Compare($row, '>=', 1); $row = $this->Math->Subtract($row, 1))
        {
            for ($column = 0; $this->Math->Compare($column, '<', $row); $column = $this->Math->Add($column, 1))
            {
                if ($this->Math->Compare($row, '==', $total_rows))
                {
                    $result[$total_rows][$column] = $sequence[$column];
                }

                else
                {
                    $result[$row][$column] = $this->Math->Subtract($this->Math->Absolute($result[$this->Math->Add($row, 1)][$this->Math->Add($column, 1)], $result[$this->Math->Add($row, 1)][$column]));
                }
            }
        }

        return $result;
    }

    /**
     * Returns the lowest ratio of two arbitrary precision numbers.
     *
     * @param mixed $number1
     * @param mixed $number2
     * @return string
     */
    function Ratio($number1, $number2)
    {
        $lowest = $number1;

        if ($this->Math->Compare($number2, '<', $lowest))
        {
            $lowest = $number2;
        }

        $gcf = 1;

        for ($count = $this->Math->Add($lowest, 1); $this->Math->Compare($count, '>=', 1); $count = $this->Math->Subtract($count, 1))
        {
            if (($this->Math->Compare($this->Math->Modulo($number1, $count), '==', 0)) && ($this->Math->Compare($this->Math->Modulo($number2, $count), '==', 0)) && ($this->Math->Compare($count, '>', $gcf)))
            {
                $gcf = $count;
            }
        }

        $number1 = $this->Math->Divide($number1, $gcf);
        $number2 = $this->Math->Divide($number2, $gcf);

        return $number1 . ':' . $number2;
    }

    /**
     * Returns the Square Difference method of Fermat.
     *
     * @param mixed $number
     * @return mixed
     */
    function Square_Difference_Fermat($number)
    {
        if ($this->Math->Compare($this->Math->Modulo($number, 2), '==', 0))
        {
            return false;
        }

        else
        {
            $result = array();

            if ($this->Math->Is_Integer($this->Math->Root($number)))
            {
                $k = $this->Math->Root($number);
            }

            else
            {
                $k = $this->Math->Ceil($this->Math->Root($number));
            }

            $k_limit = $this->Math->Divide($this->Math->Add($number, 1), 2);

            while ($this->Math->Compare($k, '<=', $k_limit))
            {
                $n = $this->Math->Root($this->Math->Subtract($this->Math->Power($k, 2), $number));

                if ($this->Math->Compare($n, '==', $this->Math->Round($n)))
                {
                    $result[] = $k;
                    $result[] = $n;

                    sort($result);

                    break;
                }

                $k = $this->Math->Add($k, 1);
            }

            return $result;
        }
    }

    /**
     * Returns the sum of all digits from zero or from number1 to number2.
     *
     * @param mixed $number1
     * @param mixed $number2
     * @return mixed
     */
    function Sum_Gauss($number1, $number2 = null)
    {
        if (empty($number2))
        {
            return $this->Math->Divide($this->Math->Multiply($number1, $this->Math->Add($number1, 1)), 2);
        }

        $number1 = $this->Math->Subtract($number1, 1);

        return $this->Math->Subtract($this->Math->Divide($this->Math->Multiply($number2, $this->Math->Add($number2, 1)), 2), $this->Math->Divide($this->Math->Multiply($number1, $this->Math->Add($number1, 1)), 2));
    }
}

highlight_file(__FILE__);

?>