2017-06-14

Project Euler Problem 12

Finding divisors of summed natural numbers. This time I'm creating a function for doing the divisor checking. Just as in atleast one previous problem, this is a problem which can be solved with a mathematical sieve. Since my math skills obviously aren't good enough I took help from google and found a way to, by using the square root of the number to be checked, calculate the number of divisors of a triangle number. As so often in math, when you have the solution it's all so obvious.






 My math skills and patience weren't as good as they should have been for this problem. Programatically it worked out though!



number = 0

def number_of_divisors(val):
    divisors = 0    for y in range(1, int(val ** 0.5)):
        if val % y == 0:
            divisors += 2
    return divisors


for x in range(0, 10 ** 10):
    if number_of_divisors(number) > 500:
        print(number)
        break    number += x


 /Ludvig

2017-06-13

Project Euler Problem 11

First let's format the grid to fit in a list. I do this by copying it into Excel and replace all " " with "," and then copy it into a list. Since the position in the grid matters, actually I might need a two dimensional list. How do they work? Stack overflow helps out.

Now that I've though about it, there must be a better way of reading data into a Python list. And there is! I copy the data into a textfile and then read the textfile.


lines = []

with open('pe11.txt') as file:
    for line in file:
        lines = file.read().splitlines()

This is not enough though, I want a two dimensional matrix. I need to know how to add space separated values from a textfile to a Python list.







with open('pe11.txt', 'r') as file:
    lines = [[int(num) for num in line.split()] for line in file]

product = 1rowProduct = 1colProduct = 1diaDownProduct = 1diaUpProduct = 1
for row in range(0, 20):
    for col in range(0, 17):
        newProduct = lines[row][col] * lines[row][col + 1] * lines[row][col + 2] * lines[row][col + 3]
        if newProduct > rowProduct:
            rowProduct = newProduct
            rowResult = [lines[row][col], lines[row][col + 1], lines[row][col + 2], lines[row][col + 3], 'row:', row, 'col', col, 'row product', rowProduct]

for col in range(0, 20):
    for row in range(0, 17):
        newProduct = lines[row][col] * lines[row + 1][col] * lines[row + 2][col] * lines[row + 3][col]
        if newProduct > colProduct:
            colProduct = newProduct
            colResult = [lines[row][col], lines[row + 1][col], lines[row + 2][col], lines[row + 3][col], 'row:', row, 'col', col, 'col product', colProduct]

for row in range(0, 17):
    for col in range(0, 17):
        newProduct = lines[row][col] * lines[row + 1][col + 1] * lines[row + 2][col + 2] * lines[row + 3][col + 3]
        if newProduct > diaDownProduct:
            diaDownProduct = newProduct
            diaDownResult = [lines[row][col], lines[row + 1][col + 1], lines[row + 2][col + 2], lines[row + 3][col + 3], 'row:', row, 'col', col, 'dia down product', diaDownProduct]

for row in range(0, 17):
    for col in range(0, 17):
        newProduct = lines[row + 3][col] * lines[row + 2][col + 1] * lines[row + 1][col + 2] * lines[row][col + 3]
        if newProduct > diaUpProduct:
            diaUpProduct = newProduct
            diaUpResult = [lines[row + 3][col], lines[row + 2][col + 1], lines[row + 1][col + 2], lines[row][col + 3], 'row:', row, 'col', col, 'dia up product', diaUpProduct]

print(rowResult, "\n", colResult, "\n", diaDownResult, "\n", diaUpResult)

resultList = [rowProduct, colProduct, diaDownProduct, diaUpProduct]
print(max(resultList))


The codes are growing! It feels like this problem should be solvable in a more elegant way both mathematically and programatically. I'll go with this solution for now and maybe turn back in the future to try a new way (if I learn one).

/Ludvig

2017-06-12

Project Euler Problem 10

For this problem I'm going to try to reuse the code I wrote for problem 7. Problem 7 was about finding the 10001th prime number, so this is more or less a prime number calculator and should be usable for problem 10.

t = 0listOfPrimes = [2]
for numerator in range(3, 200000, 2):
    if numerator % 2 != 0:
        for x in range(0, len(listOfPrimes)):
            if numerator % listOfPrimes[x] == 0:
                t += 1        if t == 0:
            listOfPrimes.append(numerator)
        else:
            t = 0    print(len(listOfPrimes), numerator)
    if len(listOfPrimes) == 10001:
        break
print("10001th prime: ", listOfPrimes[10000])

My intuition says that this problem will take quite some running time to complete, let's see!

I've done some modifications of the code above to make it work theoretically. What annoys me is that it takes so long time to run the algorithm, so I think I'm gonna see how other people solved problem 7 to maybe get some inspiration for a better way. This takes way too long, so I'm going to program the sieve of Eratosthenes algorithm for prime number calculation. On the Euler Project forum, the people who use this algorithm solves problem 7 in (milli)seconds.



It annoys me only a little, but what I did to solve this problem was to find a fast solution for problem 7 from the Project Euler forum and then modify it. The code I chose was posted by onoki_li in May 2017. I then modified it to add all found primes to a list until the next prime was larger than 2,000,000. What bothers me is that I didn't come up with the code myself, but I rationalize it with that this is for Python and not math learning.



from math import sqrt

def is_prime(x):
    for j in range(2, int(sqrt(x)) + 1):
        if x % j == 0:
            return False            break    return True
i = 0m = 1listOfPrimes = []


while m < 2000001:
    m += 1    if is_prime(m):
        listOfPrimes.append(m)

print(sum(listOfPrimes))

/Ludvig

2017-06-11

Project Euler Problem 9

Hola!

Another day, another problem. What's new in this solution is the built-in function is_integer() which I use to check if a float number has no decimal value. For example when c = 5.0, c.is_integer() returns true and when c = 8.3, c.is_integer() returns false. It was a good help since most square roots aren't integers.

product = 1c = 0
for a in range(1, 1000):
    for b in range(1, 1000):
        c2 = a ** 2 + b ** 2        c = c2 ** 0.5        abcSum = a + b + c
        if c.is_integer() and abcSum == 1000:
            c = int(c)
            print("a: ", a, "b: ", b, "c:", c, "sum", abcSum)
            product = a * b * c
            break    if abcSum == 1000:
        break
print("product:", product)



/Ludvig

2017-06-10

Project Euler Problem 8

In the last post I wrote about finding a feature for measuring the run time for an algorithm. It seems as though I either need to install plugins for PyCharm or I need to upgrade to a commercial version of it. I'll leave it for now.

Now it's time for problem 8:


What I'm going to do is to cut out 13 digits from the number, multiply them, save the product, and then doing the same thing after shifting the 13 digits one to the right. Instead of saving every product, I'll compare the new one and the current one and only save the larger one.


From now on, I'll stop posting the problems here on the blog and let you read the problem yourself on ProjectEuler.net instead.

The code I used for this problem is:

fullNumber = '731671765313306249192....' # insert numbers hereproduct = 1newProduct = 1
for x in range(0, 987):
    for y in range(x, x+13):
        newProduct *= int(fullNumber[y])
    if newProduct > product:
        product = newProduct
    newProduct = 1
print("product: ", product)

2017-06-09

Project Euler Problem 7

The problem:

"By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?"

Time to make a for loop that checks if a number is a prime or not.With this code, I seem to be able to calculate prime numbers in a correct way. The problem is that it is incredibly slow.

t = 0listOfPrimes = [2]
print("length", len(listOfPrimes))
for numerator in range(3, 200000, 2):
    for x in range(2, numerator):
        if numerator % x != 0:
            for y in range(0, len(listOfPrimes)):
                if numerator % listOfPrimes[y] == 0:
                    t += 1            if t == 0:
                listOfPrimes.append(numerator)
                break            else:
                t = 0    print(len(listOfPrimes))
    if len(listOfPrimes) == 10001:
        break

print("prime no 10001: ", listOfPrimes[10000])

I'm going to rearrange is order of the for-loops to increase the speed of calculation. This didn't make it faster... Now I'm going to try to see if I can limit the modulus checks even more. I've read something somewhere about prime numbers are not dividable by 2 (except the prime number 2) or by any prime numbers that are smaller than the square of the number the is being checked. Wow, I've made a huge miss. I though 10001 was one hundred thousand and one instead of ten thousand and one. Well well, here is my code for finding the 10001th prime:

t = 0listOfPrimes = [2]
for numerator in range(3, 200000, 2):
    if numerator % 2 != 0:
        for x in range(0, len(listOfPrimes)):
            if numerator % listOfPrimes[x] == 0:
                t += 1        if t == 0:
            listOfPrimes.append(numerator)
        else:
            t = 0    print(len(listOfPrimes), numerator)
    if len(listOfPrimes) == 10001:
        break
print("10001th prime: ", listOfPrimes[10000])

I'd like to have a feature in PyCharm that shows the time it took to run an algorithm.

/Ludvig

2017-06-08

Project Euler Problem 6

The problem:

"The sum of the squares of the first ten natural numbers is,
12 + 22 + ... + 102 = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)2 = 552 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum."

To do a square in Python, two * is used: "**". This time I'm going to be a little more detailed about how I produce the correct answer. First I reproduce the example given:

sumOfSquares = 0sumToSquare = 0squareOfSum = 0difference = 0
for x in range(1,11):
    sumOfSquares += x ** 2    print(sumOfSquares)

for y in range(1,11):
    sumToSquare += y
    print(sumToSquare)

squareOfSum = sumToSquare ** 2print(squareOfSum)
difference = squareOfSum - sumOfSquares
print(difference)

Not a very nice code, but it works. Then I change the upper limits in the two for-loops to 101 instead of 11 and put it into the website to verify that I've got it right.

Then I try to make the code look better. This I do because I think it's a good way to learn. Maybe I can do it all in just one for-loop? Let's try. As I've read somewhere, it seems that it's good programming practise to make the code easy to read instead of just doing it on as few lines as possible, so here we go with a more compact, and probably more effective, version:

sumOfSquares = 0sumToSquare = 0squareOfSum = 0difference = 0
for x in range(1,101):
    sumOfSquares += x ** 2    sumToSquare += x

squareOfSum = sumToSquare ** 2difference = squareOfSum - sumOfSquares
print(difference)

/Ludvig