

In [6]:

    
from __future__ import print_function

def page_printer(data, start=0, screen_lines=0, pager_cmd=None):
    if isinstance(data, dict):
        data = data['text/plain']
    print(data)

import IPython.core.page
IPython.core.page.page = page_printer



In [2]:

    
import os
import sys
module_path = os.path.abspath(os.path.join('..'))
if module_path not in sys.path:
    sys.path.append(module_path)

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.

Brute Force



In [34]:

    
%psource p1.natural_3and5_brute



In [8]:

    
from destryseuler import p1
p1.natural_3and5_brute??









    



Signature: p1.natural_3and5_brute(upper=1000)
Source:   
def natural_3and5_brute(upper=1000):
    output = 0
    for i in range(1,upper):
        if i % 3 == 0:
            output += i
            continue
        if i % 5 == 0:
            output += i
            continue
    return output
File:      ~/code/euler/python/destryseuler/p1.py
Type:      function



In [3]:

    
%pfile ../destryseuler/p1.py









    



Object `../destryseuler/p1.py` not found.



In [11]:

    
def natural3and5Brute(upper=1000):
    output = 0
    for i in range(1,upper):
        if i % 3 == 0:
            output += i
            continue
        if i % 5 == 0:
            output += i
            continue
    return output



In [12]:

    
natural3and5Brute()









    Out[12]:





233168

I believe this has O(n) complexity.

More Elegant

If $n$ is the maximum value, the sum of the multiples can be represented as such: $$(3 + 6 + 9 + ... \left \lfloor{\frac{x}{3}}\right \rfloor \times 3 ) + (5 + 10 + 15 + ... + \left \lfloor{\frac{x}{5}}\right \rfloor \times 5) - (15 + 30 + 45 + ... + \left \lfloor{\frac{x}{15}}\right \rfloor \times 15)$$ where $\left \lfloor{x}\right \rfloor$ is the floor function, returning the largest integer not greater than $x$The first term is the sum of natural numbers divisible by 3, the second term is the sum of numbers divisible by 5, and the last term are the terms that are repeated in the first two terms.We can rewrite this as $$3\times(1+ 2 +3 +... \left \lfloor{\frac{x}{3}}\right \rfloor) + 5 \times (1 + 2 + 3 +... + \left \lfloor{\frac{x}{5}}\right \rfloor) - 15 \times (1 + 2 + 3 + ... + \left \lfloor{\frac{x}{15}}\right \rfloor)$$ Now each term contains a sum of sequential integers which is easily calculated $$ 3 \times \frac{\left \lfloor{\frac{n}{3}}\right \rfloor (\left \lfloor{\frac{n}{3}}\right \rfloor +1)}{2} + 5 \times \frac{\left \lfloor{\frac{n}{5}}\right \rfloor (\left \lfloor{\frac{n}{5}}\right \rfloor +1)}{2} - 15 \times \frac{\left \lfloor{\frac{n}{15}}\right \rfloor (\left \lfloor{\frac{n}{15}}\right \rfloor +1)}{2} $$



In [4]:

    
import math
def natural3and5(upper=1000):
    floor3 = math.floor((upper-1)/3)
    floor5 = math.floor((upper-1)/5)
    floor15 = math.floor((upper-1)/15)
    output = 3 * (floor3 * (floor3+1))/2 + 5 * (floor5 * (floor5 + 1))/2 - 15 * (floor15 * (floor15 + 1))/2
    return output

I believe this has O(1) complexity.



In [5]:

    
natural3and5()









    Out[5]:





233168.0



In [6]:

    
natural3and5(5000)









    Out[6]:





5829168.0

ToDo

Benchmarks
Can you make the divisors inputs and calulate the common term?
More than 2 Divisors?



In [7]:

    
elegant = []
brute = []
for i in [10**x for x in range(1,5)]:
    tmp = %timeit -o natural3and5(i)
    elegant.append(tmp.all_runs[0]/tmp.loops)
    tmp = %timeit -o natural3and5Brute(i)
    brute.append(tmp.all_runs[0]/tmp.loops)









    



956 ns ± 41 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
1.31 µs ± 33.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
960 ns ± 30.2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
10.6 µs ± 196 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
1.04 µs ± 53.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
110 µs ± 5.22 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
1.19 µs ± 19.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
1.16 ms ± 72.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)



In [8]:

    
elegant









    Out[8]:





[1.0273497749585658e-06,
 9.61151337949559e-07,
 1.0434619040461257e-06,
 1.1640232669888065e-06]



In [9]:

    
brute









    Out[9]:





[1.3695799689739942e-06,
 1.0671428500209004e-05,
 0.00010547546389279886,
 0.0010516491399612277]



In [10]:

    
import matplotlib.pyplot as plt
%matplotlib inline



In [11]:

    
y = [10**x for x in range(1,5)]

# Create plot
fig = plt.subplot()
fig.loglog(y,elegant,'yo-',linewidth=2)
fig.loglog(y,brute,'ro-',linewidth=2)

# Label it and make it pretty
myfont = {'family' : 'Times New Roman',
        'weight' : 'bold',
        'size'   : 22}

fig.set_xlabel('n', **myfont)
fig.set_ylabel('time (seconds)',**myfont)
fig.tick_params(axis='both',which='both',labelsize=20,width=2)
[fig.spines[x].set_linewidth(2) for x in fig.spines]

#Show it
plt.show()

So it looks like the brute force is linear and the elegant is constant(ish)