# encoding=utf8


"""

Module containing functions and methods related to sequences in number theory such as
the Fibonacci sequence, the 3n + 1 problem, and more.

"""


import numpy as np
from mathpy.numtheory.integers import iseven
from decimal import Decimal, localcontext


def fibonacci(n, output='last', prec=100):
    r"""
    Computes the Fibonacci sequence up to given value of n.

    Parameters
    ----------
    n : int
        Integer designating the stopping point of the Fibonacci sequence
    output : {'last', 'array'}, optional
        If 'last', the last integer in the Fibonacci sequence up to n is returned,
        if 'array', the entire sequence is returned. Defaults to 'last'.
    prec : int default 100, optional
        Defines level of precision for factorials over 100
        for use by the decimal package

    Returns
    -------
    fn : numpy ndarray or int
        Last integer in Fibonacci sequence up to :math:`n` or the an array of the
        Fibonacci sequence up to :math:`n`.

    Notes
    -----
    The Fibonacci sequence is defined by a recurrence relation where :math:`f_n` denotes
    the series up to :math:`n` points.

    .. math::

        f_n = f_{n-1} + f_{n-2}

    With initial conditions:

    .. math::

        f_1 = 1, \qquad f_2 = 2

    Examples
    --------
    >>> fibonacci(10)
    55.0
    >>> fibonacci(10, 'array')
    array([  0.,   1.,   1.,   2.,   3.,   5.,   8.,  13.,  21.,  34.,  55.])

    References
    ----------
    Moler, C. (2011). Numerical computing with MATLAB (1st ed.).
        Philadelphia, Pa: Society for Industrial & Applied Mathematics.

    """
    fn = np.empty(n + 1)

    fn[0] = 0
    fn[1] = 1
    if n >= 100:
        with localcontext() as ctx:
            ctx.prec = prec
            for i in np.arange(2, n + 1):
                fn[i] = Decimal(fn[i - 1]) + Decimal(fn[i - 2])
    else:
        for i in np.arange(2, n + 1):
            fn[i] = fn[i - 1] + fn[i - 2]

    if output is 'last' or output is not 'array':
        return fn[-1]
    else:
        return fn


def three_n_one(n):
    r"""
    Computes the famous :math:`3n + 1` sequence, also known as the Collatz conjecture.

    Parameters
    ----------
    n : int
        Starting integer to begin :math:`3n + 1` process.

    Returns
    -------
    sequence : list
        The sequence generated by the Collatz conjecture. If n is 1, 1 is returned.

    Notes
    -----
    The Collatz conjecture, also known as the :math:`3n + 1` problem, is a currently
    unsolved problem in number theory that is stated as:

    - Start with a positive integer :math:`n`
    - If :math:`n` is even, divide :math:`n` by 2
    - If :math:`n` is odd, multiply by 3 and add 1 to obtain :math:`3n + 1`
    - Repeat this process until the sequence reaches 1

    References
    ----------
    3x + 1 problem. (2017, May 13). In Wikipedia, The Free Encyclopedia.
        from https://en.wikipedia.org/w/index.php?title=3x_%2B_1_problem&oldid=780191927

    Moler, C. (2011). Numerical computing with MATLAB (1st ed.).
        Philadelphia, Pa: Society for Industrial & Applied Mathematics.

    """
    if n == 1:
        return 1.0

    sequence = []

    while n > 1:
        if iseven(n):
            n /= 2.0
            sequence.append(n)
        else:
            n = 3 * n + 1
            sequence.append(n)

    return sequence
