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)
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.
In [34]:
%psource p1.natural_3and5_brute
In [8]:
from destryseuler import p1
p1.natural_3and5_brute??
In [3]:
%pfile ../destryseuler/p1.py
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]:
I believe this has O(n) complexity.
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]:
In [6]:
natural3and5(5000)
Out[6]:
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)
In [8]:
elegant
Out[8]:
In [9]:
brute
Out[9]:
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)