Project Euler

For questions about problems on the Project Euler web site. No spoilers. Please include the question number in the subject line of your post.

Project Euler

micseydel wrote:If you enjoyed this, you might want to check out Project Euler (especially problem 14).

Merci micseydel pour ton aide !

Thanks to you I cleaned a bit my script .

If you enjoyed this, you might want to check out Project Euler (especially problem 14).

What a great idea. I registered to the Project Euler some weeks ago but the problems were not as easy as it seems to be ! Here was my attempt to solve the first problem...

Problem : 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.

Code: Select all
# -*- coding: utf-8 -*-

def algorithm(a):

a -= 1
_list = []

while a > 0:

if a % 5 == 0:
_list.append(a)

elif a % 3 == 0:
_list.append(a)

a -= 1

return _list

def multiples_sum(_list):

multiples_sum = sum(_list)
return multiples_sum

def solve():

i = algorithm(1000)
e = multiples_sum(i)
print e

solve()

... As you can see, I've used the brute force solution which isn't very ingenious...
Last edited by pyjul on Tue Jun 10, 2014 6:51 pm, edited 7 times in total.
pyjul

Posts: 14
Joined: Tue Jun 03, 2014 5:24 pm

Re: Syracuse sequence

You're repeating the same mistakes micseydel mentioned in your first code.

Why not just use sum()? (not to mention you gave the same name to the function and a variable in it)
Code: Select all
def multiples_sum(_list):

multiples_sum = sum(_list)
return multiples_sum

Your variable names could (and should) be better.
Also, the loop in the algorithm() functions should be a for loop.

Btw, this problem is easily written as a one-liner.
Friendship is magic!

R.I.P. Tracy M. You will be missed.

stranac

Posts: 1790
Joined: Thu Feb 07, 2013 3:42 pm

Re: Syracuse sequence

Bonjour, welcome to the forums!

If you like to discuss Euler problems, maybe start a thread in the apropiate forum, as this thread is mainly about your completed script above.
Due to the reasons discussed here we are moving to python-forum.net on October 1, 2016.

This forum will be closed. Please create an account at the new site to continue discussion.

IRC://irc.freenode.net/python-forum
Kebap

Posts: 689
Joined: Thu Apr 04, 2013 1:17 pm
Location: Germany, Europe

Re: Project Euler

You're repeating the same mistakes micseydel mentioned in your first code.

Oh ! Autant pour moi, I've written this script before he mentioned the mistakes from the first program and I had better to correct my solution to the first Euler project problem before posting it. Mea culpa!

Your variable names could (and should) be better.

According to you, what is a "good" variable name ?

Also, the loop in the algorithm() functions should be a for loop.

Why ? The while loop 'while n > 0:' is quite good...

Btw, this problem is easily written as a one-liner.

Oh, well... I'm really curious to see how it would be to write this program in a single line !

I've reviewed my solution
Code: Select all
# -*- coding: utf-8 -*-

def multiples(n):

return n % 5 == 0 or n % 3 == 0

def algorithm(n):

numbers = []

while n > 0:

if multiples(n):
numbers.append(n)

n -= 1

return numbers

def solve():

numbers = algorithm(1000)
return sum(numbers)
Last edited by pyjul on Fri Jun 06, 2014 8:52 pm, edited 4 times in total.
pyjul

Posts: 14
Joined: Tue Jun 03, 2014 5:24 pm

Re: Syracuse sequence

pyjul wrote:According to you, what is a "good" variable name ?

Something like limit instead of n, or numbers instead of _list.
i and e in your first code also make no sense.

pyjul wrote:Why ? The while loop 'while n > 0:' is quite good...

Because iterating over a list of numbers is exactly what a for loop is meant for.
This (btw, this is not what you want, since you don't want the 1000):
Code: Select all
# n initialized somewhere
while n > 0:
# some stuff here
n -= 1

Can be written as:
Code: Select all
for n in range(n, 0, -1):
# some stuff here

Or more simply (with numbers growing):
Code: Select all
for n in range(n + 1):
# some code here

pyjul wrote:Oh, well... I'm really curious to see how it would be to write this program in a single line !

Either this:
Code: Select all
sum(n for n in xrange(1000) if n % 3 == 0 or n % 5 == 0)

or this:
Code: Select all
sum(xrange(3, 1000, 3)) + sum(range(5, 1000, 5)) - sum(xrange(15, 1000, 15))
Friendship is magic!

R.I.P. Tracy M. You will be missed.

stranac

Posts: 1790
Joined: Thu Feb 07, 2013 3:42 pm

Re: Project Euler

Thank you stranac
pyjul

Posts: 14
Joined: Tue Jun 03, 2014 5:24 pm

Re: Project Euler

Hello, I am new here and I am a beginner/intermediate level python programmer. I am also interested in these kinds of problems. This post is not so much a question as it is another potential solution and an introduction of myself (so hopefully the answer is correct ). I believe you can do this without for loops a la Gauss, where you add the highest multiple and the lowest multiple together and multiply that value with the total number of multiples below the upper bound and then divide by 2.
Code: Select all
def sumFunc(upper, mult)
"""based on summing up numbers from 1 to n
n(n-1)/2"""
upper -= 1 # below 1000
numMults = upper/mult # total number of multiples (for 3 numMults = 333)
highest = numMults*mult # highest number that is multiple (for 3 highest = 999)
addy = highest + mult # sum these two numbers
return addy*numMults/2 # divide by two because you would sum each of the numbers twice

def main():
mult3 = sumFunc(1000,3)
mult5 = sumFunc(1000,5)
mult15 = sumFunc(1000,15)
return mult3 + mult5 - mult15

if __name__ == "__main__":
main()

In the specified case this seems to work (I checked with the for loop method), but I am unsure if it always works. I tested it with much higher upper bounds (10**9) and it is significantly faster than the for loop methods. An addition to the script could be calculating the lowest product of the 2 multiples of interest, so that it does not have to be hard-coded into the script.
Last edited by Mekire on Sun Jun 29, 2014 3:31 pm, edited 1 time in total.
Reason: First post lock.
McCoffee

Posts: 2
Joined: Sat Jun 28, 2014 10:20 pm