Welcome to my Project Euler Blog
Hi, I'm Charlotte! Welcome to my blog where I document my journey through solving problems on Project Euler.
I am new to the world of coding and was recommended to sign up to Project Euler.
I jumped at the opportunity as it seemed like a perfect place to practise my coding, improve my logic and keep my maths skills sharp.
This is where I will document my journey through solving problems on Project Euler.
Project Euler is a collection of challenging mathematical and computational problems that require more than just mathematical insights to solve. A good understanding of programming is also necessary.
I will be sharing my solutions, thought processes, and any challenges I encounter along the way, in the hope to help further my own abilities and also guide you with my own misconceptions.
Feel free to explore my blog and follow along as I tackle these intriguing problems!
Problem 0: Sum of the Odd Squares
Among the first 636 thousand square numbers, what is the sum of all the odd squares?
Language used: C++
This is the initial porblem you need to solve in order to get started on Project Euler.
When I started writing my code for this problem I was getting the incorrect answer and couldn't work out why as I knew my maths logic was correct.
By using the code below, I found I was getting negative square numbers, which obviously made zero sense as all square numbers are positive.
std::cout << "The last square number is " << squares.back() << std::endl;
This was because I had used 'int' instead of 'long int' when defining my vectors.
Once I changed this, I was able to get the correct answer.
My Solution
#include
#include
int main() {
std::vector squares;
for(long int i = 1; i <= 636000 ; i++){
squares.push_back(i*i);
}
std::vector odd_squares;
for(long int a = 0; a < squares.size(); a++){
if (squares[a] % 2 != 0){
odd_squares.push_back(squares[a]);
}
}
long int odd_sum = 0;
for (long int c = 0; c < odd_squares.size(); c++){
odd_sum += odd_squares[c];
}
std::cout << "The sum of odd squares is " << odd_sum << std::endl;
return 0;
}
Problem 1: Multiples of 3 or 5
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.
Language used: C++
This was a great problem to start with as it was fairly straightforward and I was able to solve it fairly quickly. I used a for loop to iterate through all the numbers below 1000 and an if statement to check if each number was a multiple of 3 or 5. But found I still got the wrong answer. I'm starting to think this is a common theme with my coding journey so far!
After editing the code to test with smaller numbers, I found that I was including 1000 in my calculations when I should not have been.
Once I realised my mistake it was an easy fix and then I got the correct answer.
My Solution
#include
int main() {
//Create variables
std::vector below1000 = {};
int sum = 0;
//Loop through numbers below 1000
for(int i = 1; i < 1000; i++) {
//Check if number is a multiple of 3 or 5
if(i % 3 == 0 || i % 5 == 0) {
below1000.push_back(i);
sum += i; //Add to sum
}
}
//Output result
std::cout << "The sum of all multiples of 3 or 5 below 1000 is: " << sum << std::endl;
return 0;
}
Problem 2: Even Fibonacci Numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
Language used: C++
When I saw this problem, I thought 'easy'. Again, Project Euler has taught me to eat my words as even though the logic of how to complete this seems easy, getting my code to do what I want is less so.
My intinct was to first create a vector by using a for and while loop to add the two previous elements to create the next. I first tried this with a smaller value so it would be easier to see if my code works correctly. I tried to do a while loop nested inside a for loop.
for(int i=2; i <= 20; i++){
int c = 0;
while(c <= 40){
c = fib_seq[i-1] + fib_seq[i-2];
fib_seq.push_back(c);
}
}
But this just created an endless loop, so I tried doing a for loop inside a while loop to see if I got a complete Fibonacci sequence.
int c;
while(c <= 40){
c = 0;
for(int i=2; i <= 20; i++){
c = fib_seq[i-1] + fib_seq[i-2];
fib_seq.push_back(c);
}
Despite not creating an endless loop and populating my fib_seq vector, because the for loop is inside the while loop it completely ignores the while condition and just completes the process until it has created 21 elements. My next thought is to stick with a for loop, but nest an if conditional inside.
It worked! After a slight adaptation of my original code, giving c the value of the 3 and swapping the order of the executed code, I have a Fibonacci sequence that doesn't exceed 40. Continuing on the path of using a smaller value to make it easier to check I now plan to create a new vector of just the even values. To do this I will do a for loop with a nested if conditional checking the remainder when divided by 2.
//for loop and if conditional to fill the even_fib vector
for(int i = 0; i < fib_seq.size(); i++){
if(fib_seq[i]%2==0){
even_fib.push_back(fib_seq[i]);
}
}
Next, I had to find the sum of all the even numebrs and print to console. Once I completed this and checked that I got the correct answer, it was time to change the number from 40 to 4000000 and get the answer.
I happy to say that I got the correct answer!
My Solution
#include
#include
int main() {
//Create vectors for sequences
std::vectorfib_seq={1, 2};
std::vectoreven_fib;
//for loop and if conditional to fill the fib_seq vector
int c = 3;
for(int i = 3; i <= 20000; i++){
if (c <= 4000000){
fib_seq.push_back(c);
c = fib_seq[i-1] + fib_seq[i-2];
}
}
//for loop and if conditional to fill the even_fib vector
for(int i = 0; i < fib_seq.size(); i++){
if(fib_seq[i]%2==0){
even_fib.push_back(fib_seq[i]);
}
}
//for loop to find the sum of all the even terms
int even_sum = 0;
for(int i = 0; i < even_fib.size(); i++){
even_sum += even_fib[i];
}
//print sum of even_fib
std::cout << "The sum of all the even values less than or equal to 4 000 000 is " << even_sum;
}
Problem 3: Largest Prime Factor
The prime factors of 13195 are 5, 7, 13 and 19.
What is the largest prime factor of the number 600851475143?
Language used: JavaScript
I decided to challenge myself more and use JavaScript for this problem.
My first thought was to find all the factors of value, so I wrote the code below to do this. But this proved impossible as there were too many for my array.
//Find factors of value
for(let l = 1; l<=number; l++){
if(number % l == 0){
factors.push(l)
}
}
I found this problem really difficult, I initially made the same mistake I made previously and didn't read the problem well enough. I originally tried to find the largest prime number under 600851475143, which was proving a problem as I couldn't make an array big enough.
Once I noticed my mistake, I decided to make an array of all the prime numbers below the squareroot of 600851475143, as the quickest way to test is a number is a prime number is to divide it by the prime numbers.
I used for loops paired with if conditionals to create an array of prime factors of the value. Finally, I used Math.max() to find the largest prime factor.
My Solution
//Create variables
const number = 600851475143
let factors=[]
const primeFactors =[]
const primeNumbers =[2]
//Function to test if number is a prime number
function isPrime(n) {
// Check from 2 to n-1
for (let i = 2; i < n; i++){
if (n % i == 0){
return false;
}
}
return true;
}
//Loop to fill primeNumber array
for (let k = 3; k <= Math.sqrt(number); k++){
if(isPrime(k)==true){
primeNumbers.push(k);
}
}
//Loop to see what prime numbers can be divided into the number
for(i=0; i<=primeNumbers.length; i++){
if(number%primeNumbers[i]==0){
primeFactors.push(primeNumbers[i])
}
}
//find the max value
const largestPrimeFactor = Math.max(...primeFactors);
//print to console
console.log(largestPrimeFactor);
Problem 4: Largest Palindrome Product
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.
Find the largest palindrome made from the product of two 3-digit numbers.
Language used: JavaScript
My first instinct was to create two empty arrays; one for all the products of 3-digit numbers and the other for all the palindrone products. After creating these I used a for loop and the .toString() function to convert each item in the arrange to strings and then compare them with the reverse by using .split('').reverse().join(''). Then once checking they were the same I used the .push() function to put them into the palindroneProducts array.
for (let i = 0; i < products.length; i++){
//original converted to string
const original = products[i].toString();
//reverse the original
const reverse = original.split('').reverse().join("");
//check if they are equal with a conditional
if (original === reverse) {
palindroneProducts.push(products[i]);
}
}
Everything seemed to be going well until I found the index of the last value and that number wasn't correct. Suddenly it hit me! I hadn't sorted the array, so I quickly fixed this with .sort() function and tried again. Still the wrong answer, at this point I had to take to the internet and do some research. It turns out .sort() only works on strings. So after using the below code to sort my values, I finally for the correct answer.
//order the array in ascending order
palindroneProducts.sort(function(a,b) {return a - b});
My Solution
//Array for all products
var products = [];
palindroneProducts = [];
for(let a = 100; a < 1000; a++) {
for (let b = 100; b < 1000; b++)
products.push(a*b);
}
for (let i = 0; i < products.length; i++){
//original converted to string
const original = products[i].toString();
//reverse the original
const reverse = original.split('').reverse().join("");
//check if they are equal with a conditional
if (original === reverse) {
palindroneProducts.push(products[i]);
}
}
//order the array in ascending order
palindroneProducts.sort(function(a,b) {return a - b});
//find the index of the final number
const index = (palindroneProducts.length)-1;
//print to console
console.log(palindroneProducts[index]);
Problem 5: Smallest Multiple
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
Language used: C++
The way that I tackled this problem was definitely not the tidiest. However, I struggled to work out how to use a for loop to check if it is divisible by all numbers between 1 and 20, though this must be possible so it is something I shall look more into in the future. My first thought was to create a vector for each multiples of 1 to 20, as below, but then I quickly realised this was a waste of time.
std::vector <int> divisible_by_1 = {};
std::vector <int> divisible_by_2 = {};
std::vector <int> divisible_by_3 = {};
After scrapping this idea, I then decided down the root of using nested if conditionals. This would check to see if it is divisible by 1 and if it was move on to 2, then 3 and so on. Obviously, checking if it is divisible by 1 is a complete waste of time as every integer is divisible by 1, however I included it for completion of the check. As I didn't know how many loops I would need to do I std::cout the vector size to the terminal, as the first loop was i < 200000 it returned a vector size of 0. Thus I had to increase the stopping conditional and retest. Once I got a vector size of 3, I used std::cout << answer[0]; to get the smallest number in the vector.
std::cout << answer.size();
std::cout << answer[0];
This gave me, you guessed it, the wrong answer. It took me 2 minutes to work out why. I noticed it hadn't printed answer.size and answer[0] on seperate lines, which when I copied it into the website put a random 3 (the vector size) in front of the correct answer.
My Solution
#include
#include
int main() {
// Variable for smallest value
std::vector answer = {};
//nested for loop to divide by each number
for (long int i = 1; i < 900000000; i++) {
if (i % 1 == 0) {
if (i % 2 == 0) {
if (i % 3 == 0) {
if (i % 4 == 0) {
if (i % 5 == 0) {
if (i % 6 == 0) {
if (i % 7 == 0) {
if (i % 8 == 0) {
if (i % 9 == 0) {
if (i % 10 == 0) {
if (i % 11 == 0) {
if (i % 12 == 0) {
if (i % 13 == 0) {
if (i % 14 == 0) {
if (i % 15 == 0) {
if (i % 16 == 0) {
if (i % 17 == 0) {
if (i % 18 == 0) {
if (i % 19 == 0) {
if (i % 20 == 0) {
answer.push_back(i);
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
std::cout << answer.size() << "\n";
std::cout << answer[0];
}
Problem 6: Sum Square Difference
The sum of the squares of the first ten natural numbers is,
12 + 22 + ... + 102 = 385.
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)2 = 552 = 3025.
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is
3025 - 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
Language used: C++
I really liked the look of this one, as my maths brain very quickly started to split the two variables up and started writing a for loop to go through the numbers 1 to 100. Despite feeling confident in my ability to solve this problem, history has shown me that even though I have the correct logic, my code doesn't always work out as inteneded, so I made sure to check that each part was working after each step by using the number in the example and printing my variables to the console for comparison.
// Testing
std::cout << "sum of the square is " << sum_of_square << "\n";
std::cout << "sum of the first 10 numbers is " << sum << "\n";
std::cout << "square of the sum is " << square_of_sum << "\n";
Another thought I had while completing this problem was I didn't know how big the numbers were going to be, so to ensure that the values were included I used long int, as I was not falling into that trap again.
One final thought was I wanted the difference to be positive, I could easily just copy the answer and ignore a negative symbol, but if I was serious about improving my coding I decided to put a conditional into my code.
//Ensure difference is postiive
if (diff < 0) {
diff = diff * -1;
}
My Solution
#include
#include
// Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
int main() {
// Create variables for both values
long int sum_of_square = 0;
long int sum = 0;
long int square_of_sum;
// Make a loop for sum of square numbers
for (int i = 1; i <= 100; i++) {
sum_of_square = sum_of_square + (i * i);
}
// Make a loop for the sum
for (int j = 1; j <= 100; j++) {
sum = sum + j;
}
// Square the sum
square_of_sum = sum * sum;
// Testing
std::cout << "sum of the square is " << sum_of_square << "\n";
std::cout << "sum of the first 100 numbers is " << sum << "\n";
std::cout << "square of the sum is " << square_of_sum << "\n";
// Difference between
long int diff = sum_of_square - square_of_sum;
//Ensure difference is postiive
if (diff < 0) {
diff = diff * -1;
}
// Solution
std::cout << "The difference bettwen the sum of the quares and the square of the sum is " << diff << "\n";
}