7
\$\begingroup\$

What do you think about my code? I am a beginner and just started doing some algorithmic exercises to sharpen up my python skills.

Here is code for 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."""

x = 0

for i in range(1000):
    if i % 3 == 0 or i % 5 == 0:
        x += i

print(x)

Problem 2:

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

numbers = [1, 2]
total = 0

for i in range(4000000):
    if i == numbers[-1] + numbers[-2]:
        numbers.append(i)

for n in numbers:
    if n % 2 == 0:
        total += n

print(total)

I'm sure there are better ways to solve those problems but would like to see what you think about my quite simple idea.

\$\endgroup\$
  • 1
    \$\begingroup\$ In the future, please stick to one program per question, please. \$\endgroup\$ – 200_success Dec 7 '16 at 17:33
5
\$\begingroup\$

Problem 1 is probably better and more pythonic when written as a list comprehension:

x = sum(i for i in range(1000) if i % 3 == 0 or i % 5 == 0)
print(x)

For the second problem I would recommend a generator and to use sum again:

def fibonacci(max_n):
    n, prev = 1, 1
    while n <= max_n:
        yield n
        n, prev = n + prev, n

total = sum(n for n in fibonacci(4000000) if n % 2 == 0)
print(total)

This way only two ints are ever in memory (well three if you count max_n). In comparison, your code has a list of possibly large size.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot! I didnt know anything about generators until now but after reading some posts on SO about them I think I kinda get what they are about, definitely will be looking more into them - thank you again for feedback! \$\endgroup\$ – ohwelppp Dec 6 '16 at 21:51
  • \$\begingroup\$ @doublemic If you like an answer, you can upvote it (as soon as you reach 15 reputation). If after some time (usually at least a day is recommended to give people in other timezones also the chance to answer), you find that you like one answer best, you can accept it using the green checkmark to the left of the post. \$\endgroup\$ – Graipher Dec 6 '16 at 21:55
4
\$\begingroup\$

This is how I did problem 1:

sum({*range(3, 1000, 3)} | {*range(5, 1000, 5)})

create the numbers, don't search for them. Many eulers is like that.


I thought I share this ugly code as well:

def arithmetic_sum(number, limit):
    for last in range(limit, 1, -1):
        if last % number == 0:
            return ((limit // number) * (number + last)) // 2

def math_power():
    ans, limit = 0, 999
    ans += arithmetic_sum(3, limit)
    ans += arithmetic_sum(5, limit)
    ans -= arithmetic_sum(15, limit)
    return ans

that is the fastest way I know of to solve this first problem. For bigger n:s the execution time is pretty much unaffected.

Instead of creating the numbers, add the all at the same time :).

\$\endgroup\$
  • \$\begingroup\$ Note that this only works in Python 3.x due to the range unpacking into a set (which is fine, because the OP also used Python 3.x). \$\endgroup\$ – Graipher Dec 7 '16 at 10:20
  • \$\begingroup\$ In Python 2.x, this works instead: sum(set(range(3, 1000, 3)) | set(range(5, 1000, 5))) and is actually two to three times faster than what I proposed in my answer (starting at three and going down to two for n from 1000 to 100000000). \$\endgroup\$ – Graipher Dec 7 '16 at 10:23
  • \$\begingroup\$ It's an interesting problem, the first Euler problem, you solve it it in many ways. \$\endgroup\$ – Simon Dec 7 '16 at 15:03
  • \$\begingroup\$ Didn't dear post anything on euler 2 since it would pretty much be like copying you! \$\endgroup\$ – Simon Dec 7 '16 at 15:06
0
\$\begingroup\$

Timing of your algorithm

def f():
    x = 0

    for i in range(1000):
        if i % 3 == 0 or i % 5 == 0:
            x += i

    return x

%timeit f()
152 µs ± 12.5 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Using Principle of Inclusion and Exclusion (PIE) gives you the answer faster.

%timeit (sum(range(3, 1000, 3)) + sum(range(5, 1000, 5)) - sum(range(15, 1000, 15)))
14.8 µs ± 1.01 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Regarding the second question, the simple for loop is the best thing and quite fast than the naive recursive algorithm. However the Wikipedia page discusses some great formulas which can speed-up your search Fibonacci Numbers Wiki.

a, b = 1, 1
while True:
    a, b = b, a + b
    print(a, b)

Nice formula which can be used in recursion.

Formula to find even Fibonacci Numbers: Source Wikipedia

\$\endgroup\$
0
\$\begingroup\$

Edit: this is same algorithm as provided by Simon but different code. .......

One option is to use Euler himself to solve Euler Project #1. Namely triangular numbers (Elements of Algebra, 427).

def triangular_number(num, max_num=999):
    """Return maximum triangular number of num in range  max_num (inclusive).

    Calculate number of occurances of num within range. Then calculatate
    triangular number of occurances and multiply by num.

    :param num: number of which occurances are calculated
    :type num: int
    :param max_num: upper limit for finding num  occurances (inclusive)
    :type max_num: int
    :returns: triangular number
    :rtype: int
    """

    occurrences = max_num // num

    return (num * occurrences * (occurrences + 1)) / 2


print(triangular_number(3) + triangular_number(5) - triangular_number(15))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.