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())
 
euler7(10001)

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

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

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)))
 
euler9(1000)

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