Project Euler Problem 3

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

What is the largest prime factor of the number 600851475143?

The trick in this problem is to divide out the value of d (in this case a number) if the remainder is 0. By doing this, you deal the other values that could be divisible by 2 such as 4 and 8. And this value of d must be appended to an array of factors. An array which is basically tracking the values that divide into n.

def largest_factor(n):
    factor = []
    d = 2
    while n > 1:
        while n % d == 0:
            factor.append(d)
            n /= d
        d +=1
    return factor

This second snippet of code runs the function and gets the result, but you still have to call the max function on the array to obtain the largest value which is the answer to this problem.

answer = largest_factor(600851475143)
max_value = max(answer)
print max_value

Project Euler Problem 2: Fibonacci Sequence

Problem #2:

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, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

The key to this problem is to understand the Fibonacci sequence. If you can write down the sequence on paper for the first 2-3 iterations writing the code shouldn’t be too hard. As you see below I start with the first two terms at 0, and 1. I add them up store them in a variable, and check if it’s divisible by 2 (checking if it’s even), and if it is I add the result to the final solution.

def fib():
    answer = 0
    first = 0
    second = 1
    while(second < 4000000):
        temp = first
        first = second
        second = temp + first
        if second % 2 == 0:
            answer += second
    return answer

print fib()

Project Euler Problem #1

From time to time I live to solve programming problems I find online. I find them to be a good brain exercise, and it keeps me sharp. One of the sites I like to use is Project Euler the problems found here are  mathematical in origin compared to other types you could do (but don’t worry I do plenty of those also).

So every so often expect a post like this one in which I dissect a Project Euler problem, and give my solution. It should be fun, and I hope you enjoy it as much as I do. Don’t worry my other type of content isn’t going to disappear.

Problem #1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

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

Note: I do understand there are more efficient solutions to the one’s I have written, and perhaps sometime in the foreseeable future I will go back, and write a more efficient solution.

This problem is simple enough we are looking for the sum of the numbers that are multiples of either 3 or 5 that are within 100.

Except I am going to go a little further let’s say we want to find the sum of all the numbers that are multiples of 3 or 5 less than N. This N could be 50, 100, or 2,000 it’s a place holder value in a sense. Those who are familiar with mathematical notation will recognize.

from sys import argv
n = argv[1]

This code is written to handle the command line argument so that we can run the program as follows.
python file.py [ARG]
Nothing fancy it’s just there to handle the input of the value of n.

So to solve this problem the approach is simple. We simply loop until n, and while doing so we test each value 0….N and if it’s divisible by 3 or 5 we add it to the sum. We check this by using modulus operation which returns the remainder of the two arguments. For example 42 % 2 = 0 because 42 is divisible by 2 without remainder. Thus we want to test if a number let’s call it x if x % 3 = 0 or x % 5 = 0 we know we are on the right track.

def problem1(n):
    """
    Find the sum of multiples of 3 and 5 less than n
    """
    n = int(n)
    answer = 0
    for n in range(0, n):
        if n % 3 == 0 or n % 5 == 0:
            answer += n
    return answer

print problem1(n)

If your confused by the or statement I used I did that to save time. You could have easily written two if statements testing each of the two conditions, but I am lazy, and wrote it all on one line saving me the effort. As you can see this is actually a pretty straightforward problem. Yet this isn’t the most efficient solution. If I ever get around to writing it myself you can expect another post on the matter.