<jupyter_start><jupyter_text>// http://chris-said.io/2016/02/13/how-to-make-polished-jupyter-presentations-with-optional-code-visibility/  // https://github.com/csaid/polished_notebooks  function code_toggle() {    if (code_shown){      $('div.input').hide('500');      $('toggleButton').val('Show Code')    } else {      $('div.input').show('500');      $('toggleButton').val('Hide Code')    }    code_shown = !code_shown  }  $( document ).ready(function(){    code_shown=false;    $('div.input').hide()  });<jupyter_code>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
import os
import sys
module_path = os.path.abspath(os.path.join('..'))
if module_path not in sys.path:
    sys.path.append(module_path)<jupyter_output><empty_output><jupyter_text>[Problem 1](https://projecteuler.net/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---<jupyter_code>%psource p1.natural_3and5_brute
from destryseuler import p1
p1.natural_3and5_brute??
%pfile ../destryseuler/p1.py
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
natural3and5Brute()<jupyter_output><empty_output><jupyter_text>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](http://math.stackexchange.com/questions/2260/proof-for-formula-for-sum-of-sequence-123-ldotsn) 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}$$<jupyter_code>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<jupyter_output><empty_output><jupyter_text>I believe this has O(1) complexity.<jupyter_code>natural3and5()
natural3and5(5000)<jupyter_output><empty_output><jupyter_text>ToDo---1. Benchmarks2. Can you make the divisors inputs and calulate the common term?3. More than 2 Divisors?<jupyter_code>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)
elegant
brute
import matplotlib.pyplot as plt
%matplotlib inline
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()<jupyter_output><empty_output><jupyter_text>So it looks like the brute force is linear and the elegant is constant(ish)<jupyter_code><script>
  $(document).ready(function(){
    $('div.prompt').hide();
    $('div.back-to-top').hide();
    $('nav#menubar').hide();
    $('.breadcrumb').hide();
    $('.hidden-print').hide();
  });
</script>

<footer id="attribution" style="float:right; color:#999; background:#fff;">
Created with Jupyter, MIT License, 2017 <NAME>.
</footer><jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.17257634761221563, 'fraction_numerical': 0.04078704652592744, 'mean_word_length': 3.959349593495935, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 30, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '386146', 'license': 'MIT', 'n_tokens_mistral': 1873, 'n_tokens_neox': 1722, 'n_words': 435, 'path': 'python/notebooks/Problem1.ipynb', 'repo_name': 'destrys/euler', 'size': '4884'}