Project Euler problems 1 and 2 in python

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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))