-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsum-multiples.html
123 lines (89 loc) · 4.08 KB
/
sum-multiples.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
<p><!doctype html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="markdown.css" type="text/css" rel="stylesheet"></link>
<link href="prettify.css" type="text/css" rel="stylesheet"></link>
<script type="text/javascript" src="js/jquery-1.7.1.min.js"></script>
<script type="text/javascript" src="js/google-code-prettify/prettify.js"></script>
<script type="text/javascript" src="https://d3eoax9i5htok0.cloudfront.net/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script type="text/javascript" src="js/myscripts.js"></script>
<title>Thousand Note - The Sum of Multiples</title>
</head></p>
<p><body onload="styleCode()"></p>
<p><a href="index.html">Thousandnote</a></p>
<h1>The Sum of Multiples</h1>
<p>Problem:</p>
<blockquote>
<p>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.</p>
<p>Find the sum of all the multiples of 3 or 5 below 1000.</p>
</blockquote>
<h2>Your solution</h2>
<p>In Java,</p>
<pre><code>public static void runthenumbers(){
int sum=0;
for (int x=1;x<1000;x++){
if(x%3==0 || x%5==0){
sum+=x;
}
}
out.println(sum);
}
</code></pre>
<p>Correct!</p>
<h2>Two solutions in Python</h2>
<p>I offer two solutions in Python to illustrate different ways of solving this problem.
The first solution is iterative. It is similar to yours and you are already familiar with this way of thinking.
The second solution is a <a href="http://docs.python.org/tutorial/datastructures.html#list-comprehensions">list comprehension</a>,
which comes more from the <a href="http://en.wikipedia.org/wiki/Functional_programming">functional programming</a> paradigm.</p>
<pre><code>"""
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.
"""
def forLoops():
t = 0
for i in range(1,1000):
if i % 3 == 0 or i % 5 == 0:
t += i
return t
def listComp():
return sum([i for i in range(1,1000) if i % 3 == 0 or i % 5 == 0])
def test():
"""
Makes sure that they get the same answer: 233168
"""
a1 = forLoops()
a2 = listComp()
assert a1 == a2
return "True"
if __name__ == '__main__':
print __doc__
print "Test successful:", test()
</code></pre>
<p>List comprehensions are used often in Python and can be a very powerful construct.</p>
<h2>My feedback</h2>
<p>Both your solution and my two solutions are pretty inefficient. They are brute force
solutions to a potentially elegant problem. </p>
<p>First of all, we iterate over every number from 1 to 1000, when it is obvious
that most numbers, including 1 and 2, aren't multiples of 3 or 5. </p>
<p>And second, as we learned with the <a href="http://thousandnote.com/fizzbuzz.html">FizzBuzz</a> problem,
we can actually figure out exactly how many numbers are multiples of 3 and 5 with math. And
from there, a clever solution becomes much simpler!</p>
<h2>Elegance with math</h2>
<p>Remember how I explained how we can count the number of multiples of two numbers
with the inclusion-exclusion principle? Let's apply some of that here.</p>
<pre><code>Let |A| be the set of multiples of 3 below 1000
Let |B| be the set of multiples of 5 below 1000
</code></pre>
<p>Then,</p>
<pre><code>|A| = Floor(999/3) = 333
|B| = Floor(999/5) = 199
|A intersect B| = Floor(999/15) = 66
</code></pre>
<p>But how do you get the sum from this information? With a little help from
<a href="http://en.wikipedia.org/wiki/Arithmetic_progression">arithmetic progressions</a>.
Where <i>a</i><sub>1</sub> is the initial term and <i>a</i><sub>n</sub> the nth,
the sum of n terms is,</p>
<p><img src="http://upload.wikimedia.org/wikipedia/en/math/a/f/e/afe20f89d7bfdbd0a191168d80eb8077.png" alt="Arithmetic Progression" title="Arithmetic Progression" /></p>
<p>Hence, we come up with a formula, and the solution,</p>
<pre><code>3*333*(1+333)/2 + 5*199*(1+199)/2 - 15*66*(1+66)/2 = 233168
</code></pre>