Project Euler/1 - Revision history

Admin: /* Going Deeper */

2017-07-22T10:36:59Z

Going Deeper

← Older revision		Revision as of 10:36, 22 July 2017
Line 21:		Line 21:
	We can come up with a simple solution that uses a bit vector to represent integers, or we can toss numbers into a set (which, under the hood, is likely using a similar representation anyway). Given our maximum N, and our two numbers a and b, we can allocate a boolean array with that many integers, set them all to false, then walk through the list in intervals of 3 and 5, flipping the booleans to true as we go.		We can come up with a simple solution that uses a bit vector to represent integers, or we can toss numbers into a set (which, under the hood, is likely using a similar representation anyway). Given our maximum N, and our two numbers a and b, we can allocate a boolean array with that many integers, set them all to false, then walk through the list in intervals of 3 and 5, flipping the booleans to true as we go.

	==Going Deeper==		==Going Deeper: An Example==

	It's true that this problem seems a bit boring on its face. But let's dive deeper. Suppose I asked you to find the number of multiples of the integers 3 and 4, but not the integer 5, below 2,001 - and to do so without explicitly enumerating them with a computer.		It's true that this problem seems a bit boring on its face. But let's dive deeper. Suppose I asked you to find the number of multiples of the integers 3 and 4, but not the integer 5, below 2,001 - and to do so without explicitly enumerating them with a computer.

Admin: /* Going Deeper */

2017-07-20T09:47:27Z

Going Deeper

← Older revision		Revision as of 09:47, 20 July 2017
Line 38:		Line 38:

	So we will add the items in <math>A \bigcap B \bigcap C</math> back into the final set.		So we will add the items in <math>A \bigcap B \bigcap C</math> back into the final set.

			Visually representing A, B, and C with a Venn diagram,

			[[Image:ProjectEuler1.png\|500px]]

	To get back to the problem at hand, we can compute the size of these sets using the floor function. For example, the cardinality of A is:		To get back to the problem at hand, we can compute the size of these sets using the floor function. For example, the cardinality of A is:

Admin: /* Going Deeper */

2017-07-20T09:24:46Z

Going Deeper

← Older revision		Revision as of 09:24, 20 July 2017
Line 89:		Line 89:
	</math>		</math>

			=Flags=

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

			[[Category:Prime Numbers]]
			[[Category:Sequences]]
			[[Category:Combinatorics]]
			[[Category:Number Theory]]

Admin: /* Going Deeper */

2017-07-20T09:24:08Z

Going Deeper

← Older revision		Revision as of 09:24, 20 July 2017
Line 35:		Line 35:
	Next, we can count <math>A \bigcap C</math> and <math>B \bigcap C</math>, which are the multiples of a and b that we counted that we should not have because they are multiples of c.		Next, we can count <math>A \bigcap C</math> and <math>B \bigcap C</math>, which are the multiples of a and b that we counted that we should not have because they are multiples of c.

	Finally, we cannot forget <math>A \bigcap B \bigcap C</math> - numbers that have a, b, and c as multiples.		Finally, we cannot forget <math>A \bigcap B \bigcap C</math> - numbers that have a, b, and c as multiples. This case is a bit tricky. Any item that is in <math>A \bigcap B \bigcap C</math> has already been removed - twice. The first time was when it was removed because it was in <math>A \bigcap C</math>, and the second time was when it was removed because it was in <math>B \bigcap C</math>. Therefore, we must add each of these items back in, to account for the double-removal and ensure these items are only removed once.

			So we will add the items in <math>A \bigcap B \bigcap C</math> back into the final set.

	To get back to the problem at hand, we can compute the size of these sets using the floor function. For example, the cardinality of A is:		To get back to the problem at hand, we can compute the size of these sets using the floor function. For example, the cardinality of A is:
Line 63:		Line 65:
	</math>		</math>

	And last but not least, those numbers with a, b, and c as factors:		And last but not least, those numbers with a, b, and c as factors were just removed twice, so we add them back in once:

	<math>		<math>
Line 75:		Line 77:
	- \mbox{floor}\left( \frac{N}{ab} \right)		- \mbox{floor}\left( \frac{N}{ab} \right)
	- \mbox{floor}\left( \frac{N}{ac} \right) - \mbox{floor}\left( \frac{N}{bc} \right)		- \mbox{floor}\left( \frac{N}{ac} \right) - \mbox{floor}\left( \frac{N}{bc} \right)
	- \mbox{floor}\left( \frac{N}{abc} \right)		+ \mbox{floor}\left( \frac{N}{abc} \right)
	</math>		</math>

Line 82:		Line 84:
	<math>		<math>
	\begin{align}		\begin{align}
	M &=& 667 + 500 - 166 - 133 - 100 - 33 \\		M &=& 667 + 500 - 166 - 133 - 100 + 33 \\
	M &=& ~~735~~		M &=& 801
	\end{align}		\end{align}
	</math>		</math>

Admin: /* Going Deeper */

2017-07-20T09:18:40Z

Going Deeper

← Older revision		Revision as of 09:18, 20 July 2017
Line 81:		Line 81:

	<math>		<math>
	\begin{~~array~~}		\begin{align}
	M &=& 667 + 500 - 166 - 133 - 100 - 33 \\		M &=& 667 + 500 - 166 - 133 - 100 - 33 \\
	M &=& 735		M &=& 735
	\end{~~array~~}		\end{align}
	</math>		</math>


	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Admin: /* Going Deeper */

2017-07-20T09:18:07Z

Going Deeper

← Older revision		Revision as of 09:18, 20 July 2017
Line 84:		Line 84:
	M &=& 667 + 500 - 166 - 133 - 100 - 33 \\		M &=& 667 + 500 - 166 - 133 - 100 - 33 \\
	M &=& 735		M &=& 735
			\end{array}
	</math>		</math>


	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Admin: /* Going Deeper */

2017-07-20T09:17:48Z

Going Deeper

@@ Line 40: / Line 40: @@
 <math>
-\mbox{card}(A) = \mbox{floor}\left( \frac{2001}{3} \right)
+\mbox{card}(A) = \mbox{floor}\left( \frac{2001}{3} \right) = 667
 </math>
 {{ProjectEulerFlag}}

Admin: /* Going Deeper */

2017-07-20T09:09:41Z

Going Deeper

← Older revision		Revision as of 09:09, 20 July 2017
Line 23:		Line 23:
	==Going Deeper==		==Going Deeper==

	It's true that this problem seems a bit boring on its face. But let's dive deeper. Suppose I asked you to find the number of multiples of the integers 3 and 4, but not the integer 5, below 2,~~000~~ - and to do so without explicitly enumerating them with a computer.		It's true that this problem seems a bit boring on its face. But let's dive deeper. Suppose I asked you to find the number of multiples of the integers 3 and 4, but not the integer 5, below 2,001 - and to do so without explicitly enumerating them with a computer.

	To do this, we can express the problem in set notation. We have three sets, A, B, C, containing multiples of 3, 4, and 5, respectively. In set theory language, we wish to find		To do this, we can express the problem in set notation. We have three sets, A, B, C, containing multiples of 3, 4, and 5, respectively. In set theory language, we wish to find

	<math>		<math>
	( A \bigcup B ) \ C		( A \bigcup B ) \backslash C
	</math>		</math>

			We can start by counting the sets A and B, as well as accounting for <math>A \bigcap B</math> (numbers that are multiples of both a and b).

			Next, we can count <math>A \bigcap C</math> and <math>B \bigcap C</math>, which are the multiples of a and b that we counted that we should not have because they are multiples of c.

			Finally, we cannot forget <math>A \bigcap B \bigcap C</math> - numbers that have a, b, and c as multiples.

			To get back to the problem at hand, we can compute the size of these sets using the floor function. For example, the cardinality of A is:

			<math>
			\mbox{card}(A) = \mbox{floor}\left( \frac{2001}{3} \right)
			</math>

Admin at 09:01, 20 July 2017

2017-07-20T09:01:58Z

@@ Line 1: / Line 1: @@
 This is problem 1 on Project Euler: https://projecteuler.net/problem=1
 ==Question==
@@ Line 7: / Line 9: @@
 Find the sum of all the multiples of 3 or 5 below 1000.
-(This is essentially the fizz buzz problem, but with a practical application.)
+Note that, if you've ever seen the fizz-buzz problem in computer science, this is the number-theory version.
-==Approach==
+=Solution=
-Two-part problem: enumerating multiples of 3 or 5, and summing them up.
+We can come up with a simple solution that uses a bit vector to represent integers, or we can toss numbers into a set (which, under the hood, is likely using a similar representation anyway). Given our maximum N, and our two numbers a and b, we can allocate a boolean array with that many integers, set them all to false, then walk through the list in intervals of 3 and 5, flipping the booleans to true as we go.
-Data structure:
+==Going Deeper==
-Task 1: generate all multiples of b, up to a given maximum N.
+It's true that this problem seems a bit boring on its face. But let's dive deeper. Suppose I asked you to find the number of multiples of the integers 3 and 4, but not the integer 5, below 2,000 - and to do so without explicitly enumerating them with a computer.
-Task 2: sum them up.
+To do this, we can express the problem in set notation. We have three sets, A, B, C, containing multiples of 3, 4, and 5, respectively. In set theory language, we wish to find
-==Code==
+<math>

Admin: /* Question */

2017-07-11T01:46:04Z

Question

← Older revision		Revision as of 01:46, 11 July 2017
Line 6:		Line 6:

	Find the sum of all the multiples of 3 or 5 below 1000.		Find the sum of all the multiples of 3 or 5 below 1000.

			(This is essentially the fizz buzz problem, but with a practical application.)

	==Approach==		==Approach==