Project Euler

What is the easiest way to study for a programming exam?

Program. It's as simple as that! So after finishing up assignment 2 part 1 (which seems unsettlingly easy) I decided to dive into some programming problems in order to practice some of the concepts I will need to know for the test. These problems are courtesy of a website called Project Euler, which is essentially a huge database of math problems that (mostly) require a computer to solve.

Problem 1, Square Root Convergents:

It is possible to show that the square root of two can be expressed as an infinite continued fraction.
 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...
By expanding this for the first four iterations, we get:
1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...
The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.
In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

So to solve this I need to have some way to keep track of numerators and denominators, to reduce successive fractions, to check if the numerator has more digits than the denominator, and to find the next iteration of the continued fraction expansion.

So what I did was I made a Fraction class, which has two attributes: a numerator, and a denominator. Then I noticed that for every iteration, we add 1 to the entire thing, put it as the denominator of a fraction (which convieniently is a reciprocal, and then just add 1 again. As an example, if we have our first iteration, which is 3/2 and we add 1 to it we get 5/2, the reciprocal of that is 2/5, and then 1 added to that is 7/5 which is our second iteration. Then we do it again, add 1 to get 12/5, reciprocal is 5/12, add 1 to get 17/12 which is our third iteration. So all I did was make a new fraction by adding the denominator to the numerator, switching the variables, and then adding the denominator in the new fraction to the numerator.

Then all that was needed was to make a simple list comprehension that did all of these fraction expansions and reduced them on every successive iteration. Followed by a filtering of the list by reading the length of the numerator.

This gives the final answer of 153.

Problem 2, Multiples of 3 and 5:

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 1000.

This is the very first problem on the site, which is incredibly easy to solve however in order to practice the concepts, it makes for a good problem since you can write it in one line.

The natural thought process is that to solve it we must iterate through all the numbers from 1 to 999, take out the ones that are multiples of 3 or 5, and then sum all of these together. The way I originally solved it was with an accumulator, and the code looked something like this:

total = 0
for num in range(1, 1000):
        if num%3 == 0 or num%5 == 0:
                total += num
print(num)

So how could we do this in one line? Well with list comprehensions of course! To get a list with all of the numbers that have this property, we can write it like this:

[num for num in range(1, 1000) if num%3 == 0 or num%5 ==0]

So all we need to do is sum them up, and print them, which gives us the one-line beauty:

print(sum([num for num in range(1, 1000) if num%3 == 0 or num%5 ==0]))

Which gives us the final answer of 233168.

Problem 3, Largest Prime Factor:

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

So, can this one be written in one line? Let's first think of what we can do to solve this.

Every number can be divided into prime factors, for example 10 can be written as 2x5. The natural thing to do would be to iterate over the prime numbers, and if they divided our number, we divide our number by that, and add that factor to the list. We would then stop iterating when we get to a number that is higher than the number ours has become, and the number we are left over with is in fact the largest prime factor.

Now the truth is, with this implementation, we CANNOT write it in one line, since it requires a variable to be set to 600851475143 for us mess with among other factors. However we can actually write a one line program for this, (although it may not fit on one line on this blog):

print(max([factor for factor in range(2, 600851475143) if (600851475143%factor==0 and len([n for n in range(2, factor) if factor%n == 0]) == 0)]))

What it is basically doing is populating a list of numbers that divide 600851475143 evenly, and which cannot be divided evenly by any number other than 1 and itself (i.e. the list of numbers that divide this number between 2 and itself-1 has a length of 0). After that it simply prints out the largest number in that list, which is by definition our "largest prime factor".

The thing is though, this is a HORRIBLE program, and would take a long time to run even on a supercomputer (In fact, trying it myself it generates a memory error before it gets anywhere). So there is a lesson here, SOMETIMES ONE LINE PROGRAMS ARE NOT THE BEST PROGRAMS.

Anyways, implementing the originally stated algorithm, I got the correct answer of 6857 in a much, much faster time, less than a second.