Various utilities for solving project euler problems

util.py

# Useful stuff

from operator import mul


def prod(x):
    """ Product reducer """
    return reduce(mul, x, 1)


def count(x):
    """ Counting reducer """
    return sum(1 for i in x)


def fact(n):
    """ Factorial """
    return prod(range(1, n + 1))


def isqrt(n):
    """ Integer square root """
    x, y = n, (n + 1) / 2
    while y < x:
        x, y = y, (y + n / y) / 2
    return x


def nPr(n, k):
    """ Number of Permutations """
    return fact(n) / fact(n - k)


def nCr(n, k):
    """ Number of Combinations """
    return nPr(n, k) / fact(k)


def gcd(a, b):
    """ Greatest common divisor """
    while b != 0:
        a, b = b, a % b
    return a


def lcm(a, b):
    """ Least common multiple """
    return a * b / gcd(a, b)


def coprime(a, b):
    """ Return true if a and b are coprime """
    return gcd(a, b) == 1


def seive(n):
    """ Return a list containing positional primes and 0s """
    primes = list(range(n))
    primes[1] = 0  # 1 is not prime
    for i in range(int(n**.5) + 1):
        if primes[i]:
            for j in range(i*2, n, i):
                primes[j] = 0
    return primes


def filter_seive(n):
    """ Return a list of primes under n """
    return filter(None, seive(n))


def factor(n):
    """ Return a list of prime factors of n """
    factors = []
    for i in range(2, int(n**.5) + 1):
        while n % i == 0:
            factors.append(i)
            n /= i
    if n > 1:
        factors.append(n)
    return factors


def divisor(n):
    """ Return a list of all proper divisors of n """
    divisors = [1] if n > 1 else []
    for i in range(2, int(n**.5) + 1):
        if n % i == 0:
            divisors += [i, n/i]
    return list(set(divisors))


def is_triangle(v):
    """ Is this a triangle number """
    s = 8*v + 1
    return isqrt(s)**2 == s


def is_pentagonal(v):
    """ Is this a pentagonal number """
    f = 24 * v + 1
    s = isqrt(f)
    if s**2 != f:
        return False
    return s % 6 == 5


def is_hexagonal(v):
    """ Is this a hexagonal number """
    f = 8*v + 1
    s = isqrt(f)
    if s**2 != f:
        return False
    return s % 4 == 3


class Triangle(object):
    """ Iterate over triangle numbers """
    def __init__(self, start=0):
        self.count = start
        self.value = sum(range(self.count))

    def __iter__(self):
        return self

    def next(self):
        self.count += 1
        self.value += self.count
        return self.value


class Collatz(object):
    """ Iterate a Collatz sequence """
    def __init__(self, start):
        self.value = start * 2  # HAX

    def __iter__(self):
        return self

    def next(self):
        if self.value <= 1:
            raise StopIteration()
        if self.value % 2 == 0:
            self.value /= 2
        else:
            self.value = 3 * self.value + 1
        return self.value


class Fibonacci(object):
    """ Iterate the Fibonacci sequence """
    def __init__(self):
        self.a = 0
        self.b = 1

    def __iter__(self):
        return self

    def next(self):
        self.a, self.b = self.b, self.a + self.b
        return self.a