Thursday, June 7, 2012

Project Euler 35

The problem description of Project Euler's 35th problem is as follows:

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
How many circular primes are there below one million?

I choose to solve this problem in a rather functional way so all you will need to do is get a list of all of the primes below 1 million and a function that simply tells if a prime is a circular prime or not. The method that I used to get the primes is the Sieve of Eratosthenes. This is just about the best way to generate primes for almost any project euler problem as it is very fast for generating the primes up to about 10 million, after that there are faster methods which you can employ if you ever need to. The code for just generating the primes is as follows:




def generate_primes(end):
    primes = range(end)
    for i in range(2,len(primes)):
        if primes[i]: #This if statement never fires if we have already 'crossed' the prime out
            for j in range(2*i,end,i):
                primes[j] = None #crosses the prime out
        if i**2 > end:
            return filter(None,primes[2:]) #This simply filters out all of the Nones in the list           

Next we need the function which tells if a prime is circular. I am going to make the assumption here that the list of primes that I have are all represented as strings, trust me it will be very simple if we make this assumption:

def is_circular(prime):
    for i in range(len(prime)):
        if prime[i:] + prime[:i] not in primes:      
            return 0
    return 1

A refresher on how python handles string splicing: string[2:] will copy starting at the third letter and going to the end of the string while string[:2] will start at the first letter of the string and go to the third letter.

So the first time through the for loops prime[i:] will be prime[0:] which copies the entire string while prime[:0] copies nothing. In this way each letter of the string is rotated to the front and the entire string is matched against our current list of primes. If it ever is not found then false is returned. If the for loop runs all the way through true is returned.

So putting it all together we get:


def generate_primes(end):
    primes = range(end)
    for i ∈ range(2,len(primes)):
        if primes[i]:
            for j ∈ range(2*i,end,i):
                primes[j] = None
        if i**2 > end:
            return filter(None,primes[2:])           
        
def euler35():
    def is_circular(prime):
        for i ∈ range(len(prime)):
            if prime[i:] + prime[:i] ¬∈ primes:      
                return 0
        return 1
        
    primes = map(str,generate_primes(10**6))
    circulars = filter(is_circular,primes)   
        
    return len(circulars)
            
print euler35()
Which works at a horribly inefficient time of 5 minutes... Fortunatly there is a solution. Past the primes 2 and 5 every prime ends in 1, 3, 7 or 9 and because each digit in a circular prime is rotated to the last digit at least once we can throw out every prime that contains a 2, 4, 5, 6, 8 or 0. This turns out to be a substantial number, and not only do we never have to check if these are circular, but when checking to see if a number exists in the list of primes having a smaller list greatly reduces the computational cost. So here is my final solution, which runs in only 2 seconds.
def generate_primes(end):
    primes = range(end)
    for i ∈ range(2,len(primes)):
        if primes[i]:
            for j ∈ range(2*i,end,i):
                primes[j] = None
        if i**2 > end:
            return filter(None,primes[2:])           
        
def euler35():
    def is_circular(prime):
        for i ∈ range(len(prime)):
            if prime[i:] + prime[:i] ¬∈ primes:      
                return 0
        return 1
        
    primes = filter(lambda x: x.count('1') + x.count('3') + x.count('7') + x.count('9') == len(x),map(str,generate_primes(10**6)))
    #idea to filter that junk out attributed to njlytoh in project euler fourms
    circulars = filter(is_circular,primes)   
    circulars += ['2','5'] #these are added because they were originally thrown out
        
    return len(circulars)
            
print euler35()
Hope you enjoyed it!

Monday, June 4, 2012

Project Euler 56

The problem description that Problem 56 gives is as follows:
A googol (10100) is a massive number: one followed by one-hundred zeros; 100100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.
Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?
 This problem really shows off how sucinctly python can solve some of the problems, especially without having to worry about producing these insanely large numbers. If this was to be done in c you would have to deal with all sorts of problems with having numbers that are too big, and with java you would have to pull out BigInt. I ended up solving this problem in two lines of python.


from itertools import product

print max(map(lambda x: sum(map(int,str(x[0]**x[1]))), product(range(1,100),range(1,100))))
This solves the problem, and at a skimpy 1 second to boot. However while it is cute to solve problems in one or two lines, it is by no means pretty or easy to understand. So lets expand this a bit and see if we can make it more readable
from itertools import product

# for example this takes in (90,90) returns 360 
sum_of_digits = lambda x: sum(map(int,str(x[0]**x[1])))
#generates a list from (90,90),(90,91) to (99,98),(99,99)
numbers_to_check = product(xrange(90,100),xrange(90,100))

print max(map(sum_of_digits,numbers_to_check))
So the first variable you see turns out to actually be a function. Lambda is a keyword that simply creates a new function on the fly, it is heavily used in functional style programming. If you find this line confusing I will write out an equivilant, but more verbose way of accomplishing the same thing:

def sum_of_digits(x):
   sum = 0
   number = x[0] ** x[1] #Takes the product. ex: (3,2) -> 9
   string = str(number) #turns it into a string ex: 9 -> "9"
   for digit in string:
      sum += int(digit)
   return sum
This may look more familiar, and if the first line was confusing I would highly recommend trying to puzzle out what each part of it does before reading my explination below, it is not too long and figuring something out on your own is one of the most gratifiying parts of learning!






So as you must have realized the for loop must have gone somewhere, that is where the map function comes into play. The map function takes a function as its first argument (here the function int()) and something it can loop over for its second (here a string). Then it applies that function to each of the elements and returns a new list that contains the results. So for example "123" turns into [1,2,3]. Very handy.

The second line, leverages the product function from itertools. hopefully my comment shows what the function does, if it does not please refer to the python documentation, it explains it very well.

And lastly the astute reader will have noticed that I changed from iterating from 1 to 100 to 90 to 100. I made the assumption that the larger the a and b variables are the larger a^b will be, a pretty safe assumption! It turns out that this is correct and my computation now runs in only 0.02 seconds.

As always, any comments or questions are more than welcome.


 EDIT:


Nolen Royalty has commeneted and provided what I believe to be a cleaner solution. It is as follows:

print max(sum(map(int, str(i**j))) for i in range(100) for j in range(100))

Or for people who don't like one liners:
answer = 0
for i in range(100):
   for j in range(100):
      answer = max(sum(map(int, str(i**j))),answer)
print answer