euler.py

from math import sqrt
from collections import Counter

def memoize(f):
    results = {}
    def helper(x):
        if x not in results:            
            results[x] = f(x)
        return results[x]
    return helper

primes = []
def gen_prime():
    for i in primes:
        yield i

    if not primes or primes[-1] < 2:
        i = 2
        primes.append(i)
        yield i
    
    i += 1
    if i % 2 == 0:
        i += 1
    while True:
        sqrt_i = int(sqrt(i))
        for j in primes:
            if j > sqrt_i:
                primes.append(i)
                yield i
                break
            elif i % j == 0:
                break                
        i += 2

def get_primes():
    return primes

def old_gen_prime():
    primes = []
    i = 2
    primes.append(i)
    yield primes[-1]
    
    i = 3
    while True:
        for j in primes:
            if j * j > i:
                primes.append(i)
                yield primes[-1]
                break
            elif i % j == 0:
                break                
        i += 2

def old_get_factors(x):
    factors = []
    f = 2
    while f * f <= x:
        while x % f == 0:
            factors.append(f)
            x /= f
        f += 1
    if x != 1:
        factors.append(x)
    return factors

def get_factors2(x):
    sqrt_x = int(sqrt(x))
    factors = []
    for p in gen_prime():
        while p <= sqrt_x and x % p == 0:
            factors.append(p)
            x //= p
            sqrt_x = int(sqrt(x))
        if p * p > x:
            break
    if x != 1:
        factors.append(x)
    return factors

def greatest_common_divisor(a, b):
    while True:
        c = a % b
        if c == 0:
            return b
        a, b = b, c

def get_factors3(x):
    factors = []
    for f in gen_prime():
        while f * f <= x and x % f == 0:
            factors.append(f)
            x //= f
        if f * f > x:
            break
    if x != 1:
        factors.append(x)
    return factors

_factors_cache = {}
def get_factors4(x):
    if x in _factors_cache:
        return _factors_cache[x]
    original_x = x
    factors = []
    for f in gen_prime():
        while f * f <= x and x % f == 0:
            factors.append(f)
            x //= f
            # if x in _factors_cache:
            #     factors.extend(_factors_cache[x])
            #     _factors_cache[original_x] = factors
            #     return _factors_cache[x]
        if f * f > x:
            break
    if x != 1:
        factors.append(x)
    _factors_cache[original_x] = factors
    return factors

@memoize
def get_factors5(x):
    factors = []
    for f in gen_prime():
        while f * f <= x and x % f == 0:
            factors.append(f)
            x //= f
        if f * f > x:
            break
    if x != 1:
        factors.append(x)
    return factors

@memoize
def get_factors(x):
    factors = []
    for f in gen_prime():
        while f * f <= x and x % f == 0:
            factors.append(f)
            x //= f
        if f * f > x:
            break
    if x != 1:
        factors.append(x)
    return factors

def canonical_decomposition2(x):
    '''
    Returns dictionary where keys are primes and values are exponents.

    [(prime, p[prime]) for prime in sorted(p)]
    '''
    factors = {}
    for factor in get_factors2(x):
        try:
            factors[factor] += 1
        except KeyError:
            factors[factor] = 1
    return factors

def canonical_decomposition3(x):
    '''
    Returns dictionary where keys are primes and values are exponents.

    [(prime, p[prime]) for prime in sorted(p)]
    '''
    factors = {}
    for factor in get_factors2(x):
        if factor not in factors:
            factors[factor] = 0
        factors[factor] += 1
    return factors

def canonical_decomposition4(x):
    '''
    Returns dictionary where keys are primes and values are exponents.

    [(prime, p[prime]) for prime in sorted(p)]
    '''
    factors = Counter()
    for factor in get_factors2(x):
        factors[factor] += 1
    return factors

def canonical_decomposition5(x):
    factors = Counter()
    for f in gen_prime():
        while f * f <= x and x % f == 0:
            factors[f] += 1
            x //= f
        if f * f > x:
            break
    if x != 1:
        factors[x] += 1
    return factors

def canonical_decomposition(x):
    factors = {}
    for f in gen_prime():
        while f * f <= x and x % f == 0:
            if f not in factors:
                factors[f] = 0
            factors[f] += 1
            x //= f
        if f * f > x:
            break
    if x != 1:
        if x not in factors:
            factors[x] = 0
        factors[x] += 1
    return factors

def gen_triangular():
    i = 0
    n = 1
    while True:
        i += n
        yield i
        n += 1

def direct_fibonacci(n):
    '''
    This is likely not accurate for other than small n.
    '''
    phi = (sqrt(5) + 1.) / 2.
    return int(round((phi ** n) / sqrt(5)))   

from math import sqrt, log, ceil
phi = (sqrt(5) + 1.) / 2.
def term_of_ndigits_fibonacci(ndigits):
    return int(ceil((log(sqrt(5)) + (ndigits - 1) * log(10)) / log(phi)))

def gen_fibonacci():
    a, b = 0, 1
    while True:
        a, b = b, a + b
        yield b

def gen_even(gen):
    for i in gen:
        if i%2 == 0:
            yield i

def gen_lte(gen, n):
    for i in gen:
        if i > n:
            break
        yield i

def gen_lt(gen, n):
    for i in gen:
        if i >= n:
            break
        yield i

def gen_n(gen, n):
    for i in gen:
        if n <= 0:
            break
        yield i
        n -= 1

def make_square_roots(n):
    return map((lambda x: (x*x, x)), range(n))

def product(x):
    n = 1
    for i in x:
        n *= i
    return n