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:

x = 1y = 1while y != 20:
    if x % y == 0:
        y += 1    else:
        y = 1        x += 1print(x, y)

/Ludvig

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.

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]

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

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.

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

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:

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.

Here is the code that completed the task:

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)

This is a great hobby!

/Ludvig

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:

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

More Configuration and Project Euler

More Configuration

I need to change the editor color theme. I chose Warmneon in the startup configuration which now is terrible to have together with the Darcula theme. Violet text on dark grey background is really hard to read. I go to Settings | Editor | Colors & Fonts and set Scheme to Darcula here too. Looks a lot better now. Instead of violet, it's now orange. I'm also setting the editor font size to 14.

Euler Project

In the description of this blog it says that Quantopian is what got me interested in Python programming. After being introduced to Quantopian, the same friend introduced me to Project Euler.

" Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems. "

After creating an account and logging in for the first time, this is what greets me.

This is what the website says about using the Internet for finding help and/or answers. So there shouldn't be a problem for me to put my code for solving the problems on this blog.

Hello World

The aimof today is to write my first Python program in PyCharm. The program I'm hoping to create is going to make output "Hello World".

I start PyCharm and click (File | New Project). Create.

 A dialog box pops up in which I choose to "Open in current window" and not "Add to currently opened projects" (did this popup since I created a project when I ran PyCharm the first time?).

Anyway, I need somewhere to put my code. On Youtube I found a video by Ryan Burmeister that seems to be about what I'm looking for.

I too set my color theme (I thought I did this in the startup configuration?) to Darcula (Shift+Alt+S | Appearance & Behaviour | Appearance).

Press Ctrl+Insert to popup a New-list in which you choose to create a new file (just press Enter).

I'm naming it "main.py". I don't know if PyCharm puts the ".py" there by itself if I wouldn't do it, but it's good practise to do it. One day maybe I'm using another IDE in which it doesn't do it automatically. OK.

Thanks to the auto code folding, to write "print("Hello World")", all I had to type on the keyboard was "print("Hello World". The bracket and quote closed off itself.

To run my first Python program, I now use what I learned from Tip of the Day and press Alt+Shift+F10 and then Enter on "main". This will not only run the code, but PyCharm will make this code the "current code to Run" which can be invoked by either pressing Shift+F10 or the green Play button in the upper right corner.

If I want to run another file, I can use Alt+Shift+F10 again to popup the menu again.