with open('pe67.txt', 'r') as file: numbers = [[int(num) for num in line.split()] for line in file] numbersRev = reversed(numbers) for line in numbersRev: for item in range(0, len(line)): if item < len(line) - 1: a = line[item] b = line[item + 1] c = max(a, b) numbers[numbers.index(line) - 1][item] += c print(numbers[0][0])
Ludvig Learns Python is about me, Ludvig, who got interested in Python programming after being introduced to Quantopian (algorithm trading) which is built on Python programming. The scope of this blog is to document my learning process and see if it becomes more effective when I need to explain what I'm doing instead of just clicking around.
Showing posts with label project euler. Show all posts
Showing posts with label project euler. Show all posts
2017-06-22
Project Euler Problem 67
Since problem 67 was just a "harder" version of problem 18, I figured I'd try my problem 18 solution on it, and voila, it worked!
Labels:
problem 67,
project euler
2017-06-21
Project Euler Problem 18
with open('pe18.txt', 'r') as file: numbers = [[int(num) for num in line.split()] for line in file] numbersRev = reversed(numbers) for line in numbersRev: for item in range(0, len(line)): if item < len(line) - 1: a = line[item] b = line[item + 1] c = max(a, b) numbers[numbers.index(line) - 1][item] += c print(numbers[0][0])
Labels:
problem 18,
project euler
2017-06-19
Project Euler Problem 17
For this problem I want to use a dictionary
This problem took me way too long time to solve. All because of a mistake I made caused by naming my dictionaries too similarly. When I thought I was adding "hundred_and_text", I really was adding "hundreds_text". What made it really annoying is that I made my code output all the thousand numbers in words, which worked great. For troubleshooting I copied the output into excel and counted the letters in the cells which gave the correct answer, but when I used my code for counting, I missed ~300 letters. Next time I'm planning on doing something like this, I'm going to give dictionaries more distinguishable names.
In this program I also worked in multiple files, i.e. I had my dictionaries in a file called "dicts.py" and my main program in "main.py" (mostly because I could).
Dictionary code:
Program code:
/Ludvig
This problem took me way too long time to solve. All because of a mistake I made caused by naming my dictionaries too similarly. When I thought I was adding "hundred_and_text", I really was adding "hundreds_text". What made it really annoying is that I made my code output all the thousand numbers in words, which worked great. For troubleshooting I copied the output into excel and counted the letters in the cells which gave the correct answer, but when I used my code for counting, I missed ~300 letters. Next time I'm planning on doing something like this, I'm going to give dictionaries more distinguishable names.
In this program I also worked in multiple files, i.e. I had my dictionaries in a file called "dicts.py" and my main program in "main.py" (mostly because I could).
Dictionary code:
singulars_text = { # 36 1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine',}
ten_to_nineteen_text = { # 70 1: 'ten', 2: 'eleven', 3: 'twelve', 4: 'thirteen', 5: 'fourteen', 6: 'fifteen', 7: 'sixteen', 8: 'seventeen', 9: 'eighteen', 10: 'nineteen'}
tens_text = { # 46 2: 'twenty', 3: 'thirty', 4: 'forty', 5: 'fifty', 6: 'sixty', 7: 'seventy', 8: 'eighty', 9: 'ninety'}
hundreds_text = { # 107 1: 'onehundred', # onehundred 2: 'twohundred', # twohundred 3: 'threehundred', # threehundred 4: 'fourhundred', 5: 'fivehundred', 6: 'sixhundred', 7: 'sevenhundred', 8: 'eighthundred', # eighthundred 9: 'ninehundred', # ninehundred}
hundred_and_text = { # 126 1: 'onehundredand', # onehundredand 2: 'twohundredand', # twohundredand 3: 'threehundredand', # threehundredand 4: 'fourhundredand', # fourhundredand 5: 'fivehundredand', 6: 'sixhundredand', 7: 'sevenhundredand', 8: 'eighthundredand', 9: 'ninehundredand',}
Program code:
import dicts def number_counter_text(): tot = 0 for k, v in dicts.singulars_text.items(): # print(dicts.singulars_text[k]) tot += len(dicts.singulars_text[k]) for k, v in dicts.ten_to_nineteen_text.items(): # print(dicts.ten_to_nineteen_text[k]) tot += len(dicts.ten_to_nineteen_text[k]) for k, v in dicts.tens_text.items(): # print(dicts.tens_text[k]) tot += len(dicts.tens_text[k]) for a, b in dicts.singulars_text.items(): # print(dicts.tens_text[k], end="") # print(dicts.singulars_text[a]) tot += len(dicts.tens_text[k]) + len(dicts.singulars_text[a]) for k, v in dicts.hundred_and_text.items(): # print(dicts.hundreds_text[k]) tot += len(dicts.hundreds_text[k]) for x, y in dicts.hundreds_text.items(): # print(dicts.hundred_and_text[k], end="") # print(dicts.singulars_text[x]) tot += len(dicts.hundred_and_text[k]) + len(dicts.singulars_text[x]) for a, b in dicts.ten_to_nineteen_text.items(): # print(dicts.hundred_and_text[k], end="") # print(dicts.ten_to_nineteen_text[a]) tot += len(dicts.hundred_and_text[k]) + len(dicts.ten_to_nineteen_text[a]) for c, d in dicts.tens_text.items(): # print(dicts.hundred_and_text[k], end="") # print(dicts.tens_text[c]) tot += len(dicts.hundred_and_text[k]) + len(dicts.tens_text[c]) for e, f in dicts.singulars_text.items(): # print(dicts.hundred_and_text[k], end="") # print(dicts.tens_text[c], end="") # print(dicts.singulars_text[e]) tot += len(dicts.hundred_and_text[k]) + len(dicts.tens_text[c]) + len(dicts.singulars_text[e]) # print("onethousand") tot += len("onethousand") print("----- result -----") print(tot) pass number_counter_text()
/Ludvig
Labels:
problem 17,
project euler
2017-06-18
Project Euler Problem 16
Easiest to far. I take the number, make it into a string, during for-loop through the characters in the string, I make them into integers and add them to tot.
A slimmer version of the same code:
/Ludvig
number = 2 ** 1000tot = 0 for x in range(0, len(str(number))): digit = str(number)[x:x + 1] tot += int(digit) print("tot:", tot)
A slimmer version of the same code:
tot = 0 for x in range(0, len(str(2 ** 1000))): tot += int(str(2 ** 1000)[x:x + 1]) print("tot:", tot)
/Ludvig
Labels:
problem 16,
project euler
2017-06-17
Project Euler Problem 15
I think this problem is about combinatorics, i.e. finding out in how many ways a series of discrete values can be combined. For this problem I'm going to use factorials, mathematically expressed as "!".
2x2 has 3! combinations: 3x2x1=6
3x3 has 4! combinations: 4x3x2x1=24
4x4 has 5! combinations: 5x4x3x2x1=120
etc.
What I want to do is to write a code that calculated factorials and tells me what 21! is.
Outputs: 51090942171709440000 which is WRONG. I'm guessing that it's because this way of doing it includes duplicates of routes. Another approach is to write all routes as directions. I chose R for right and D for down. On a 2x2 grid, going from upper left corner to lower right corner, it takes four directions: RRDD. As long as these four directions are included in the route, it will make the route complete. So I want to make a program that checks all the combinations of the directions and removes all duplicates. When I google for help on these problems I try to avoid websites that addresses the very problems that I'm working on (there's a lot of help to get on Project Euler problems already).
I found a video about this type of problem and I was on the way to finding the solution, what I missed though was that I need to divide the factorial with the number of directions that I'll take (20xR and 20xD). So I get: c(40,(20,20)) which is 40!/(20!20!). Voila, I got it to work. This code works for any grid sized ROW*COLUMN.
To make this problem a little bit more interesting I'm going to let the user input values in the console instead of having it hard coded. By the way, when googling around, I found an interesting quote:
"The classical Python mentality, though, is that it's easier to ask forgiveness than permission. In other words, don't check whether
So I'm also going to give try-except a shot.
Aaaaand it works!
/Ludvig
2x2 has 3! combinations: 3x2x1=6
3x3 has 4! combinations: 4x3x2x1=24
4x4 has 5! combinations: 5x4x3x2x1=120
etc.
What I want to do is to write a code that calculated factorials and tells me what 21! is.
def calculate_factorial(val): result = 1 for x in range(1, val + 1): result *= x return result print(calculate_factorial(21))
Outputs: 51090942171709440000 which is WRONG. I'm guessing that it's because this way of doing it includes duplicates of routes. Another approach is to write all routes as directions. I chose R for right and D for down. On a 2x2 grid, going from upper left corner to lower right corner, it takes four directions: RRDD. As long as these four directions are included in the route, it will make the route complete. So I want to make a program that checks all the combinations of the directions and removes all duplicates. When I google for help on these problems I try to avoid websites that addresses the very problems that I'm working on (there's a lot of help to get on Project Euler problems already).
I found a video about this type of problem and I was on the way to finding the solution, what I missed though was that I need to divide the factorial with the number of directions that I'll take (20xR and 20xD). So I get: c(40,(20,20)) which is 40!/(20!20!). Voila, I got it to work. This code works for any grid sized ROW*COLUMN.
def factorial(val): result = 1 for x in range(1, val + 1): result *= x return result def routes(down, right): result = factorial(down + right) / (factorial(down) * factorial(right)) return int(result) print("Routes: ", routes(20, 20))
To make this problem a little bit more interesting I'm going to let the user input values in the console instead of having it hard coded. By the way, when googling around, I found an interesting quote:
"The classical Python mentality, though, is that it's easier to ask forgiveness than permission. In other words, don't check whether
x is an integer; assume that it is and catch the exception results if it isn't:try:
x += 1
except TypeError:
..."
So I'm also going to give try-except a shot.
def factorial(val): result = 1 for x in range(1, val + 1): result *= x return result def routes(down, right): result = factorial(down + right) / (factorial(down) * factorial(right)) return int(result) rowInput = input("Rows:") colInput = input("Columns:") try: print("Routes: ", routes(int(rowInput), int(colInput))) except: print("Invalid input")
Aaaaand it works!
/Ludvig
Labels:
problem 15,
project euler
2017-06-16
Project Euler Problem 14
I first ran a code that went through all the 1M starting values, and when it was finished, it printed the chain length instead of what starting number the chain had -.-. When I modified the code to solve the problem I made it stop at that chain length instead of continuing searching.
chain = [] newChain = [] val = 0 def odd_val(val): odd = 3 * val + 1 return int(odd) def even_val(val): even = val / 2 return int(even) for value in range(10 ** 6, 1, -1): print(value, len(chain)) while value != 1: if value % 2 == 0: value = even_val(value) newChain.append(value) else: value = odd_val(value) newChain.append(value) if len(newChain) > len(chain): chain = newChain print("New chain!") if len(chain) == 524: break newChain = [] print(len(chain), val)
Hmmm now that I look through the print out there seems to be something weird in the code. I'm going to make it look nicer before heading on to the next problem.
I ran out of energy for fixing it. Hopefully I'll turn back sometime in the future.
/Ludvig
Labels:
problem 14,
project euler
2017-06-15
Project Euler Problem 13
tot = 0 with open('pe13.txt') as file: lines = file.readlines() lines = [x.strip() for x in lines] for x in range(0, len(lines)): line = lines[x] tot += int(line) tot = str(tot) tot = tot[:10] print(tot)
Above is what I first did to solve the problem. Below is how I refined my solution:
tot = 0lines = [] with open('pe13.txt') as file: lines = file.readlines() lines = [x.strip() for x in lines] lines = list(map(int, lines)) tot = str(sum(lines)) tot = tot[:10] print(tot)
and even more:
with open('pe13.txt') as file: lines = file.readlines() lines = [x.strip() for x in lines] lines = list(map(int, lines)) print(str(sum(lines))[:10])
Quite compact if I may say so.
/Ludvig
Labels:
problem 13,
project euler
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!
/Ludvig
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
Labels:
problem 12,
project euler
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.
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.
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
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
Labels:
problem 11,
project euler
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.
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.
/Ludvig
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
Labels:
problem 10,
project euler
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.
/Ludvig
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
Labels:
problem 9,
project euler
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:
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)
Labels:
problem 8,
project euler
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.
"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.
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:
I'd like to have a feature in PyCharm that shows the time it took to run an algorithm.
/Ludvig
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
Labels:
problem 7,
project euler
2017-06-08
Project Euler Problem 6
The problem:
"The sum of the squares of the first ten natural numbers is,
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:
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:
/Ludvig
"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
Labels:
problem 6,
project euler
2017-06-07
Project Euler Problem 5
The problem:
"2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?"
Should I go for a for-loop or a while-loop? Atleast I need to use the modulus %. After messing around, trying to mix for-loops, while-loops and if-statements, I started to think that I needed to take a break. Then suddenly I hover "y == 1" with the cursor and see "Statement seems to have no effect". What's this?! Then I realized! Double equal sign is when doing logical things like checking if x is equal to y. When assigning a value to a variable, only one equal sign is to be used!
To solve this problem I'm using a brute force way, checking every single modulus for every denominator up to 20. This takes quite some time (a minute) and there must be a more efficient (faster) way of doing this, probably there is some smart math way to do it.
The code I used:
/Ludvig
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?"
Should I go for a for-loop or a while-loop? Atleast I need to use the modulus %. After messing around, trying to mix for-loops, while-loops and if-statements, I started to think that I needed to take a break. Then suddenly I hover "y == 1" with the cursor and see "Statement seems to have no effect". What's this?! Then I realized! Double equal sign is when doing logical things like checking if x is equal to y. When assigning a value to a variable, only one equal sign is to be used!
To solve this problem I'm using a brute force way, checking every single modulus for every denominator up to 20. This takes quite some time (a minute) and there must be a more efficient (faster) way of doing this, probably there is some smart math way to do it.
The code I used:
x = 1y = 1while y != 20: if x % y == 0: y += 1 else: y = 1 x += 1print(x, y)
/Ludvig
Labels:
problem 5,
project euler
2017-06-06
Project Euler Problem 4
The problem is:
"A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
"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."
My approach to this problem is to do the multiplication, put the product into a string, reverse the string and compare the reversed string to the original string. Every time the comparison is true, I'll save the result as a variable.
For this problem I'm going to use two for-loops, one for each factor. I also need to find a way to reverse a string in Python. Google! Oh, when googling "python palindrome", I found on Stack overflow that there is actually a very compact way in Python to check for palindromes.
Wow, this was really easy thanks to the str(x*y)[::-1]
7 rows!
/Ludvig
My approach to this problem is to do the multiplication, put the product into a string, reverse the string and compare the reversed string to the original string. Every time the comparison is true, I'll save the result as a variable.
For this problem I'm going to use two for-loops, one for each factor. I also need to find a way to reverse a string in Python. Google! Oh, when googling "python palindrome", I found on Stack overflow that there is actually a very compact way in Python to check for palindromes.
Wow, this was really easy thanks to the str(x*y)[::-1]
largestPalindrome = 0for x in range(100,1000): for y in range(100,1000): if str(x*y) == str(x*y)[::-1]: if x*y>largestPalindrome: largestPalindrome = x*y print(largestPalindrome)
7 rows!
/Ludvig
Labels:
problem 4,
project euler
2017-06-05
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 ?"
Let's start off by googling how to calculate prime factors in a good way. Maybe I need to start calculating prime numbers? Checking every number between 0 and 600851475143 to see if it's a prime number was a bad idea.
After some coding I've successfully produced the same result as in the example.
which makes following output:
ok prime: 5
ok prime: 7
ok prime: 13
ok prime: 29
Number of ok primes: 4
I've hard coded the prime numbers into the list primeList. After consulting with an online prime factor calculator, I've found that the prime number that I'm looking for is way bigger than what I've hard coded. Now the question is if I should calculate my own prime numbers or if I should hard code them into the list.
Now that I'm checking remainder of 600851475143%x (for-loop), I'm getting really many ok prime numbers, and also on fewer lines of code!
Output:
ok prime: 1
ok prime: 71
ok prime: 839
ok prime: 1471
ok prime: 6857
ok prime: 59569
ok prime: 104441
ok prime: 486847
ok prime: 1234169
ok prime: 5753023
ok prime: 10086647
.... I stop it manually
Now I need to make it stop automatically when it have reached enough factors to multiply to 60085147514 (which are the five first in the above output). To do this in a nice way I want to check the product of all the okPrimes and check the remainder of 600851475143%(the product). Stack overflow suggests that I add the library functools and operator by adding "
Success was reached with following code:
with 20 lines. I could've skipped the last 6 lines and added a print on each okPrime instead, but this solution has a nicer output.
/Ludvig
Let's start off by googling how to calculate prime factors in a good way. Maybe I need to start calculating prime numbers? Checking every number between 0 and 600851475143 to see if it's a prime number was a bad idea.
After some coding I've successfully produced the same result as in the example.
primeList = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79] okPrimes = [] number = 13195 for x in range(1,len(primeList)): if number%primeList[x]==0: okPrimes.append(primeList[x]) print("ok prime: ", primeList[x]) print("Number of ok primes: ", len(okPrimes))
which makes following output:
ok prime: 5
ok prime: 7
ok prime: 13
ok prime: 29
Number of ok primes: 4
I've hard coded the prime numbers into the list primeList. After consulting with an online prime factor calculator, I've found that the prime number that I'm looking for is way bigger than what I've hard coded. Now the question is if I should calculate my own prime numbers or if I should hard code them into the list.
Now that I'm checking remainder of 600851475143%x (for-loop), I'm getting really many ok prime numbers, and also on fewer lines of code!
okPrimes = [] number = 600851475143 for x in range(1,600851475143): if number%x==0: okPrimes.append(x) print("ok prime: ", x) print("Number of ok primes: ", len(okPrimes))
Output:
ok prime: 1
ok prime: 71
ok prime: 839
ok prime: 1471
ok prime: 6857
ok prime: 59569
ok prime: 104441
ok prime: 486847
ok prime: 1234169
ok prime: 5753023
ok prime: 10086647
.... I stop it manually
Now I need to make it stop automatically when it have reached enough factors to multiply to 60085147514 (which are the five first in the above output). To do this in a nice way I want to check the product of all the okPrimes and check the remainder of 600851475143%(the product). Stack overflow suggests that I add the library functools and operator by adding "
import functools" and "import operator" in the beginning of my code to get access to the feature.Success was reached with following code:
import functools import operator okPrimes = [] product = 1number = 600851475143largestFactor = 0 for x in range(1,600851475143): if number%x==0: okPrimes.append(x) product = functools.reduce(operator.mul, okPrimes) if product==number: break for x in range(0,len(okPrimes)): if okPrimes[x]>largestFactor: largestFactor=okPrimes[x] print(largestFactor)
with 20 lines. I could've skipped the last 6 lines and added a print on each okPrime instead, but this solution has a nicer output.
/Ludvig
Labels:
problem 3,
project euler
2017-06-04
Project Euler Problem 2
The problem:
"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:
An even-valued term is dividable by 2. When starting to write a for loop I got this:
which might be useful. Since the steps I'll be iterating will change, a while-loop might be more useful in this case. How does Python use while-loops? I found a while-loop-example here, which I modify to run on Python 3.
"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."An even-valued term is dividable by 2. When starting to write a for loop I got this:
which might be useful. Since the steps I'll be iterating will change, a while-loop might be more useful in this case. How does Python use while-loops? I found a while-loop-example here, which I modify to run on Python 3.
count = 0while (count < 9): print('The count is:', count) count = count + 1 print("Good bye!")
This is how I'm setting up my variables for the first loop: 1, 2, 3. Next loop will shift the three variables to the right on step so that "previous" is 2, "current" is 3 and "next" is 5.
previousNumber = 1currentNumber = 2nextNumber = 3fourM = 4000000sum = currentNumber while (nextNumber < fourM): nextNumber=previousNumber+currentNumber previousNumber=currentNumber currentNumber=nextNumber if nextNumber<fourM and nextNumber%2==0: sum+=nextNumber print("Sum: ", sum)
/Ludvig
Labels:
problem 2,
project euler
2017-06-03
Project Euler 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 1000."
For this problem I think I'll need the syntax for for-loop and if-statement. From Python Wiki:
What to notice here is that the print command is not written as a function. This is probably because the page is written for Python 2.x and not Python 3.x that I'm running. To make it run, I'll rewrite it as a function with parentheses.
This returns:
We're on time 0
We're on time 1
We're on time 2
Process finished with exit code 0
What does %d do? According to Stack Overflow %d is a placeholder for numbers and %s is a placeholder for strings. I.e. %d is where the variable x will be output. Try and see!
Now to the Euler Project Problem 1 and to the problem with documenting programming progress. Of course I didn't succeed on the first try and I did learn something useful. What I did wrong (failed maybe 6-7 times) was that I used "sum=+x" to add up the values. After trying "sum = sum + x" it worked like a charm and I got the correct answer. Isn't it weird that "sum=+x" didn't work? Yes and no, I was thinking correctly but got it wrong. The correct syntax for this operation is to have the + before =, i.e. "sum+=x" works. This is my code:
/Ludvig
For this problem I think I'll need the syntax for for-loop and if-statement. From Python Wiki:
for x in range(0, 3):
print "We're on time %d" % (x)
What to notice here is that the print command is not written as a function. This is probably because the page is written for Python 2.x and not Python 3.x that I'm running. To make it run, I'll rewrite it as a function with parentheses.
for x in range(0, 3): print("We're on time %d" % (x))
This returns:
We're on time 0
We're on time 1
We're on time 2
Process finished with exit code 0
What does %d do? According to Stack Overflow %d is a placeholder for numbers and %s is a placeholder for strings. I.e. %d is where the variable x will be output. Try and see!
Now to the Euler Project Problem 1 and to the problem with documenting programming progress. Of course I didn't succeed on the first try and I did learn something useful. What I did wrong (failed maybe 6-7 times) was that I used "sum=+x" to add up the values. After trying "sum = sum + x" it worked like a charm and I got the correct answer. Isn't it weird that "sum=+x" didn't work? Yes and no, I was thinking correctly but got it wrong. The correct syntax for this operation is to have the + before =, i.e. "sum+=x" works. This is my code:
sum = 0 for x in range(0, 1000): if x%3==0 or x%5==0: sum+=x print('%s %d' % ("Sum: ", sum))
/Ludvig
Labels:
for,
if,
problem 1,
project euler
Subscribe to:
Posts (Atom)
