Problems 1 10

Euler 1: Add all the natural numbers below 1000 that are multiples of 3 or 5

def euler1():
    """Add all the natural numbers below 1000 that
    are multiples of 3 or 5"""
    return sum(x for x in xrange(1, 1000) if (x % 3 == 0) or (x % 5 == 0))

Euler 2: Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed one million.

def fibonacci():
    """Generate fibonnacci serie"""
    # Ugly, but the typical while loop solution is not functional
    get_next = lambda (a, b), _: (b, a+b)
    return (b for a, b in ireduce(get_next, count(), (0, 1)))
def euler2():
    """Find the sum of all the even-valued terms in the Fibonacci
    sequence which do not exceed one million"""
    candidates = takewhile(lambda n: n < 1000000, fibonacci())
    return sum(x for x in candidates if x % 2)

Euler 3: Find the largest prime factor of 317584931803

def prime_factors(num, factor=2):
    """Return all prime factors (ordered) of num in a list"""
    if num <= 1:
        return []
    candidates = chain(xrange(factor, int(sqrt(num))+1), [num])
    next = first(x for x in candidates if (num%x == 0))
    return [next] + prime_factors(num/next, next)
def euler3():
    return max(prime_factors(317584931803))

Euler 4: Find the largest palindrome made from the product of two 3-digit numbers

def icross(*sequences):
    """Cartesian product of sequences (recursive version)"""
    if sequences:
        for x in sequences[0]:
            for y in icross(*sequences[1:]):
                yield (x,)+y
    else: yield ()
def digits_from_num(num, base=10):
    """Get digits from num in base 'base'"""
    def recursive(num, base):
        if num < base:
            return [num]
        return [num%base] + recursive(num/base, base)
    return list(reversed(recursive(num, base)))
def is_palindrome(num, base=10):
    """Check if 'num' in base 'base' is a palindrome, that's it, if it can be
    read from left to right and right to left being the same number"""
    digitslst = digits_from_num(num, base)
    return (digitslst == list(reversed(digitslst)))
def euler4(lstlst):
    canditates = (mul(ns) for ns in icross(*lstlst))
    return max(ifilter(is_palindrome, canditates))
euler4(2*[range(111, 1000)])

Discussion: In the aim of implementing generic solutions, we not only consider two lists but a arbitrary number of lists. That was just an excuse to show the icross (a Cartesian product) function. Take a look at Python cookbook for further info. On the same wave, we could have reversed the number easily by transforming it to string, this approach is more pedagogical.

Euler 5: What is the smallest number divisible by each of the numbers 1 to 20?

def least_common_multiple(nums): 
    """Return least common multiples of nums"""
    return reduce(lambda a, b: a * b / greatest_common_divisor(a, b), nums)
def greatest_common_divisor(a, b):
    """Return greatest common divisor of nums"""
    return (greatest_common_divisor(b, a % b) if b else a)
def euler5():
    return least_common_multiple(xrange(1, 20+1))

Euler 6: What is the difference between the sum of the squares and the square of the sums?

def euler6(op, end):
    return op(sum(xrange(end+1))) - sum(op(x) for x in xrange(end+1))
euler6(lambda x: x**2, 100)

Euler 7: Find the 10001st prime

def isprime(n):
    """Return True if n is a prime number"""
    if n < 3:
        return (n == 2)
    elif n % 2 == 0:
        return False
    elif any(((n % x) == 0) for x in xrange(3, int(sqrt(n))+1, 2)):
        return False
    return True
def primes(start=2):
    """Generate prime numbers from 'start'"""
    return ifilter(isprime, count(start))
def euler7(n):
    return takenth(n-1, primes())

Euler 8: Find the greatest product of five consecutive digits in the 1000-digit number:


def euler8(strnum, op, length, step=1):
    return max(reduce(op, imap(int, n)) for n in get_groups(strnum, length, step))
euler8(filter(str.isdigit, number8), operator.mul, 5)

Euler 9: Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000

def is_pythagorean((a, b, c)):
    """Return True if a**2 = b**2 + c**2 (a, b, c must be integers)"""
    return (a**2 == b**2 + c**2)
def euler9(val):
    xr = xrange
    candidates = ((val-b-c, b, c) for c in xr(1, val/2) for b in xr(c, val/2))
    return mul(head(ifilter(is_pythagorean, candidates)))

Euler 10: Calculate the sum of all the primes below one million

def euler10(condition):
    return sum(takewhile(condition, primes()))
euler10(lambda p: p < 1e6)
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License