Project Euler/1: Difference between revisions

From charlesreid1
No edit summary
Line 1: Line 1:
This is problem 1 on Project Euler: https://projecteuler.net/problem=1
This is problem 1 on Project Euler: https://projecteuler.net/problem=1
=Overview of the Problem=


==Question==
==Question==
Line 7: Line 9:
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.)
Note that, if you've ever seen the fizz-buzz problem in computer science, this is the number-theory version.
 
==Why this problem==
 
Naturally, the very first Project Euler question will raise the question - why this one? Project Euler is a fantastic, complex, and difficult site involving many beautiful aspects of number theory. So why begin the journey at this problem in particular?
 
This problem shares many similarities, algorithm-wise, with the Sieve of Eratosthenes (at least, that's the idea.) With the Sieve of Eratosthenes, you begin with the smallest primes and work your way up by finding multiples of these primes and crossing them off the list of potential primes. In essence, ''this is the first question because it is the most fundamental operation of the most fundamental algorithm in number theory.''


==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==
* Use a set to store integers and avoid duplicates.


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.
* Given a maximum N, biggest number t hat can be a multiple of b is N/b.
* Generate numbers from 1 to N/b.
* Multiply them by b to generate numbers up to N that are multiples.


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
* Iterate over your set using a generator.


==Code==
<math>
( A \bigcup B ) \ C
</math>


<pre>
import java.util.Set;
import java.util.HashSet;


public class Euler {
public static void main(String[] args) {
// Maximum
int max = 100;
// Multiples list
int[] multiplesList = {3,5};
// Results set
Set<Integer> s = new HashSet<Integer>();


// From 1 up to and including (max-1)/multiple (not max/multiple-1)
for(int m=0; m<multiplesList.length; m++) {
int multiple = multiplesList[m];
for(int i=1; i<=((max-1)/multiple); i++) {
int num = i*multiple;
s.add(num);
}
}
// Sum them all up
int sum = 0;
for(Integer i : s) {
sum += i;
}
System.out.println("sum = "+sum);
}


}
</pre>




Revision as of 09:01, 20 July 2017

This is problem 1 on Project Euler: https://projecteuler.net/problem=1

Overview of the Problem

Question

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.

Note that, if you've ever seen the fizz-buzz problem in computer science, this is the number-theory version.

Why this problem

Naturally, the very first Project Euler question will raise the question - why this one? Project Euler is a fantastic, complex, and difficult site involving many beautiful aspects of number theory. So why begin the journey at this problem in particular?

This problem shares many similarities, algorithm-wise, with the Sieve of Eratosthenes (at least, that's the idea.) With the Sieve of Eratosthenes, you begin with the smallest primes and work your way up by finding multiples of these primes and crossing them off the list of potential primes. In essence, this is the first question because it is the most fundamental operation of the most fundamental algorithm in number theory.

Solution

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

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.

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

$ ( A \bigcup B ) \ C $







Euler.jpg
Project Euler
project euler notes

Project Euler

Grid 0: Problems 1-99

Problem 1  · Problem 2  · Problem 3  · Problem 4  · Problem 5  · Problem 6  · Problem 7  · Problem 8  · Problem 9  · Problem 10

Problem 11  · Problem 12  · Problem 13  · Problem 14  · Problem 15  · Problem 16  · Problem 17  · Problem 18  · Problem 19  · Problem 20

Problem 27  · Problem 28  · Problem 29  · Problem 30

Problem 31  · Problem 32  · Problem 33  · Problem 40

Problem 41  · Problem 42  · Problem 43  · Problem 44  · Problem 45  · Problem 46  · Problem 47  · Problem 48  · Problem 49  · Problem 50

Problem 51  · Problem 52  · Problem 53  · Problem 54  · Problem 55  · Problem 56  · Problem 57  · Problem 58  · Problem 59  · Problem 60

Problem 61  · Problem 62  · Problem 63  · Problem 64  · Problem 65  · Problem 66  · Problem 67  · Problem 68  · Problem 69  · Problem 70

Grid 1: Problems 100-199

...

Problem 110  · Problem 111  · Problem 112  · Problem 113  · Problem 114  · Problem 115  · Problem 116  · Problem 117  · Problem 118  · Problem 119

Problem 150  · Problem 151  · Problem 152  · Problem 153  · Problem 154  · Problem 155  · Problem 156  · Problem 157  · Problem 158  · Problem 159

...

Problem 170  · Problem 171  · Problem 172  · Problem 173  · Problem 174  · Problem 175  · Problem 176  · Problem 177  · Problem 178  · Problem 179

...


Problem 190  · Problem 191  · Problem 192  · Problem 193  · Problem 194  · Problem 195  · Problem 196  · Problem 197  · Problem 198  · Problem 199


Grid 2: Problems 200-299

Problem 227  · Problem 254


Grid 3: Problems 300-399


Problem 301  · Problem 310

Problem 312  · Problem 319

Problem 323  · Problem 328

Problem 334  · Problem 337

Problem 345  · Problem 346

Problem 355  · Problem 356

Problem 364  · Problem 367

Problem 373  · Problem 378

Problem 382  · Problem 389

Problem 391

Grid 4: Problems 400-499

Problem 400


Grid 5: Problems 500-599

Problem 500  · Problem 501  · Problem 502


Grid 9: Problems 900-999

Problem 932


* = in progress

Flags  · Template:ProjectEulerFlag  · e


Retrieved from "https://charlesreid1.com/w/index.php?title=Project_Euler/1&oldid=19849"