python

projecteuler / python — 4 Comments
4
Jan 10

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

Problem Statement

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Notes

This is a relatively simple list comprehension problem. Probably the only interesting aspect here is the way a number is checked for being a palindrome – ie. the test str(x*y) == str(x*y)[::-1]

For testing for palindrome we convert the number into a string. We subsequently reverse the string (the [::-1] slice). If both are same then the underlying number is a palindrome.

Solution

1
2
3
4
print max(x * y
    for x in xrange(100,1000)
        for y in xrange(100,1000)
            if str(x*y) == str(x*y)[::-1])
projecteuler / python — Comments Off
4
Jan 10

The largest prime factor of the number 600851475143

Problem Statement

We need to compute the largest prime factor of a particular number – in this case 600851475143

Notes

We define a new prime factors generator which generates all the prime factors of a particular number (not including 1). After that it is trivially easy to use the max function around its results to find the maximum prime factor.

To generate the prime factors we use a while loop on the number itself being greater than 1. The reason we do that is that once we find a prime factor, we divide the number by the prime factor, and continue further processing with the number being now set to the quotient of the division.

One usually only needs to search within 1 and the square root of a number to find a factor (since one of any two factors of a number is always less than the square root of the number). Since we use it in the range operator (which is non inclusive of the upper end) we add 1.0 to it.

However there are situations when the number itself is a prime number. We would like to return the number in such a case – but that is clearly not an option when the for loop continues only until the square root of the number. Hence we use the chain function from the itertools library to chain a sequence with the number itself at the end of the for loop (which itself is another generator). The chain operator effectively creates a continuous sequence spanning the first and the second generator. We only take the first element from this combined sequence and yield it (as a generated value). That value is the lowest prime factor for the number. Having yielded the prime factor, we divide the number by that factor and resume processing on the quotient.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from itertools import chain

# A function which just takes the first value from a generator
# and ignores the rest
def first(gen):
    try:
        return gen.next()
    except StopIteration :
        return None

# A generator to return the prime factors of a number
def prime_factors(n):
    while n > 1 :
        ff = first(val for val in chain(
                        xrange(2,int(n**0.5+1.0)),[n]) if n % val == 0)
        yield ff
        n = n / ff

# Actual computation
print max(prime_factors(600851475143))
projecteuler / python — 2 Comments
4
Jan 10

Find the sum of all the even-valued terms in the sequence which do not exceed four million

Problem Statement

Each new term in the Fibonacci sequence is generated by adding the previous two terms.
By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Notes

In this case we shall write a method fib() for generating a fibonacci sequence. However in order to keep the sequence open ended (infinite), we shall use a generator. This allows us to use the necessary memory only on demand. However we do need to terminate the sequence generation at some point. In this case when the generated numbers exceed four million. For this we define a method until(gen,predicate) which is also a generator which wraps another generator (in this case fib()), but also accepts a predicate which acts as a stop condition for further generation when the predicate evaluates to True. Update: Changed to using itertools.takewhile per Navin’s suggestion in comments. We supply the predicate itself as a lambda which has a condition check for value exceeding four million. Finally in order to add only the even values in the series, we use the for loop on the generator followed by an if condition to test whether the generated value is even.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
from itertools import takewhile

def fib():
    """ Fibonacci series generator """
    x = 1
    y = 1
    while True :
        x,y = y,x+y
        yield x

# Actual Solution
print sum(val for val in takewhile(lambda x : x <= 4000000,fib()) if val%2 ==0)
projecteuler / python — Comments Off
4
Jan 10

Find the sum of all the multiples of 3 or 5 below 1000

Problem Statement

The various multiples of either 3 and / or 5 between 1 and 20 are 3, 5, 6, 9, 10, 12, 15 and 18. The sum of all these values is 78. Similarly we are required to find the sum of all the multiples of 3 and / or 5 between 1 and 1000.

Notes

We use a simple list comprehension using a for loop with a if condition as filter and add up all the elements in the sequence using the sum function.

Solution

1
2
3
print sum((
    i for i in xrange(1,1000)  
        if i % 3 == 0 or i % 5 == 0))
Newer Entries →