from math import log

import constants
import helper

def problem_1():
    """Find the sum of all the multiples of 3 or 5 below 1000."""
    return sum([i for i in range(1000) if i % 3 == 0 or i % 5 == 0])

def problem_2():
    """By considering the terms in the Fibonacci sequence whose values do not
    exceed four million, find the sum of the even-valued terms."""
    i = curr = total = 0
    while curr < 4000000:
        if curr % 2 == 0:
            total += curr
        i += 1
        curr = helper.get_fib(i)
    return total

def problem_3():
    """What is the largest prime factor of the number 600851475143?"""
    # NOTE: Faster by trying primes highest to lowest from sqrt(const)?
    return max(helper.get_prime_factors(600851475143))

def problem_4():
    """Find the largest palindrome made from the product of two 3-digit
    numbers."""
    # TODO: Brute force; only fast by virtue of being small. Fix.
    maximum = curr = 999 * 999
    while curr >= 100 * 100:
        if helper.is_palindrome(curr):
            for i in range(100, 1000):
                if curr % i == 0 and 999 >= curr / i >= 100:
                    return curr
        curr -= 1
    raise error('No solution to problem 4 found!')

def problem_5():
    """What is the smallest positive number that is evenly divisible by all of
    the numbers from 1 to 20?"""
    return reduce(lambda a, b: helper.lcm(a, b), range(1, 21))

def problem_6():
    """Find the difference between the sum of the squares of the first one
    hundred natural numbers and the square of the sum."""
    return (sum(range(101)) ** 2) - sum([i**2 for i in range(101)])

def problem_7():
    """What is the 10 001st prime number?"""
    # Upper bound on nth prime:
    # http://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-01037-6/S0025-5718-99-01037-6.pdf
    n = 10001
    num_primes = 0
    for lim in xrange(0, n * int(log(n) + log(log(n))), 1000):
        p = helper.get_primes(lim + 1000, lower=lim)
        if num_primes + len(p) >= 10001:
            return p[n - num_primes - 1]
        num_primes += len(p)

def problem_8():
    """Find the greatest product of five consecutive digits in the 1000-digit
    number."""
    highest = 0
    for i in range(len(constants.p8) - 4):
        prod = reduce(lambda x, y: x * y,
                      [int(ch) for ch in constants.p8[i : i + 5]])
        if prod > highest:
            highest = prod
    return highest    

def problem_9():
    """There exists exactly one Pythagorean triplet for which
    a + b + c = 1000. Find the product abc."""
    # Using Euclid's formula:
    # http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple
    # 1000 = a + b + c = (m**2 - n**2) + 2mn + (m**2 + n**2) = 2m**2 + 2mn =>
    # 500 = m**2 + mn = m (m + n)
    for f1, f2 in helper.get_factors(500):
        m, n = (f1, f2 - f1) if f2 > f1 else (f2, f1 - f2) # Avoid negatives.
        m, n = (m, n) if m > n else (n, m) # Make sure m > n.
        a, b, c = (m**2 - n**2, 2 * m * n, m**2 + n**2) # Euclid's formula.
        if a + b + c == 1000:
            return a * b * c
    raise error('No solution to problem 9 found!')

def problem_10():
    """Find the sum of all the primes below two million"""
    return sum(helper.get_primes(2000000))
