Solutions to Euler problems posted online. This repository isn't meant to be a place for people to find answers, but just somewhere I can store my solutions, and compare them with my friends. Basic explanations are here too, so my friends will understand what I wrote. The solutions are meant to be as generic as possible, so if values in the questions change, only a few variable values need to be modified.
Q: Find the sum of all multiples of 3 or 5 under 1000A: For loop with cases divisible by 3 and 5, divisible by 3, and divisible by 5 Q: Find the sum of all fibonacci numbers less than 4 million
A: While loop Q: Find the largest prime factor of 600851475143
A: Loop dividing by smallest primes possible, until the remaining value is prime Q: Find the largest palindrome made by multiplying two 3-digit numbers
A: For loop multiplying combinations of 3-digit numbers and checking if the result is a palindrome Q: Find the smallest positive number divisible by all numbers from 1 to 20
A: Array to hold prime factors of values from 1 to 20. Find and store max of each prime factor using for loop. Multiply max of each prime factor from 1 to 20 to find the smallest value. Q: Compute the difference (1 + 2 + ... 100)2 - (12 + 22 + ... + 1002)
A: Use a for loop and the equation 1 + 2 + ... + n = (n+1)*n/2 Q: Find the 10001st prime
A: While loop of numbers until counter reaches 10001. For loop to determine if numbers are prime Q: Find the largest product of 13 adjacent digits in a 1000-digit number
A: For loop through the number stored as a string Q: Given a2 + b2 = c2 and a + b + c = 1000, find abc
A: For loop of numbers from 1 to 1000 based on the condition that a + b + c = 1000. Check to see if a2 + b2 = c2 Q: Find the sum of all primes below two million
A: For loop of all numbers under two million. For loop to check if numbers are prime Q: Given a 20x20 grid of numbers, find the largest product of four adjacent numbers in a straight line (up, down, left, right, diagonal)
A: For loop from top left to bottom right corner of grid, checking down, right, down-right diagonal, and down-left diagonal. Q: Find the first triangle number to have over five hundred divisors
A:
1) For loop triangle numbers
2) Prime factor triangle numbers by dividing by smallest possible prime. Store prime factors in array
3) If a number n can be expressed as ax * by *......., where a,b,... are primes, then:
Number of factors of n = (x+1)* (y+1) * ..... Q: Find the sum of the following one-hundred 50-digit numbers
A: Store numbers as strings, do addition by adding individual characters converted back to integers Q: What starting number under a million produces the longest chain using the Collatz Sequence?
Note: The Collatz sequence is as follows:
n -> n/2 (n is even)
n -> 3n + 1 (n is odd)
The sequence stops when n=1
A:
1) Create an array of size one millions, where the index of the array corresponds to the number
2) For loop of numbers from 1 to 1 000 000
3) If a number is encountered in a chain, flag it. The flag signifies a sequence does not need to be started at this number, since it is part of a longer sequence
4) Store the length of the sequence with the starting number
5) For loop of the array to find the longest sequence Q: Starting in the top left corner of a 20x20 grid, and only being able to move down and right, how many paths are there to the bottom right corner?
A: Number of paths to coordinates (i,j) = number of paths to (i-1, j) + number of paths to (i, j-1)
For loop to go through the array using this method Q: What is the sum of the digits of 21000
A: Similar to Euler_013, store numbers as strings, do multiplication by multiplying individual characters converted back to integers Q: If the numbers from 1 to 1000 were written out in words, how many letters would be used?
A: Array to hold number of letters given a number. For loop of the numbers from 1 to 1000 Q: Given a triangle of numbers, find the path that gives the maximum sum
A:
1) Store the numbers in an array, and find the height of the triangle
2) Start from the bottom row, and add the larger of two adjacent numbers to the number above it in the triangle. This can also be thought of as collapsing the triangle from the bottom-up
3) Repeat step 2 using recursion until there is only one number left. This number is the maximum
NOTE: This solution isn't the simplest, but also works with Euler_067 as well. Q: Find the number of months that started with a Sunday from Jan 1st 1901 to Dec 31st 2000
A: Array to hold number of days in each month, basic function to check whether year is a leap year. Counter to keep track of what day it is. Add the number of days in a month to the counter and see if it's a Sunday using the remainder when divided by 7 Q: Find the sum of the digits of 100!
A: Similar to Euler_016, store numbers as strings, do multiplication by multiplying individual characters converted back to integers Q: Let d(n) be the sum of proper divisors of n. If d(a)=b and d(b)=a, where a and b are not equal, then a and b are amicable numbers
Find the sum of all amicable numbers under 10000.
A:
1) Similar to Euler_012, we store the prime factors of numbers in an array
2) If a number n can be expressed as ax * by *......., where a,b,... are primes, then:
The sum of its divisors, s, is the sum of combinations of a0->x * b0->y *...
The sum of its proper divisors is therefore s - n
3) Create array of size 10000, where the index corresponds to what the cell represents
3) For loop to go through the numbers from 1 to 10000, with index i
4) Suppose d(i) = x and d(x) ≠ i. Since we aim to minimize runtime, we flag i as not amicable in the array, and now see if x is amicable. This continues until x is greater than 10000 or we find an amicable pair
5) Go through the array, and add the indexes of all cells that were flagged as amicable Q: Given a list of names, first sort them alphabetically
The score of a name is (product of the score of the digits, where A=1, B=2,......) * (index of the name in the sorted list)
Find the total score of the names
A: Sort the names using insertion sort. Then for loop through the array. Q: An abundant number is a number where the sum of its proper divisors is larger than the number itself
Given that all integers greater than 28123 can be written as the sum of two abundant numbers, find the sum of all positive integers which cannot be written as the sum of two abundant numbers
A:
1) Similar to Euler_021, we can use the same method to find the sum of a number's proper divisors
2) Find all numbers less than or equal to 28123 that are abundant, and store them in an array
3) Create another array of size 28124, where each index corresponds to the value the cell represents
4) Add all possible combinations of two abundant numbers, and flag these sums in the array defined in 3)
5) Go through the array, and add the indexes of all cells that were not flagged Q: Find the millionth lexicographic permutation of the digits 0,1,2,3,4,5,6,7,8, and 9
A:
1) If x digits follow the digit at index i, then the number of possible permutations following i is x!
2) For loop, starting at the left most digit. If the number of permutations of the remaining digits would be bigger than the max we are looking for, we cannot increase the digit we are currently on
3) Therefore, the left most digit is determined. Remove it from the list of possible digits, and subtract the number of permutations we have passed in the lexicographic order
4) Repeat recursively, until there is only one digit left Q: Find the index of the first term in the Fibonacci sequence with 1000 digits
A: Similar to Euler_013, store numbers as strings, do addition by adding individual characters converted back to integers