from math import sqrt

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

def lcm(a, b):
    return (a * b) / gcd(a, b)

def is_palindrome(num):
    digits = str(num)
    for i in range(len(digits) / 2):
        if digits[i] != digits[len(digits) - 1 - i]:
            return False
    return True

def get_factors(num):
    factors = []
    low = 1
    hi = num
    while low < hi:
        if num % low == 0:
            factors.append((low, num / low))
            hi = num / low
        low += 1
    return factors

def sieve_of_eratosthenes(lim):
    """Returns list of all primes <= lim."""
    sieve = range(lim + 1)
    sieve[1] = 0 # Explicitly mark 1.
    for i in xrange(2, int(round(sqrt(lim))) + 1):
        if sieve[i]:
            # If number hasn't been marked, mark all multiples of it.
            sieve[i*i : lim + 1 : i] = [0] * len(xrange(i*i, lim + 1, i))
    return filter(None, sieve) # Remove all the marks (i.e. 0s).

def get_primes(upper, lower=1):
    """Returns list of primes between upper (inclusive) and lower (exclusive)."""
    return [p for p in sieve_of_eratosthenes(upper) if p > lower]

def get_prime_factors(num):
    factors = []
    lim = 1000 # Check small chunks at a time in case num is huge.
    while num > 1:
        found_prime = False
        for prime in get_primes(lim, lower=lim-1000):
            if num % prime == 0:
                found_prime = True
                factors.append(prime)
                num /= prime
                break
        lim = (1000 if found_prime else lim + 1000)
    return factors

# TODO: Make both of these not suck. 

fib = {1: 1, 2: 2}

def get_fib(i):
    if i not in fib:
        fib[i] = get_fib(i - 1) + get_fib(i - 2)
    return fib[i]

def get_closed_fib(n):
    # NOTE: Currently not used, but may be useful.
    phi = (1 + sqrt(5)) / 2
    return ((phi ** n) - ((-1 / phi) ** n)) / sqrt(5)

collatz = {1: 1}

def collatz_length(i):
    if i in collatz:
        return collatz[i]
    collatz[i] = 1 + collatz_length(i / 2 if i % 2 == 0 else 3 * i + 1)
    return collatz[i]
