Category Archives: Python

Code Python

Project Euler: Problem 4

Problem:

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

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

Source: http://projecteuler.net/problem=4


Solution:

Before we can being to solved the problem above we first must answer the questions raised by it. In other words:

  • Palindromic Number?

 

Palindromic Number?

A palindromic number a number that is a palindrome, which is just a word or phrase that is the same in either direction.

 

Code:

Source: https://bitbucket.org/TWith2Sugars/project-euler/src/dbd1afaa7fc6/python/4.py

def isPalindrome(n):
    return (n==n[::-1])

def findLargestPalindrome():
    largest = 0
    for x in range(100,1000):
        for y in range(100,1000):
            product = x*y

            if product > largest and isPalindrome(str(product)):
                largest = product
    return largest

print(findLargestPalindrome())

 

IsPalindrome

This method is what is responsible for checking if a number is a palindrome; the “[::-1]” is what takes the parameter and reverses it. That’s it!

 

Code Python

Project Euler: Problem 3

Problem:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

Source: http://projecteuler.net/index.php?section=problems&id=3


Solution:

Before we can being to solved the problem above we first must answer the questions raised by it. In other words:

  • What is a prime number?
  • What is a factor?
  • What is a prime factor?
  • How do we find the prime factors for a number?

 

What is a prime number?

A prime number is any natural number that can only be divided by 1 or itself. E.G. 7 is a prime number because it can only be divided by 1 or 7 while 10 is not a prime number because it’s divisors are 1,2,5,10.

 

What is a factor?

A factor (also known as a divisor) is any number that that can divide in to another number and not leave a remainder. In the previous section about prime numbers you can see the for 10 it’s factors are:

  • 1
  • 2
  • 5
  • 10

 

What is a prime factor?

A prime factor is any factor that is also a prime number.

 

How do we find the prime factors for a number?

The method of finding prime factors is called Prime Factorisation.  It involves taking a number and dividing it by the smallest prime possible, then taking what’s remaining and dividing that by the smallest prime possible; keep doing this until the remainder is a prime. This Khans Academy video offers a great introduction to this concept.

 

Code:

Source: https://bitbucket.org/TWith2Sugars/project-euler/src/8892d0a39946/python/3.py

def primeNumbers(n):
    # Found this example on Wikipedia: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    # Create a candidate list within which non-primes will be
    # marked as None; only candidates below sqrt(n) need be checked. 
    candidates = list(range(n+1))

    # Square root of n
    fin = int(n**0.5)

    # Loop over the candidates, marking out each multiple.
    for i in xrange(2, fin+1):
        if candidates[i]:
            candidates[2*i::i] = [None] * (n//i - 1)

    # Filter out non-primes and return the list.
    return [i for i in candidates[2:] if i]

def primeFactors(n):
    # Generators all of the prime factors for n

    # The largest number that a prime factor could be
    maxPossiblePrimeNumber = int(n**0.5)

    # List of all prime numbers up to the square root of n
    primes = primeNumbers(maxPossiblePrimeNumber)

    while n > 1:
        for p in primes:
            # This is a prime factor
            if n % p == 0:
                # Set n to be the result of the division of n by the current prime number (p)
                n = n / p
                yield p

maxPrime = max(primeFactors(600851475143))
print(maxPrime)

The code is broken down in to two parts:

  • Generating Prime Numbers (primeNumbers)
  • Performing Prime Factorisation (primeFactors)

 

Generating Prime Numbers

There are many methods of generating prime numbers and in my search I’ve decided to use a method called Sieve of Eratosthenes which is pretty efficient are generating prime numbers below 100. It also comes with a python example that we can use. You’ll see the code below.

 

Performing Prime Factorisation

This function just implemented the method of finding prime factors as mentioned earlier, there is probably a more efficient/mathematical way of doing this but for now it’s a good start.

 

 

Code Python

Project Euler: Problem 2

Right, here is my attempt at problem 2 of project euler.

Problem: http://projecteuler.net/index.php?section=problems&id=2

source: https://bitbucket.org/TWith2Sugars/project-euler/changeset/3ec9f237dbb9

def fib(n):
    evenSum, a, b = 0, 0, 1
    while a < n:
        a, b = b, a+b
        if b % 2 == 0:
		    evenSum += b

    return evenSum;

result = fib(4000000)
print(result)

Update:

Thanks to Mohammad’s advice the code has been update to avoid pointlessly assigning variables.

def fib(n):
    evenSum, a, b = 0, 1, 2
    while a < n:
        if b % 2 == 0:
		    evenSum += b
        a, b = b, a+b
    return evenSum;

result = fib(4000000)
print(result)
Code Python

Project Euler + Python

For a while I’ve been meaning to play with python but I could never think of something to do with it; so I decided to try and solve as many problems in Project Euler as I can.

Here is my mercurial repository on bitbucket: https://bitbucket.org/TWith2Sugars/project-euler

This is my attempt at the first problem so far:

Problem: http://projecteuler.net/index.php?section=problems&id=1
source: https://bitbucket.org/TWith2Sugars/project-euler/src/813d5ec90687/python/1.py

result = 0
for i in range(1000):
    if i % 5 == 0:
	    result += i
    elif i % 3 == 0:
	    result += i

print(result)