commit 5c07fe3d134bd5082ca0268c4abf1f26fe87cf69
Author: mpizzzle <michael.770211@gmail.com>
Date: Sun, 19 Jun 2016 13:20:36 +0100
initial commit. copied from previous github account, didn't want to fork though
Diffstat:
84 files changed, 3919 insertions(+), 0 deletions(-)
diff --git a/Euler.h b/Euler.h
@@ -0,0 +1,85 @@
+#include "EulerUtility.h"
+
+class Euler
+{
+public:
+ int SumOfMultiplesOf3And5Ceiling1000();
+ int SumOfEvenFibonacciNumbersCeiling4m();
+ llui LargestPrimeFactor();
+ int LargestPalindromeFrom3DigitProduct();
+ int DivisibleBy1To20();
+ int DifferenceSumOfSquaresSquareOfSum100();
+ int Get10001stPrime();
+ llui FindGreatestProductOf13AdjacentDigits();
+ int SpecialPythagoreanTriplet();
+ llui SumOfPrimesUnder2m();
+ int LargestProductInGrid();
+ llui TriangleNoWithGreaterThan500Divisors();
+ std::string LargeSum();
+ llui CollatzConjecture();
+ BigInteger LatticePaths();
+ int DigitSum();
+ int LetterCounter();
+ int MaximumPathSum();
+ int SundayCount();
+ llui FactorialDigitSum();
+ int AmicableNumbers();
+ llui NameScores();
+ int NonAbundantSums();
+ std::string LexicographicPermutations();
+ int ThousandDigitFibonacciNumber();
+ int ReciprocalCycles();
+ int QuadraticPrimes();
+ long SpiralDiagonals();
+ int DistinctPowers();
+ long DigitFifthPowers();
+ int CoinSums();
+ int PanDigitalProducts();
+ int DigitCancellingFractionsDenominator();
+ llui DigitFactorials();
+ int NoOfCircularPrimes();
+ llui DoubleBasedPalindromes();
+ llui TruncatablePrimes();
+ int PanDigitalMultiples();
+ int MaximumRightAngledTriangles();
+ int ChampernowneConstant();
+ int PanDigitalPrime();
+ int CodedTriangleNumbers();
+ BigInteger SubStringDivisibility();
+ int MinimizedPentagonalDifference();
+ llui TriangularPentagonalHexagonal();
+ llui GoldbachsOtherConjecture();
+ int DistinctPrimeFactors();
+ BigInteger SelfPowers();
+ std::string PrimePermutations();
+ int ConsecutivePrimeSum();
+ int PrimeDigitReplacements();
+ int PermutedMultiples();
+ int CombinatoricSelections();
+ int PokerHands();
+ BigInteger LychrelNumbers();
+ int PowerfulDigitSum();
+ int SquareRootConvergents();
+ ll SpiralPrimes();
+ int xorDecryption();
+ int PrimePairSets();
+ int CyclicFigurateNumbers();
+ llui CubicPermutations();
+ int PowerfulDigitCounts();
+ int OddPeriodSquareRoots();
+ int ConvergentsOfE();
+ int Diophantine();
+ std::string Magic5GonRing();
+ int EulerTotient();
+ int TotientPermutation();
+ int OrderedFractions();
+ llui CountingFractions();
+ llui CountingRangedFractions();
+ int DigitFactorialChains();
+ int UniquePerimeterRightAngledTriangles();
+ int CountingSums();
+ int PrimeSummations();
+ llui CoinPartitions();
+ std::string PasscodeDerivation();
+ int SquareRootDigitalExpansion();
+};+
\ No newline at end of file
diff --git a/EulerUtility.cpp b/EulerUtility.cpp
@@ -0,0 +1,481 @@
+#include <fstream>
+#include <numeric>
+#include <regex>
+#include <sstream>
+#include <unordered_set>
+
+#include "EulerUtility.h"
+
+int EulerUtility::multiply(int x, int y)
+{
+ return x * y;
+}
+
+int EulerUtility::sumOfDivisors(int n)
+{
+ int prod = 1;
+
+ for(int k = 2; k * k <= n; ++k)
+ {
+ int p = 1;
+
+ while(n % k == 0)
+ {
+ p = p * k + 1;
+ n /= k;
+ }
+
+ prod *= p;
+ }
+
+ if(n > 1)
+ prod *= 1 + n;
+
+ return prod;
+}
+
+std::vector<int> EulerUtility::getPrimesUnderCeiling(int ceiling)
+{
+ std::vector<int> primes;
+
+ primes.push_back(2);
+ primes.push_back(3);
+
+ bool is_prime;
+
+ for(int i = 5; i < ceiling; i += 2)
+ {
+ is_prime = true;
+
+ for(int j = 3; j * j <= i && is_prime; j += 2)
+ if(i % j == 0) is_prime = false;
+
+ if(is_prime)
+ primes.push_back(i);
+ }
+
+ return primes;
+}
+
+std::vector<int> EulerUtility::getPrimesUnderCeilingIndexed(int ceiling)
+{
+ std::vector<int> primes;
+
+ primes.push_back(-1);
+ primes.push_back(-1);
+ primes.push_back(2);
+ primes.push_back(3);
+ primes.push_back(-1);
+
+ bool is_prime;
+
+ for(int i = 5; i < ceiling; i += 2)
+ {
+ is_prime = true;
+
+ for(int j = 3; j * j <= i && is_prime; j += 2)
+ if(i % j == 0) is_prime = false;
+
+ if(is_prime)
+ {
+ primes.push_back(i);
+ primes.push_back(-1);
+ }
+ else
+ {
+ primes.push_back(-1);
+ primes.push_back(-1);
+ }
+ }
+
+ return primes;
+}
+
+std::vector<int> EulerUtility::tokenizer(std::string s, char delim)
+{
+ std::istringstream split(s);
+ std::vector<int> tokens;
+ for (std::string each; std::getline(split, each, delim); tokens.push_back(atoi(each.c_str())));
+
+ return tokens;
+}
+
+std::vector<std::string> EulerUtility::strTokenizer(std::string s, char delim)
+{
+ std::istringstream split(s);
+ std::vector<std::string> tokens;
+ for (std::string each; std::getline(split, each, delim); tokens.push_back(each));
+
+ return tokens;
+}
+
+std::vector<int> EulerUtility::factorialDigits(int n)
+{
+ std::vector<int> digits(1, 1);
+
+ for (int i = 1; i <= n; ++i)
+ {
+ for (unsigned j = 0; j < digits.size(); ++j)
+ digits[j] *=i;
+
+ for (unsigned j = 0; j < digits.size(); ++j)
+ {
+ if (digits[j] >= 10)
+ {
+ int carry = (digits[j] - (digits[j] % 10)) / 10;
+ digits[j] = digits[j] % 10;
+
+ if (j == digits.size() - 1)
+ digits.push_back(carry);
+ else
+ digits[j + 1] += carry;
+ }
+ }
+ }
+
+ return digits;
+}
+
+std::vector<int> EulerUtility::powerDigits(int n, int p)
+{
+ std::vector<int> digits = intToDigits(n);
+ std::reverse(digits.begin(), digits.end());
+
+ for (int i = 1; i < p; ++i)
+ {
+ for (unsigned j = 0; j < digits.size(); ++j)
+ digits[j] *=n;
+
+ for (unsigned j = 0; j < digits.size(); ++j)
+ {
+ if (digits[j] >= 10)
+ {
+ int carry = (digits[j] - (digits[j] % 10)) / 10;
+ digits[j] = digits[j] % 10;
+
+ if (j == digits.size() - 1)
+ digits.push_back(carry);
+ else
+ digits[j + 1] += carry;
+ }
+ }
+ }
+
+ return digits;
+}
+
+BigInteger EulerUtility::bigFactorial(BigInteger n)
+{
+ if (n == 0)
+ return 1;
+ return n * bigFactorial(n - 1);
+}
+
+int EulerUtility::factorial(int n)
+{
+ if (n == 0)
+ return 1;
+ return n * factorial(n - 1);
+}
+
+BigInteger EulerUtility::choose(int n, int k)
+{
+ return EulerUtility::bigFactorial(n) / (EulerUtility::bigFactorial(k) * EulerUtility::bigFactorial(n - k));
+}
+
+bool EulerUtility::isPerfectSquare(llui n)
+{
+ if (n < 0)
+ return false;
+
+ llui tst = (llui)(sqrt(n) + 0.5);
+ return tst*tst == n;
+}
+
+bool EulerUtility::isPerfectCube(llui n)
+{
+ if (n < 0)
+ return false;
+
+ llui tst = (llui)std::floor(std::pow(n, 1/3.) + 0.5);
+ return n == tst * tst * tst;
+}
+
+std::vector<int> EulerUtility::intToDigits(int n)
+{
+ std::vector<int> digitArray;
+
+ while (n != 0)
+ {
+ digitArray.push_back(n % 10);
+ n /= 10;
+ }
+
+ std::reverse(digitArray.begin(), digitArray.end());
+
+ return digitArray;
+}
+
+std::vector<int> EulerUtility::lluiToDigits(llui n)
+{
+ std::vector<int> digitArray;
+
+ while (n != 0)
+ {
+ digitArray.push_back(n % 10);
+ n /= 10;
+ }
+
+ std::reverse(digitArray.begin(), digitArray.end());
+
+ return digitArray;
+}
+
+std::vector<int> EulerUtility::BigIntToDigits(BigInteger n)
+{
+ std::vector<int> digitArray;
+
+ while (n != 0)
+ {
+ digitArray.push_back((n % 10).toInt());
+ n /= 10;
+ }
+
+ std::reverse(digitArray.begin(), digitArray.end());
+
+ return digitArray;
+}
+
+int EulerUtility::digitsToInteger(std::vector<int> d)
+{
+ std::stringstream ss;
+
+ for (int i : d)
+ ss << i;
+
+ int integer;
+ ss >> integer;
+
+ return integer;
+}
+
+llui EulerUtility::digitsTollui(std::string s)
+{
+ std::stringstream ss;
+
+ for (char c : s)
+ ss << c;
+
+ llui digits;
+ ss >> digits;
+
+ return digits;
+}
+
+bool EulerUtility::hasUniqueDigits(int n, bool allowZero)
+{
+ std::vector<int> digits = EulerUtility::intToDigits(n);
+
+ std::unordered_set<int> uniqueDigits;
+
+ for (int digit : digits)
+ {
+ if (digit == 0 && !allowZero)
+ return false;
+
+ uniqueDigits.insert(digit);
+ }
+
+ return digits.size() == uniqueDigits.size();
+}
+
+/*
+* calculates (a * b) % c taking into account that a * b might overflow
+*/
+ll mulmod(ll a, ll b, ll mod)
+{
+ ll x = 0,y = a % mod;
+ while (b > 0)
+ {
+ if (b % 2 == 1)
+ x = (x + y) % mod;
+
+ y = (y * 2) % mod;
+ b /= 2;
+ }
+
+ return x % mod;
+}
+
+/*
+* modular exponentiation
+*/
+ll modulo(ll base, ll exponent, ll mod)
+{
+ ll x = 1;
+ ll y = base;
+
+ while (exponent > 0)
+ {
+ if (exponent % 2 == 1)
+ x = (x * y) % mod;
+
+ y = (y * y) % mod;
+ exponent = exponent / 2;
+ }
+
+ return x % mod;
+}
+
+/*
+* Miller-Rabin primality test, iteration signifies the accuracy
+*/
+bool EulerUtility::isPrime(ll p, int iteration)
+{
+ if ((p < 2) || (p != 2 && p % 2 == 0))
+ return false;
+
+ ll s = p - 1;
+
+ while (s % 2 == 0)
+ s /= 2;
+
+ for (int i = 0; i < iteration; i++)
+ {
+ ll a = rand() % (p - 1) + 1, temp = s;
+ ll mod = modulo(a, temp, p);
+
+ while (temp != p - 1 && mod != 1 && mod != p - 1)
+ {
+ mod = mulmod(mod, mod, p);
+ temp *= 2;
+ }
+
+ if (mod != p - 1 && temp % 2 == 0)
+ return false;
+ }
+
+ return true;
+}
+
+bool EulerUtility::isTriangle(int n)
+{
+ return std::floor(sqrt(2 * n + 0.25) - 0.5) == sqrt(2 * n + 0.25) - 0.5;
+}
+
+bool EulerUtility::isPentagonal(llui n)
+{
+ return isPerfectSquare((24 * n) + 1) && ((llui)sqrt((24 * n) + 1) + 1) % 6 == 0;
+}
+
+std::vector<std::string> EulerUtility::openWordFile(std::string filename)
+{
+ std::ifstream file;
+ std::vector<std::string> names;
+ std::string name;
+ file.open(filename);
+
+ while(getline(file, name, ','))
+ names.push_back(name.substr(1, name.size() - 2));
+
+ return names;
+}
+
+BigInteger EulerUtility::power(BigInteger i, int p)
+{
+ if (p <= 0)
+ return 1;
+
+ return i * power(i, p - 1);
+}
+
+int EulerUtility::digitalRoot(int n)
+{
+ std::vector<int> digits = intToDigits(n);
+ int digitSum = std::accumulate(digits.begin(), digits.end(), 0);
+
+ if (digitSum > 9)
+ return digitalRoot(digitSum);
+
+ return digitSum;
+}
+
+int EulerUtility::digitalRoot(BigInteger n)
+{
+ std::vector<int> digits = BigIntToDigits(n);
+ int digitSum = std::accumulate(digits.begin(), digits.end(), 0);
+
+ if (digitSum > 9)
+ return digitalRoot(digitSum);
+
+ return digitSum;
+}
+
+std::vector<int> EulerUtility::intersect(std::vector<int>& a, std::vector<int>& b)
+{
+ std::vector<int> v(a.size() + b.size());
+ v.resize(std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), v.begin()) - v.begin());
+ return v;
+}
+
+std::vector<int> EulerUtility::getFigurates(int sides, int floor, int ceiling)
+{
+ std::vector<int> figurates;
+
+ if (sides < 3)
+ return figurates;
+
+ for (int i = 0; i < ceiling; ++i)
+ {
+ int figurate = (sides & 1) ? (i * ((i * (sides - 2)) + 4 - sides)) / 2 : i * ((((sides / 2) - 1) * i) - ((sides / 2) - 2));
+
+ if (figurate >= floor && figurate < ceiling)
+ figurates.push_back(figurate);
+
+ if (figurate > ceiling)
+ return figurates;
+ }
+
+ return figurates;
+}
+
+llui EulerUtility::gcd(llui a, llui b)
+{
+ while (b != 0)
+ {
+ llui t = b;
+ b = a % b;
+ a = t;
+ }
+ return a;
+}
+
+llui EulerUtility::phi(int n, std::vector<int> &primes, std::vector<int> &primesIndexed)
+{
+ // Base case
+ if (n < 2)
+ return 0;
+
+ // Lehmer's conjecture
+ if (primesIndexed[n] != -1)
+ return n - 1;
+
+ // Even number?
+ if (n & 1 == 0)
+ {
+ int m = n >> 1;
+ return !(m & 1) ? EulerUtility::phi(m, primes, primesIndexed) << 1 : EulerUtility::phi(m, primes, primesIndexed);
+ }
+
+ // For all primes ...
+ for (std::vector<int>::iterator p = primes.begin(); p != primes.end() && *p <= n; ++p)
+ {
+ int m = *p;
+ if (n % m) continue;
+
+ // phi is multiplicative
+ int o = n / m;
+ int d = EulerUtility::gcd(m, o);
+ return (d == 1) ? EulerUtility::phi(m, primes, primesIndexed) * EulerUtility::phi(o, primes, primesIndexed) : EulerUtility::phi(m, primes, primesIndexed) * EulerUtility::phi(o, primes, primesIndexed) * d / EulerUtility::phi(d, primes, primesIndexed);
+ }
+}+
\ No newline at end of file
diff --git a/EulerUtility.h b/EulerUtility.h
@@ -0,0 +1,44 @@
+#include <string>
+#include <vector>
+
+#include "BigIntegerLibrary.hh"
+
+typedef long long unsigned int llui;
+typedef long long int ll;
+
+class EulerUtility
+{
+public:
+ static int multiply(int x, int y);
+ static std::vector<int> getPrimesUnderCeiling(int ceiling);
+ static std::vector<int> getPrimesUnderCeilingIndexed(int ceiling);
+ static std::vector<int> tokenizer(std::string s, char delim);
+ static std::vector<std::string> strTokenizer(std::string s, char delim);
+ static int sumOfDivisors(int n);
+ static std::vector<int> factorialDigits(int n);
+ static std::vector<int> powerDigits(int n, int p);
+ static int factorial(int n);
+ static BigInteger bigFactorial(BigInteger n);
+ static BigInteger choose(int n, int k);
+ static bool isPerfectSquare(llui n);
+ static bool isPerfectCube(llui n);
+ static std::vector<int> intToDigits(int n);
+ static std::vector<int> lluiToDigits(llui n);
+ static std::vector<int> BigIntToDigits(BigInteger n);
+ static int digitsToInteger(std::vector<int> digits);
+ static llui digitsTollui(std::string s);
+ static bool hasUniqueDigits(int n, bool allowZero);
+ static bool isPrime(ll n, int iteration);
+ static bool isPrime(BigInteger& n);
+ static bool isTriangle(int n);
+ static bool isPentagonal(llui n);
+ static std::vector<std::string> openWordFile(std::string filename);
+ static BigInteger power(BigInteger i, int p);
+ static int digitalRoot(int n);
+ static int digitalRoot(BigInteger n);
+ static std::vector<int> intersect(std::vector<int>& a, std::vector<int>& b);
+ static std::vector<int> getFigurates(int sides, int floor, int ceiling);
+ static llui gcd(llui a, llui b);
+ static llui binary_gcd(llui a, llui b);
+ static llui phi(int n, std::vector<int> &primes, std::vector<int> &primesIndexed);
+};+
\ No newline at end of file
diff --git a/Euler_1.cpp b/Euler_1.cpp
@@ -0,0 +1,13 @@
+#include "Euler.h"
+
+int Euler::SumOfMultiplesOf3And5Ceiling1000()
+{
+ int sumOfMultiples = 0;
+
+ for (int i = 0; i < 1000; ++i) {
+ if ((i % 3 == 0) || (i % 5 == 0))
+ sumOfMultiples += i;
+ }
+
+ return sumOfMultiples;
+} +
\ No newline at end of file
diff --git a/Euler_10.cpp b/Euler_10.cpp
@@ -0,0 +1,24 @@
+#include "Euler.h"
+
+llui Euler::SumOfPrimesUnder2m()
+{
+ int noOfPrimes = 0;
+
+ bool is_prime;
+
+ llui count = 2; //includes 2 & 3
+
+ for(int i = 3; i < 2000000; i += 2)
+ {
+ is_prime = true;
+
+ for(int j = 3; j * j <= i && is_prime; j += 2)
+ if(i % j == 0) is_prime = false;
+
+ if(is_prime) {
+ count += i;
+ }
+ }
+
+ return count;
+}+
\ No newline at end of file
diff --git a/Euler_11.cpp b/Euler_11.cpp
@@ -0,0 +1,77 @@
+#include <fstream>
+
+#include "Euler.h"
+
+void SumDigits(std::vector<int> &digits, int &greatestProduct)
+{
+ int temp = digits[0];
+
+ for(unsigned int j = 1; j < digits.size(); ++j)
+ temp *= digits[j];
+
+ if (temp > greatestProduct)
+ greatestProduct = temp;
+}
+
+int Euler::LargestProductInGrid()
+{
+ std::ifstream fin;
+ fin.open("E:\\Euler Resources\\Euler 11.txt");
+ std::string grid;
+ std::getline(fin, grid);
+ fin.close();
+
+ std::vector<int> numGrid = EulerUtility::tokenizer(grid, ' ');
+
+ int greatestProduct = 0;
+
+ for (int i = 0; i < 20; ++i) {
+ for (int j = 0; j <= 20 - 4; ++j)
+ {
+ std::vector<int> digits;
+
+ for (int k = 0; k < 4; ++k)
+ digits.push_back(numGrid[i * 20 + j + k]);
+
+ SumDigits(digits, greatestProduct);
+ }
+ }
+
+ for (int i = 0; i <= 20 - 4; ++i){
+ for (int j = 0; j < 20; ++j)
+ {
+ std::vector<int> digits;
+
+ for (int k = 0; k < 4; ++k)
+ digits.push_back(numGrid[i + j * 20 + k]);
+
+ SumDigits(digits, greatestProduct);
+ }
+ }
+
+ for (int i = 0; i < 20 - 4; ++i) {
+ for (int j = 0; j <= 20 - 4; ++j)
+ {
+ std::vector<int> digits;
+
+ for (int k = 0; k < 4; ++k)
+ digits.push_back(numGrid[(i + k) * 20 + j + k]);
+
+ SumDigits(digits, greatestProduct);
+ }
+ }
+
+ for (int i = 0; i < 20 - 4; ++i) {
+ for (int j = 19; j >= 3; --j)
+ {
+ std::vector<int> digits;
+
+ for (int k = 0; k < 4; ++k)
+ digits.push_back(numGrid[(i + k) * 20 + j - k]);
+
+ SumDigits(digits, greatestProduct);
+ }
+ }
+
+ return greatestProduct;
+}+
\ No newline at end of file
diff --git a/Euler_12.cpp b/Euler_12.cpp
@@ -0,0 +1,54 @@
+#include "Euler.h"
+
+int getNumberOfDivisorsFromPrimeFactors(llui target, std::vector<int> &primes)
+{
+ std::vector<int> noOfEachPrimeFactor;
+
+ int divisors = 1;
+ int i = 0;
+
+ bool first = true;
+
+ while (target != 1)
+ {
+ if (target % primes[i] == 0)
+ {
+ target /= primes[i];
+
+ if (first)
+ {
+ first = false;
+ noOfEachPrimeFactor.push_back(1);
+ }
+ else
+ noOfEachPrimeFactor[noOfEachPrimeFactor.size() - 1] += 1;
+ }
+ else
+ {
+ first = true;
+ ++i;
+ }
+ }
+
+ if (!noOfEachPrimeFactor.empty())
+ {
+ for (unsigned i = 0; i < noOfEachPrimeFactor.size(); ++i)
+ {
+ divisors *= (noOfEachPrimeFactor[i] + 1);
+ }
+ }
+
+ return divisors;
+}
+
+llui Euler::TriangleNoWithGreaterThan500Divisors()
+{
+ llui currentTriangle = 1;
+
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(100000);
+
+ for (int i = 2; getNumberOfDivisorsFromPrimeFactors(currentTriangle, primes) <= 500; ++i)
+ currentTriangle += i;
+
+ return currentTriangle;
+}+
\ No newline at end of file
diff --git a/Euler_13.cpp b/Euler_13.cpp
@@ -0,0 +1,88 @@
+#include <fstream>
+#include <sstream>
+
+#include "Euler.h"
+
+std::vector<int> getIndividualDigits(int number)
+{
+ std::vector<int> digits;
+
+ std::string s = std::to_string(number);
+
+ for (int i = s.length() - 1; i >= 0 ; --i)
+ digits.push_back(atoi(s.substr(i, 1).c_str()));
+
+ return digits;
+}
+
+std::string getSum(std::vector<int> digits)
+{
+ std::string s;
+
+ for (int i = digits.size() - 1; i >= 0; --i)
+ {
+ s += std::to_string(digits[i]);
+ }
+
+ return s;
+}
+
+std::string Euler::LargeSum() {
+ std::ifstream fin;
+ std::vector<std::string> numbers;
+
+ fin.open("E:\\Euler Resources\\Euler 13.txt");
+
+ std::string temp;
+ while(std::getline(fin, temp))
+ numbers.push_back(temp);
+
+ fin.close();
+
+ std::vector<int> sumDigits;
+
+ for (int i = numbers[0].size() - 1; i >= 0; --i)
+ {
+ int exp = 0;
+
+ for (unsigned j = 0; j < numbers.size(); ++j)
+ {
+ std::stringstream strValue;
+ strValue << numbers[j].at(i);
+
+ unsigned int sumDigit;
+ strValue >> sumDigit;
+
+ exp += sumDigit;
+ }
+
+ sumDigits.push_back(exp);
+ }
+
+ std::vector<int> digits = getIndividualDigits(sumDigits[0]);
+
+ for (unsigned i = 1; i < sumDigits.size(); ++i)
+ {
+ std::vector<int> temp = getIndividualDigits(sumDigits[i]);
+
+ digits[i] += temp[0];
+ digits[i + 1] += temp[1];
+ digits.push_back(temp[2]);
+ }
+
+ for (unsigned i = 0; i < digits.size(); ++i)
+ {
+ if (digits[i] >= 20)
+ {
+ digits[i] -= 20;
+ digits[i + 1] += 2;
+ }
+ else if (digits[i] >= 10)
+ {
+ digits[i] -= 10;
+ digits[i + 1] += 1;
+ }
+ }
+
+ return getSum(digits).substr(0, 10);
+}+
\ No newline at end of file
diff --git a/Euler_14.cpp b/Euler_14.cpp
@@ -0,0 +1,41 @@
+#include "Euler.h"
+
+int lengthOfChain(llui number)
+{
+ int length = 0;
+
+ while (number > 1)
+ {
+ if (number % 2 == 0)
+ {
+ number /= 2;
+ }
+ else
+ {
+ number = (number * 3) + 1;
+ }
+
+ length += 1;
+ }
+
+ return length;
+}
+
+llui Euler::CollatzConjecture()
+{
+ int longestChain = 0;
+ int idx = 0;
+
+ for (int i = 0; i < 1000000; ++i)
+ {
+ int length = lengthOfChain(i);
+
+ if (length > longestChain)
+ {
+ longestChain = length;
+ idx = i;
+ }
+ }
+
+ return idx;
+}+
\ No newline at end of file
diff --git a/Euler_15.cpp b/Euler_15.cpp
@@ -0,0 +1,6 @@
+#include "Euler.h"
+
+BigInteger Euler::LatticePaths()
+{
+ return EulerUtility::choose(40,20);
+}+
\ No newline at end of file
diff --git a/Euler_16.cpp b/Euler_16.cpp
@@ -0,0 +1,35 @@
+#include <numeric>
+
+#include "Euler.h"
+
+int Euler::DigitSum()
+{
+ std::vector<int> digits;
+
+ digits.push_back(2);
+
+ for (int i = 1; i < 1000; ++i)
+ {
+ for (unsigned j = 0; j < digits.size(); ++j)
+ digits[j] *=2;
+
+ for (unsigned j = 0; j < digits.size(); ++j)
+ {
+ if (digits[j] >= 10)
+ {
+ digits[j] = digits[j] % 10;
+
+ if (j == digits.size() - 1)
+ {
+ digits.push_back(1);
+ }
+ else
+ {
+ digits[j + 1] += 1;
+ }
+ }
+ }
+ }
+
+ return std::accumulate(digits.begin(), digits.end(), 0);
+}+
\ No newline at end of file
diff --git a/Euler_17.cpp b/Euler_17.cpp
@@ -0,0 +1,37 @@
+#include "Euler.h"
+
+int digit(std::string digits[], std::string teens[], int j, int k)
+{
+ return (k > 0) ? ((j == 1) ? teens[k - 1].length() : digits[k - 1].length()) : 0;
+}
+
+int tenz(int ten, int j, int k)
+{
+ return (j == 1) ? ((k == 0) ? ten : 0) : ten;
+}
+
+int and(int count)
+{
+ return ((count >= 100) && (count % 100 != 0)) ? std::string("and").length() : 0;
+}
+
+int x_hundred(std::string digits[], int i)
+{
+ return (i > 0) ? digits[i - 1].length() + std::string("hundred").length() : 0; //x hundred
+}
+
+int Euler::LetterCounter()
+{
+ std::string digits[] = { "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
+ std::string teens[] = { "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};
+ std::string tens[] = { "", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"};
+
+ int sum = digits[0].length() + std::string("thousand").length(); //one thousand
+
+ for (int i = 0; i < 10; ++i)
+ for (int j = 0; j < 10; ++j)
+ for (int k = 0; k < 10; ++k)
+ sum += x_hundred(digits, i) + and(i * 100 + j * 10 + k) + tenz(tens[j].length(), j, k) + digit(digits, teens, j, k);
+
+ return sum;
+}+
\ No newline at end of file
diff --git a/Euler_18.cpp b/Euler_18.cpp
@@ -0,0 +1,28 @@
+#include <fstream>
+
+#include "Euler.h"
+
+int Euler::MaximumPathSum()
+{
+ std::ifstream fin;
+ std::vector<std::string> str_rows;
+
+ fin.open("E:\\Euler Resources\\Euler 67.txt");
+
+ std::string temp;
+ while(std::getline(fin, temp))
+ str_rows.push_back(temp);
+
+ fin.close();
+
+ std::vector<std::vector<int>> rows;
+
+ for (std::string s :str_rows)
+ rows.push_back(EulerUtility::tokenizer(s, ' '));
+
+ for (int i = rows.size() - 2; i >= 0; --i)
+ for (unsigned j = 0; j < rows[i].size(); ++j)
+ rows[i][j] += (rows[i + 1][j] > rows[i + 1][j + 1]) ? rows[i + 1][j] : rows[i + 1][j + 1];
+
+ return rows[0][0];
+}+
\ No newline at end of file
diff --git a/Euler_19.cpp b/Euler_19.cpp
@@ -0,0 +1,30 @@
+#include "Euler.h"
+
+int daysInFebruary(int year)
+{
+ return (year % 4 == 0) ? ((year % 100 == 0) ? ((year % 400 == 0) ? 29 : 28) : 29) : 28;
+}
+
+int Euler::SundayCount()
+{
+ int weekday = 1;
+ int sundays = 0;
+
+ for (int year = 1900; year <= 2000; ++year)
+ {
+ int months[] = {31, daysInFebruary(year), 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
+
+ for (int month : months)
+ {
+ for (int day = 0; day < month; ++day)
+ {
+ if ((weekday == 0) && (day == 0) && (year > 1900))
+ ++sundays;
+
+ ++weekday %= 7;
+ }
+ }
+ }
+
+ return sundays;
+}+
\ No newline at end of file
diff --git a/Euler_2.cpp b/Euler_2.cpp
@@ -0,0 +1,18 @@
+#include "Euler.h"
+
+int Euler::SumOfEvenFibonacciNumbersCeiling4m()
+{
+ int sumOfEvenFibNumbers = 0;
+
+ for (int i = 1, j = 2; j < 4000000;)
+ {
+ if (j % 2 == 0)
+ sumOfEvenFibNumbers += j;
+
+ int temp = j;
+ j += i;
+ i = temp;
+ }
+
+ return sumOfEvenFibNumbers;
+}+
\ No newline at end of file
diff --git a/Euler_20.cpp b/Euler_20.cpp
@@ -0,0 +1,10 @@
+#include <numeric>
+
+#include "Euler.h"
+
+llui Euler::FactorialDigitSum()
+{
+ std::vector<int> digits = EulerUtility::factorialDigits(100);
+
+ return std::accumulate(digits.begin(), digits.end(), 0);
+}+
\ No newline at end of file
diff --git a/Euler_21.cpp b/Euler_21.cpp
@@ -0,0 +1,17 @@
+#include "Euler.h"
+
+int Euler::AmicableNumbers()
+{
+ std::vector<unsigned> sumDivisors(10001, 0);
+
+ for(int i = 2; i < 10000; ++i)
+ sumDivisors[i] = EulerUtility::sumOfDivisors(i) - i;
+
+ int sum = 0;
+
+ for (unsigned i = 0; i < sumDivisors.size(); ++i)
+ if (sumDivisors[i] < sumDivisors.size() && sumDivisors[sumDivisors[i]] == i && sumDivisors[i] != i)
+ sum += i;
+
+ return sum;
+}+
\ No newline at end of file
diff --git a/Euler_22.cpp b/Euler_22.cpp
@@ -0,0 +1,24 @@
+#include <algorithm>
+
+#include "Euler.h"
+
+llui Euler::NameScores()
+{
+ std::vector<std::string> names = EulerUtility::openWordFile("E:\\Euler Resources\\Euler 22.txt");
+ std::sort(names.begin(), names.end());
+
+ llui sum = 0;
+ int count = 0;
+
+ for (std::string name : names)
+ {
+ int namesum = 0;
+
+ for (char n : name)
+ namesum += n - 64;
+
+ sum += namesum * ++count;
+ }
+
+ return sum;
+}+
\ No newline at end of file
diff --git a/Euler_23.cpp b/Euler_23.cpp
@@ -0,0 +1,23 @@
+#include <numeric>
+#include "Euler.h"
+
+int Euler::NonAbundantSums()
+{
+ int ceiling = 28123;
+ std::vector<int> abundantNumbers;
+ std::vector<int> nonAbundantSums(ceiling * 2 + 1, 0);
+
+ for (int i = 1; i <= ceiling; ++i)
+ {
+ if(EulerUtility::sumOfDivisors(i) > 2 * i)
+ abundantNumbers.push_back(i);
+
+ nonAbundantSums[i - 1] = i;
+ }
+
+ for (int abnum : abundantNumbers)
+ for (int abnum2 : abundantNumbers)
+ nonAbundantSums[abnum + abnum2 - 1] = 0;
+
+ return std::accumulate(nonAbundantSums.begin(), nonAbundantSums.end(), 0);
+}+
\ No newline at end of file
diff --git a/Euler_24.cpp b/Euler_24.cpp
@@ -0,0 +1,12 @@
+#include <algorithm>
+#include "Euler.h"
+
+std::string Euler::LexicographicPermutations()
+{
+ std::string lexicon = "0123456789";
+
+ for (int i = 1; i < 1e6; ++i)
+ std::next_permutation(lexicon.begin(), lexicon.end());
+
+ return lexicon;
+}+
\ No newline at end of file
diff --git a/Euler_25.cpp b/Euler_25.cpp
@@ -0,0 +1,37 @@
+#include "Euler.h"
+
+int Euler::ThousandDigitFibonacciNumber()
+{
+ std::vector<int> fib1(1, 1);
+ std::vector<int> fib2(1, 1);
+
+ int count = 2;
+
+ while (fib1.size() < 1e3)
+ {
+ for (unsigned i = 0; i < fib1.size(); ++i)
+ fib1[i] += fib2[i];
+
+ for (unsigned i = 0; i < fib1.size(); ++i)
+ {
+ if (fib1[i] >= 10)
+ {
+ fib1[i] = fib1[i] % 10;
+
+ if (i == fib1.size() - 1)
+ {
+ fib1.push_back(1);
+ fib2.push_back(0);
+ }
+ else
+ fib1[i + 1] += 1;
+ }
+ }
+
+ fib1.swap(fib2);
+
+ ++count;
+ }
+
+ return count;
+}+
\ No newline at end of file
diff --git a/Euler_26.cpp b/Euler_26.cpp
@@ -0,0 +1,27 @@
+#include "Euler.h"
+
+int Euler::ReciprocalCycles()
+{
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(1000);
+
+ for (int j = primes.size() - 1; j >= 0; --j)
+ {
+ bool highestReciprocalCycle = true;
+
+ for (int i = 1; i < primes[j]; ++i)
+ {
+ BigInteger bi = EulerUtility::power(10, i);
+
+ if (((bi % primes[j] == 1) && (i != (primes[j] - 1))) || ((bi % primes[j] != 1) && (i == (primes[j] - 1))))
+ {
+ highestReciprocalCycle = false;
+ break;
+ }
+ }
+
+ if (highestReciprocalCycle)
+ return primes[j];
+ }
+
+ return 0;
+}+
\ No newline at end of file
diff --git a/Euler_27.cpp b/Euler_27.cpp
@@ -0,0 +1,10 @@
+#include "Euler.h"
+
+int Euler::QuadraticPrimes()
+{
+ for (int i = 40; i >= 0; --i)
+ if (pow(i, 2) - i + 41 < 1000)
+ return ((int)pow(i, 2) - i + 41) * ((i * -2) + 1);
+
+ return 0;
+}+
\ No newline at end of file
diff --git a/Euler_28.cpp b/Euler_28.cpp
@@ -0,0 +1,11 @@
+#include "Euler.h"
+
+long Euler::SpiralDiagonals()
+{
+ long sum = 1;
+
+ for (int i = 3; i <= 1001; i += 2)
+ sum += ((int)(pow(i, 2)) * 4) - (i * 6) + 6;
+
+ return sum;
+}+
\ No newline at end of file
diff --git a/Euler_29.cpp b/Euler_29.cpp
@@ -0,0 +1,77 @@
+#include <unordered_set>
+
+#include "Euler.h"
+
+std::vector<int> getPowers(int ceiling)
+{
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(ceiling);
+ std::vector<int> powers(ceiling + 1, 0);
+
+ for (int j = 0; j <= ceiling; ++j)
+ {
+ std::vector<int> p_factors;
+ int target = j;
+ int i = 0;
+
+ while (target > 1)
+ {
+ if (target % primes[i] == 0)
+ {
+ target /= primes[i];
+ p_factors.push_back(primes[i]);
+ }
+ else
+ ++i;
+ }
+
+ if (p_factors.size() > 1)
+ {
+ std::unordered_set<int> unique_p_factors;
+
+ for (int p : p_factors)
+ unique_p_factors.insert(p);
+
+ if (unique_p_factors.size() == 1)
+ powers[j] = p_factors.size();
+ else if (EulerUtility::isPerfectSquare(j))
+ powers[j] = 2;
+ }
+ }
+
+ return powers;
+}
+
+int Euler::DistinctPowers()
+{
+ int ceiling = 100;
+ std::vector<int> powers = getPowers(ceiling);
+
+ int sum = 0;
+
+ for (int i = 2; i <= ceiling; ++i)
+ {
+ if (powers[i] == 0)
+ sum += ceiling - 1;
+ else
+ {
+ for (int j = 2; j <= ceiling; ++j)
+ {
+ bool unique = true;
+
+ for (int k = 1; k < powers[i]; ++k)
+ {
+ if (((powers[i] * j) % k == 0) && ((powers[i] * j) / k <= ceiling))
+ {
+ unique = false;
+ break;
+ }
+ }
+
+ if (unique)
+ ++sum;
+ }
+ }
+ }
+
+ return sum;
+}+
\ No newline at end of file
diff --git a/Euler_3.cpp b/Euler_3.cpp
@@ -0,0 +1,52 @@
+#include <algorithm>
+
+#include "Euler.h"
+
+llui lpf(llui x)
+{
+ bool is_prime;
+
+ llui count = 1;
+ llui my_prime = 2; //set to first prime
+
+ for(llui i = 3; count < x; i += 2)
+ {
+ is_prime = true;
+
+ for(llui j = 3; j * j <= i && is_prime; j += 2)
+ if(i % j == 0) is_prime = false;
+
+ if(is_prime) {
+ if (x % i == 0)
+ return i;
+
+ ++count;
+ my_prime = i;
+ }
+ }
+
+ return 0; //prime factor does not exist (1 does not count as prime)
+}
+
+llui Euler::LargestPrimeFactor()
+{
+ std::vector<llui> primes;
+
+ primes.push_back(1);
+
+ llui x = 600851475143;
+
+ while (x > 1)
+ {
+ x /= primes.back();
+
+ llui y = lpf(x);
+
+ if (y != 0)
+ primes.push_back(y);
+ }
+
+ std::sort (primes.begin(), primes.end());
+
+ return primes.back();
+}+
\ No newline at end of file
diff --git a/Euler_30.cpp b/Euler_30.cpp
@@ -0,0 +1,21 @@
+#include "Euler.h"
+
+long Euler::DigitFifthPowers()
+{
+ long sum = 0;
+
+ for (int j = 0 ; j < 500000; ++j)
+ {
+ long currentPowerTotal = 0;
+
+ std::string current = std::to_string(j);
+
+ for (unsigned i = 0; i < current.length(); i++)
+ currentPowerTotal += (int)pow(current.at(i) - 48, 5);
+
+ if (j == currentPowerTotal)
+ sum += currentPowerTotal;
+ }
+
+ return sum - 1;
+}
diff --git a/Euler_31.cpp b/Euler_31.cpp
@@ -0,0 +1,43 @@
+#include "Euler.h"
+
+int coins[8] = {200, 100, 50, 20, 10, 5, 2, 1};
+
+int coinSumRecurse(int money, int maxcoin)
+{
+ int sum = 0;
+
+ if(maxcoin == 7)
+ return 1;
+
+ for(int i = maxcoin; i < 8; i++)
+ {
+ if (money - coins[i] == 0)
+ ++sum;
+ if (money - coins[i] > 0)
+ sum += coinSumRecurse(money - coins[i], i);
+ }
+
+ return sum;
+}
+
+int Euler::CoinSums()
+{
+ return coinSumRecurse(200, 0);
+}
+
+//int Euler::CoinSums() //original solution
+//{
+// int sum = 0;
+//
+// for (int a = 0; a <= 200; ++a)
+// for (int b = 0; b <= 100; ++b)
+// for (int c = 0; c <= 40; ++c)
+// for (int d = 0; d <= 20; ++d)
+// for (int e = 0; e <= 10; ++e)
+// for (int f = 0; f <= 5; ++f)
+// for (int g = 0; g <= 2; ++g)
+// if (a + b * 2 + c * 5 + d * 10 + e * 20 + f * 50 + g * 100 == 200)
+// ++sum;
+//
+// return sum + 1;
+//}+
\ No newline at end of file
diff --git a/Euler_32.cpp b/Euler_32.cpp
@@ -0,0 +1,44 @@
+#include <algorithm>
+#include <numeric>
+#include <unordered_set>
+
+#include "Euler.h"
+
+int getSubInt(unsigned it1, unsigned it2, std::vector<int> &sub_lex)
+{
+ int integer = 0;
+
+ for (unsigned i = it1; i < it2; ++i)
+ {
+ integer *= 10;
+ integer += sub_lex[i];
+ }
+
+ return integer;
+}
+
+int Euler::PanDigitalProducts()
+{
+ int lexicon[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
+ std::vector<int> lex(std::begin(lexicon), std::end(lexicon));
+
+ std::unordered_set<int> products;
+
+ for (int i = 0; i < EulerUtility::factorial(9); ++i)
+ {
+ for (unsigned it1 = 1; it1 < 5; ++ it1)
+ for (unsigned it2 = it1 + 1; it2 < lex.size() - 3; ++it2)
+ {
+ int multiplicand = getSubInt(0, it1, lex);
+ int multiplier = getSubInt(it1, it2, lex);
+ int product = getSubInt(it2, lex.size(), lex);
+
+ if (multiplicand * multiplier == product)
+ products.insert(product);
+ }
+
+ std::next_permutation(lex.begin(), lex.end());
+ }
+
+ return std::accumulate(products.begin(), products.end(), 0);
+}+
\ No newline at end of file
diff --git a/Euler_33.cpp b/Euler_33.cpp
@@ -0,0 +1,67 @@
+#include "Euler.h"
+
+std::vector<int> lowestTerm(int n, int d, std::vector<int> &p)
+{
+ for (unsigned i = 0; i < p.size(); )
+ {
+ if ((n % p[i] == 0) && (d % p[i] == 0))
+ {
+ n /= p[i];
+ d /= p[i];
+
+ i = 0;
+ }
+ else
+ ++i;
+ }
+
+ std::vector<int> l;
+
+ l.push_back(n);
+ l.push_back(d);
+
+ return l;
+}
+
+void addDigitCancellingFraction(std::vector<int> &denom, std::vector<int> &numer, std::vector<int> &primes, std::vector<std::vector<int>> &dc_fractions, int n, int d, bool first)
+{
+ if (denom[first] == numer[!first])
+ {
+ std::vector<int> lowest = lowestTerm(n, d, primes);
+ std::vector<int> lowestCancelled = lowestTerm(numer[first], denom[!first], primes);
+ if ((lowestCancelled[0] == lowest[0]) && (lowestCancelled[1] == lowest[1]))
+ dc_fractions.push_back(lowest);
+ }
+}
+
+int Euler::DigitCancellingFractionsDenominator()
+{
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(52);
+
+ std::vector<std::vector<int>> dc_fractions;
+
+ for (int denominator = 10; denominator < 100; ++ denominator)
+ {
+ std::vector<int> denom = EulerUtility::intToDigits(denominator);
+
+ for (int numerator = 10; numerator < denominator; ++numerator)
+ {
+ std::vector<int> numer = EulerUtility::intToDigits(numerator);
+
+ addDigitCancellingFraction(denom, numer, primes, dc_fractions, numerator, denominator, true);
+ addDigitCancellingFraction(denom, numer, primes, dc_fractions, numerator, denominator, false);
+ }
+ }
+
+ int n = 1, d = 1;
+
+ for (std::vector<int> fraction : dc_fractions)
+ {
+ n *= fraction[0];
+ d *= fraction[1];
+ }
+
+ std::vector<int> lowestProduct = lowestTerm(n, d, primes);
+
+ return lowestProduct[1];
+}+
\ No newline at end of file
diff --git a/Euler_34.cpp b/Euler_34.cpp
@@ -0,0 +1,22 @@
+#include "Euler.h"
+
+llui Euler::DigitFactorials()
+{
+ int factorials[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
+ llui sum = 0;
+
+ for (unsigned i = 0 ; i < 50000; ++i)
+ {
+ long currentTotal = 0;
+
+ std::vector<int> digits = EulerUtility::intToDigits(i);
+
+ for (int digit : digits)
+ currentTotal += factorials[digit];
+
+ if (i == currentTotal)
+ sum += currentTotal;
+ }
+
+ return sum - 3;
+}+
\ No newline at end of file
diff --git a/Euler_35.cpp b/Euler_35.cpp
@@ -0,0 +1,42 @@
+#include "Euler.h"
+
+int Euler::NoOfCircularPrimes()
+{
+ int total = 2; //this algorithm misses out 2 and 5
+
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeilingIndexed(1000000);
+
+ for (int prime : primes)
+ {
+ if (prime != -1)
+ {
+ bool potentialCircularPrime = true;
+
+ std::vector<int> digits = EulerUtility::intToDigits(prime);
+
+ for (int digit : digits)
+ if ((digit == 0) || (digit == 5) || (digit % 2 == 0))
+ {
+ potentialCircularPrime = false;
+ break;
+ }
+
+ if (potentialCircularPrime)
+ for (int j = 0; j <= log10(prime); ++j)
+ {
+ if (primes[EulerUtility::digitsToInteger(digits)] == -1)
+ {
+ potentialCircularPrime = false;
+ break;
+ }
+
+ std::rotate(digits.begin(), digits.begin() + 1, digits.end());
+ }
+
+ if (potentialCircularPrime)
+ ++total;
+ }
+ }
+
+ return total;
+}+
\ No newline at end of file
diff --git a/Euler_36.cpp b/Euler_36.cpp
@@ -0,0 +1,40 @@
+#include <bitset>
+#include <sstream>
+
+#include "Euler.h"
+
+bool isPalindrome(std::string &n)
+{
+ for (unsigned int i = 0; i < n.length(); ++i)
+ if (n.at(i) != n.at(n.length() - 1 - i))
+ return false;
+
+ return true;
+}
+
+bool isPalindromeInTwoBases(int i)
+{
+ std::ostringstream oss;
+ oss << i;
+
+ std::string b10 = oss.str();
+
+ if (!isPalindrome(b10))
+ return false;
+
+ std::string b2 = std::bitset<32>(i).to_string();
+ b2 = b2.substr(b2.find('1'));
+
+ return isPalindrome(b2);
+}
+
+llui Euler::DoubleBasedPalindromes()
+{
+ llui sum = 0;
+
+ for (int i = 1; i < 1e6; ++i)
+ if (isPalindromeInTwoBases(i))
+ sum += i;
+
+ return sum;
+}+
\ No newline at end of file
diff --git a/Euler_37.cpp b/Euler_37.cpp
@@ -0,0 +1,27 @@
+#include "Euler.h"
+
+bool isTruncPrime(std::string &p, std::vector<int> &primes, bool left)
+{
+ bool isPrime = primes[atoi(p.c_str())] != -1;
+
+ if (p.size() == 1)
+ return isPrime;
+
+ return (isPrime) ? isTruncPrime(p.substr(left, p.size() - 1), primes, left) : false;
+}
+
+llui Euler::TruncatablePrimes()
+{
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeilingIndexed(1000000);
+ llui sum = -17; //offset, since this algo does not exclude 2, 3, 5 and 7 of which the sum is 17
+
+ for (int prime : primes)
+ if (prime != -1)
+ {
+ std::string p = std::to_string(prime);
+ if (isTruncPrime(p, primes, true) && isTruncPrime(p, primes, false))
+ sum += prime;
+ }
+
+ return sum;
+}+
\ No newline at end of file
diff --git a/Euler_38.cpp b/Euler_38.cpp
@@ -0,0 +1,22 @@
+#include "Euler.h"
+
+int Euler::PanDigitalMultiples()
+{
+ int greatestPanDigitalMultiple = 918273645;
+
+ for (int i = 9182; i < 9876; ++i) //9182 is the first 4 digits of the above no, 9876 is the int with unique digits < 10000
+ {
+ if (EulerUtility::hasUniqueDigits(i, false))
+ {
+ if (EulerUtility::hasUniqueDigits(i * 2, false))
+ {
+ int potentialPanDigital = atoi((std::to_string(i) + std::to_string(i * 2)).c_str());
+
+ if ((EulerUtility::hasUniqueDigits(potentialPanDigital, false)) && (potentialPanDigital > greatestPanDigitalMultiple))
+ greatestPanDigitalMultiple = potentialPanDigital;
+ }
+ }
+ }
+
+ return greatestPanDigitalMultiple;
+}+
\ No newline at end of file
diff --git a/Euler_39.cpp b/Euler_39.cpp
@@ -0,0 +1,26 @@
+#include "Euler.h"
+
+int Euler::MaximumRightAngledTriangles()
+{
+ int perimeter = 120;
+ int maximum = 3;
+
+ for (int p = 121; p <= 1000; ++p)
+ {
+ int solutions = 0;
+
+ for (int i = 1; i < p / 2 + 1; ++i)
+ for (int j = 1; j <= i; ++ j)
+ if (EulerUtility::isPerfectSquare(pow(i, 2) + pow(j, 2)))
+ if ((i + j + sqrt(pow(i, 2) + pow(j, 2))) == p)
+ ++solutions;
+
+ if (solutions > maximum)
+ {
+ maximum = solutions;
+ perimeter = p;
+ }
+ }
+
+ return perimeter;
+}+
\ No newline at end of file
diff --git a/Euler_4.cpp b/Euler_4.cpp
@@ -0,0 +1,38 @@
+#include <algorithm>
+#include <sstream>
+
+#include "Euler.h"
+
+bool isPalindrome(int i)
+{
+ std::ostringstream oss;
+ oss << i;
+
+ std::string temp = oss.str();
+
+ for (unsigned int i = 0; i < temp.length(); ++i)
+ if (temp.at(i) != temp.at(temp.length() - 1 - i))
+ return false;
+
+ return true;
+}
+
+int Euler::LargestPalindromeFrom3DigitProduct()
+{
+ std::vector<int> products;
+
+ for (int i = 999; i > 99; --i)
+ {
+ for (int j = 999; j >= i; --j)
+ {
+ if (isPalindrome(i * j)) {
+ products.push_back(i * j);
+ break;
+ }
+ }
+ }
+
+ std::sort(products.begin(), products.end());
+
+ return products.back();
+}+
\ No newline at end of file
diff --git a/Euler_40.cpp b/Euler_40.cpp
@@ -0,0 +1,24 @@
+#include "Euler.h"
+
+int product(std::string champ, int pos)
+{
+ if (pos == 1)
+ return 1;
+
+ return (champ[pos - 1] - 48) * product (champ, pos / 10);
+}
+
+int Euler::ChampernowneConstant()
+{
+ std::string champernowne;
+
+ for (int i = 1; i <= 1e6; ++i)
+ {
+ champernowne += std::to_string(i);
+
+ if (champernowne.size() >= 1e6)
+ break;
+ }
+
+ return product(champernowne, 1e6);
+}+
\ No newline at end of file
diff --git a/Euler_41.cpp b/Euler_41.cpp
@@ -0,0 +1,26 @@
+#include <algorithm>
+
+#include "Euler.h"
+
+int determinePanPrime(std::string lexicon)
+{
+ for (int i = 0; i < EulerUtility::factorial(lexicon.size()); ++i)
+ {
+ int potentialPanPrime = atoi(lexicon.c_str());
+ int mod = potentialPanPrime % 10;
+
+ if ((mod % 2 != 0) && (mod != 5))
+ if (EulerUtility::isPrime(potentialPanPrime, 5))
+ return potentialPanPrime;
+
+ std::prev_permutation(lexicon.begin(), lexicon.end());
+ }
+
+
+ return determinePanPrime(lexicon.substr(1, lexicon.size() - 1));
+}
+
+int Euler::PanDigitalPrime()
+{
+ return determinePanPrime("987654321");
+}+
\ No newline at end of file
diff --git a/Euler_42.cpp b/Euler_42.cpp
@@ -0,0 +1,21 @@
+#include "Euler.h"
+
+int Euler::CodedTriangleNumbers()
+{
+ std::vector<std::string> names = EulerUtility::openWordFile("E:\\Euler Resources\\Euler 42.txt");
+
+ int count = 0;
+
+ for (std::string name : names)
+ {
+ int total = 0;
+
+ for (char n : name)
+ total += n - 64;
+
+ if (EulerUtility::isTriangle(total))
+ ++count;
+ }
+
+ return count;
+}+
\ No newline at end of file
diff --git a/Euler_43.cpp b/Euler_43.cpp
@@ -0,0 +1,53 @@
+#include <algorithm>
+#include <numeric>
+
+#include "Euler.h"
+
+void recursePermutations(std::string ¤t, std::vector<llui> &dps, std::vector<std::vector<std::string>> &psl, int pos)
+{
+ for (std::string s : psl[pos])
+ if (s.substr(1, 2) == current.substr(0, 2))
+ {
+ if (current.find(s.substr(0, 1)) == std::string::npos)
+ {
+ std::string concat = s.substr(0, 1) + current;
+
+ if (pos == 0)
+ dps.push_back(EulerUtility::digitsTollui(concat));
+ else
+ recursePermutations(concat, dps, psl, pos - 1);
+ }
+ }
+}
+
+void findDivisiblePermutations(std::vector<llui> &dps, std::vector<std::vector<std::string>> &psl, int pos)
+{
+ for (std::string s : psl[pos])
+ recursePermutations(s, dps, psl, pos - 1);
+
+ for (unsigned i = 0; i < dps.size(); ++i)
+ for (int j = 0; j <= 9; ++j)
+ if (std::to_string(dps[i]).find(std::to_string(j)) == std::string::npos)
+ dps[i] = EulerUtility::digitsTollui(std::to_string(j) + std::to_string(dps[i]));
+}
+
+BigInteger Euler::SubStringDivisibility()
+{
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(18);
+ std::vector<std::vector<std::string>> potentialSubLex(7, std::vector<std::string>());
+ std::vector<llui> divisiblePermutations;
+
+ for (int i = 0; i < 7; ++i)
+ for (int j = 12; j <= 987; ++j)
+ if ((j % primes[i] == 0) && (EulerUtility::hasUniqueDigits(j, true)))
+ potentialSubLex[i].push_back(((j < 100) ? "0" : "") + std::to_string(j));
+
+ findDivisiblePermutations(divisiblePermutations, potentialSubLex, 6);
+
+ BigInteger i = 0;
+
+ for (unsigned long ul : divisiblePermutations)
+ i += ul;
+
+ return i;
+}+
\ No newline at end of file
diff --git a/Euler_44.cpp b/Euler_44.cpp
@@ -0,0 +1,23 @@
+#include "Euler.h"
+
+int getPentagonal(int n)
+{
+ return (n * ((3 * n) - 1)) / 2;
+}
+
+int Euler::MinimizedPentagonalDifference()
+{
+ std::vector<int> pentaNos(1, 1);
+ std::vector<int> potential_D;
+
+ for (;;)
+ {
+ pentaNos.push_back(getPentagonal(pentaNos.size() + 1));
+
+ for (int j = 0; j < pentaNos.size() - 1; ++j)
+ if (EulerUtility::isPentagonal(pentaNos[pentaNos.size() - 1] + pentaNos[j]) && EulerUtility::isPentagonal(pentaNos[pentaNos.size() - 1] - pentaNos[j]))
+ return pentaNos[pentaNos.size() - 1] - pentaNos[j];
+ }
+
+ return 0;
+}+
\ No newline at end of file
diff --git a/Euler_45.cpp b/Euler_45.cpp
@@ -0,0 +1,19 @@
+#include "Euler.h"
+
+llui getTriangular(llui n)
+{
+ return (n * (n + 1)) / 2;
+}
+
+llui Euler::TriangularPentagonalHexagonal()
+{
+ for (int i = 286;; ++i)
+ {
+ llui tri = getTriangular(i);
+
+ if ((i & 1) && EulerUtility::isPentagonal(tri))
+ return tri;
+ }
+
+ return 0;
+}+
\ No newline at end of file
diff --git a/Euler_46.cpp b/Euler_46.cpp
@@ -0,0 +1,31 @@
+#include "Euler.h"
+
+llui Euler::GoldbachsOtherConjecture()
+{
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeilingIndexed(1000000);
+
+ for (int i = 33; i < primes.size(); ++i)
+ {
+ if ((i & 1) && primes[i] == -1)
+ {
+ bool conjecture_holds = false;
+
+ for (int j = 0; j < i; ++j)
+ {
+ if (primes[j] != -1)
+ {
+ if (EulerUtility::isPerfectSquare((i - j) / 2))
+ {
+ conjecture_holds = true;
+ break;
+ }
+ }
+ }
+
+ if (!conjecture_holds)
+ return i;
+ }
+ }
+
+ return 0;
+}+
\ No newline at end of file
diff --git a/Euler_47.cpp b/Euler_47.cpp
@@ -0,0 +1,39 @@
+#include <unordered_set>
+
+#include "Euler.h"
+
+std::unordered_set<int> distinctPrimeFactors(llui target, std::vector<int> &primes)
+{
+ std::unordered_set<int> distinctPrimeFactors;
+
+ int i = 0;
+
+ while (target != 1)
+ {
+ if (target % primes[i] == 0)
+ {
+ target /= primes[i];
+ distinctPrimeFactors.insert(primes[i]);
+ }
+ else
+ ++i;
+ }
+
+ return distinctPrimeFactors;
+}
+
+int Euler::DistinctPrimeFactors()
+{
+ int consecutive = 0;
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(1000000);
+
+ for (int i = 647; ; ++i)
+ {
+ consecutive = (distinctPrimeFactors(i, primes).size() == 4) ? consecutive + 1 : 0;
+
+ if (consecutive == 4)
+ return i - 3;
+ }
+
+ return 0;
+}+
\ No newline at end of file
diff --git a/Euler_48.cpp b/Euler_48.cpp
@@ -0,0 +1,11 @@
+#include "Euler.h"
+
+BigInteger Euler::SelfPowers()
+{
+ BigInteger i;
+
+ for (int j = 1; j <= 1000; ++j)
+ i += EulerUtility::power(j, j);
+
+ return i;
+}+
\ No newline at end of file
diff --git a/Euler_49.cpp b/Euler_49.cpp
@@ -0,0 +1,42 @@
+#include <algorithm>
+
+#include "Euler.h"
+
+std::string Euler::PrimePermutations()
+{
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(10000);
+ std::vector<std::vector<std::string>> primePermutations;
+
+ for (int p : primes)
+ {
+ if (p >= 1000)
+ {
+ bool isUniquePermutation = true;
+ std::string s = std::to_string(p);
+
+ for (int i = 0; i < primePermutations.size(); ++i)
+ {
+ if (std::is_permutation(primePermutations[i][0].begin(), primePermutations[i][0].end(), s.begin()))
+ {
+ isUniquePermutation = false;
+ primePermutations[i].push_back(s);
+ }
+ }
+
+ if (isUniquePermutation)
+ primePermutations.push_back(std::vector<std::string>(1, s));
+ }
+ }
+
+ primePermutations[48] = std::vector<std::string>();
+
+ for (std::vector<std::string> pp : primePermutations)
+ if (pp.size() > 2)
+ for (int i = 0; i < pp.size() - 2; ++i)
+ for (int j = i + 1; j < pp.size() - 1; ++j)
+ for (int k = j + 1; k < pp.size(); ++k)
+ if ((atoi(pp[j].c_str()) * 2) - atoi(pp[i].c_str()) == atoi(pp[k].c_str()))
+ return pp[i] + pp[j] + pp[k];
+
+ return nullptr;
+}+
\ No newline at end of file
diff --git a/Euler_5.cpp b/Euler_5.cpp
@@ -0,0 +1,42 @@
+#include <algorithm>
+#include <numeric>
+
+#include "Euler.h"
+
+void addNewPrimeFactors(int nextDivisor, std::vector<int> &p_factors, std::vector<int> &primes)
+{
+ std::vector<int> myPrimeFactors(p_factors.size(), 0);
+ int i = 0;
+
+ while (nextDivisor != 1 && primes[i] <= nextDivisor)
+ {
+ if ((primes[i] != -1) && (nextDivisor % primes[i] == 0))
+ {
+ nextDivisor /= primes[i];
+ myPrimeFactors[i] += 1;
+ }
+ else
+ ++i;
+ }
+
+ for (int j = 0; j < myPrimeFactors.size(); ++j)
+ if (p_factors[j] < myPrimeFactors[j])
+ p_factors[j] = myPrimeFactors[j];
+}
+
+int Euler::DivisibleBy1To20()
+{
+ int ceiling = 20;
+ std::vector<int> noOfPrimeFactors(ceiling, 0);
+ std::vector<int> primeFactors;
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeilingIndexed(ceiling);
+
+ for (int i = 2; i <= ceiling; ++i)
+ addNewPrimeFactors(i, noOfPrimeFactors, primes);
+
+ for (int i = 0; i < noOfPrimeFactors.size(); ++i)
+ for (int j = 0; j < noOfPrimeFactors[i]; ++j)
+ primeFactors.push_back(primes[i]);
+
+ return std::accumulate(primeFactors.begin(), primeFactors.end(), 1, EulerUtility::multiply);
+}+
\ No newline at end of file
diff --git a/Euler_50.cpp b/Euler_50.cpp
@@ -0,0 +1,55 @@
+#include <numeric>
+
+#include "Euler.h"
+
+int Euler::ConsecutivePrimeSum()
+{
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(1000000);
+ std::vector<int> primes2 = EulerUtility::getPrimesUnderCeilingIndexed(1000000);
+
+ int highestPotential = 0;
+
+ for (int i = 0; i < 600; ++i)
+ {
+ int potentialPrime = std::accumulate(primes.begin(), primes.begin() + 600 - i, 0);
+
+ if (potentialPrime < 1000000)
+ {
+ if (potentialPrime == primes2[potentialPrime])
+ {
+ highestPotential = potentialPrime;
+ int greatestLength = 600 - i;
+
+ for (int j = 1; ; ++j)
+ {
+ bool firstPass = true;
+
+ for (int k = 1; ; ++k)
+ {
+ potentialPrime = std::accumulate(primes.begin() + j, primes.begin() + 600 - i + j + k, 0);
+
+ if (potentialPrime < 1000000)
+ {
+ if ((potentialPrime == primes2[potentialPrime]) && (600 - i + k > greatestLength))
+ {
+ highestPotential = potentialPrime;
+ greatestLength = 600 - i + k;
+ }
+
+ firstPass = false;
+ }
+ else
+ {
+ if (firstPass)
+ return highestPotential;
+
+ break;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ return 0;
+}+
\ No newline at end of file
diff --git a/Euler_51.cpp b/Euler_51.cpp
@@ -0,0 +1,65 @@
+#include <algorithm>
+#include "Euler.h"
+
+struct pair
+{
+ int prime;
+ int digit;
+};
+
+int Euler::PrimeDigitReplacements()
+{
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeilingIndexed(1000000);
+ std::vector<pair> candidates;
+
+ for (int prime : primes)
+ {
+ if (prime != -1)
+ {
+ std::vector<int> digits = EulerUtility::intToDigits(prime);
+
+ int repeatedDigits[3] = {0, 0, 0};
+
+ for (int i = 0; i < digits.size() - 1; ++i)
+ if (digits[i] <= 2)
+ ++repeatedDigits[digits[i]];
+
+ for (int i = 0; i < 3; ++i)
+ if (repeatedDigits[i] == 3)
+ {
+ pair p;
+ p.prime = prime;
+ p.digit = i;
+ candidates.push_back(p);
+ }
+ }
+ }
+
+ for (pair p : candidates)
+ {
+ std::vector<int> digits = EulerUtility::intToDigits(p.prime);
+ std::vector<int> indices;
+ int sizeOfFamily = 1;
+
+ for (int i = 0; i < digits.size() - 1; ++i)
+ if (digits[i] == p.digit)
+ indices.push_back(i);
+
+ for (int i = 0; i < 10; ++i)
+ {
+ if ((i != p.digit) && (i != 0 || indices[0] != 0))
+ {
+ for (int idx : indices)
+ digits[idx] = i;
+
+ if (primes[EulerUtility::digitsToInteger(digits)] > 0)
+ ++sizeOfFamily;
+ }
+ }
+
+ if (sizeOfFamily >= 8)
+ return p.prime;
+ }
+
+ return 0;
+}+
\ No newline at end of file
diff --git a/Euler_52.cpp b/Euler_52.cpp
@@ -0,0 +1,23 @@
+#include <algorithm>
+#include "Euler.h"
+
+int Euler::PermutedMultiples()
+{
+ for (int i = 1;;++i)
+ {
+ std::vector<int> digits = EulerUtility::intToDigits(i);
+
+ for (int j = 2; j < 7; ++j)
+ {
+ std::vector<int> multiple = EulerUtility::intToDigits(i * j);
+
+ if (!std::is_permutation(digits.begin(), digits.end(), multiple.begin()))
+ break;
+
+ if (j == 6)
+ return i;
+ }
+ }
+
+ return 0;
+}+
\ No newline at end of file
diff --git a/Euler_53.cpp b/Euler_53.cpp
@@ -0,0 +1,13 @@
+#include "Euler.h"
+
+int Euler::CombinatoricSelections()
+{
+ int total = 0;
+
+ for (int i = 1; i <= 100; ++i)
+ for (int j = 1; j <= i; ++j)
+ if (EulerUtility::choose(i, j) > 1000000)
+ ++total;
+
+ return total;
+}+
\ No newline at end of file
diff --git a/Euler_54.cpp b/Euler_54.cpp
@@ -0,0 +1,245 @@
+#include <algorithm>
+#include <fstream>
+#include <functional>
+#include <unordered_set>
+
+#include "Euler.h"
+
+struct hand
+{
+ int handValue;
+ std::vector<int> cardValues;
+};
+
+struct game
+{
+ hand hands[2];
+};
+
+char order[] = {'2', '3', '4', '5', '6', '7', '8', '9', 'T', 'J', 'Q', 'K', 'A'};
+
+bool isFlush(std::vector<std::string>& hand)
+{
+ char c = hand[0][1];
+
+ for (int i = 1; i < hand.size(); ++i)
+ if (hand[i][1] != c)
+ return false;
+
+ return true;
+}
+
+bool isStraight(std::vector<int> indices)
+{
+ for (int i = 1; i < indices.size(); ++i)
+ if (indices[i] != indices[i - 1] - 1)
+ return false;
+
+ return true;
+}
+
+std::vector<int> getCardValues(std::vector<std::string>& hand)
+{
+ std::vector<int> indices;
+
+ for (int i = 0; i < hand.size(); ++i)
+ for (int j = 0; j < 13; ++j)
+ {
+ char c = hand[i][0];
+ if (c == order[j])
+ {
+ indices.push_back(j);
+ break;
+ }
+ }
+
+ std::sort(indices.begin(), indices.end(), std::greater<int>());
+
+ return indices;
+}
+
+int determineNoOfRepeats(std::unordered_set<int>& us, std::vector<int>& cardValues, int t, int def, int high)
+{
+ for (int j : us)
+ {
+ int total = 0;
+
+ for (int k = 0; k < cardValues.size(); ++k)
+ if (j == cardValues[k])
+ ++total;
+
+ if (total == t)
+ return high;
+ }
+
+ return def;
+}
+
+int determineRepeat(std::unordered_set<int>& us, std::vector<int>& cardValues, int rep, bool skip)
+{
+ for (int j : us)
+ {
+ int total = 0;
+
+ for (int k = 0; k < cardValues.size(); ++k)
+ if (j == cardValues[k])
+ ++total;
+
+ if (total == rep)
+ {
+ if (skip)
+ skip = false;
+ else
+ return j;
+ }
+ }
+
+ return -1;
+}
+
+void determinePriorityOrder(hand& h, std::unordered_set<int>& us)
+{
+ if (h.handValue == 4 || h.handValue == 0)
+ return;
+
+ std::vector<int> values(h.cardValues);
+ int rep1, rep2, no = 0;
+
+ switch(h.handValue)
+ {
+ case 1:
+ rep1 = determineRepeat(us, h.cardValues, 2, false);
+
+ for (int i = 0; i < h.cardValues.size(); ++i)
+ if (h.cardValues[i] == rep1)
+ std::swap(h.cardValues[no++], h.cardValues[i]);
+
+ std::sort(h.cardValues.begin() + 2, h.cardValues.end(), std::greater<int>());
+ break;
+ case 2:
+ rep1 = determineRepeat(us, h.cardValues, 2, true);
+ rep2 = determineRepeat(us, h.cardValues, 2, false);
+
+ if (rep2 > rep1)
+ std::swap(rep1, rep2);
+
+ for (int i = 0; i < h.cardValues.size(); ++i)
+ {
+ if (h.cardValues[i] == rep1)
+ std::swap(h.cardValues[no++], h.cardValues[i]);
+ }
+
+ for (int i = 0; i < h.cardValues.size(); ++i)
+ if (h.cardValues[i] == rep2)
+ std::swap(h.cardValues[no++], h.cardValues[i]);
+ break;
+ case 3:
+ rep1 = determineRepeat(us, h.cardValues, 3, false);
+
+ for (int i = 0; i < h.cardValues.size(); ++i)
+ if (h.cardValues[i] == rep1)
+ std::swap(h.cardValues[no++], h.cardValues[i]);
+
+ std::sort(h.cardValues.begin() + 3, h.cardValues.end(), std::greater<int>());
+ break;
+ case 6:
+ rep1 = determineRepeat(us, h.cardValues, 3, false);
+ for (int i = 0; i < h.cardValues.size(); ++i)
+ if (h.cardValues[i] == rep1)
+ std::swap(h.cardValues[no++], h.cardValues[i]);
+
+ break;
+ case 7:
+ rep1 = determineRepeat(us, h.cardValues, 4, false);
+
+ for (int i = 0; i < h.cardValues.size(); ++i)
+ if (h.cardValues[i] == rep1)
+ std::swap(h.cardValues[no++], h.cardValues[i]);
+ break;
+ }
+}
+
+game determineHands(std::vector<std::string>& cards)
+{
+ game g;
+
+ std::vector<std::string> hands[2];
+
+ hands[0] = std::vector<std::string>(cards.begin(), cards.begin() + 5);
+ hands[1] = std::vector<std::string>(cards.begin() + 5, cards.end());
+
+ for (int i = 0; i < 2; ++i)
+ {
+ g.hands[i].cardValues = getCardValues(hands[i]);
+
+ if (isFlush(hands[i]))
+ {
+ g.hands[i].handValue = isStraight(g.hands[i].cardValues) ? (g.hands[i].cardValues[4] == 12 ? 9 : 8) : 5;
+ }
+ else
+ {
+ std::unordered_set<int> us;
+
+ for (int j : g.hands[i].cardValues)
+ us.insert(j);
+
+ switch(us.size())
+ {
+ case 2:
+ g.hands[i].handValue = determineNoOfRepeats(us, g.hands[i].cardValues, 4, 6, 7);
+ break;
+ case 3:
+ g.hands[i].handValue = determineNoOfRepeats(us, g.hands[i].cardValues, 3, 2, 3);
+ break;
+ case 4:
+ g.hands[i].handValue = 1;
+ break;
+ case 5:
+ g.hands[i].handValue = isStraight(g.hands[i].cardValues) ? 4 : 0;
+ break;
+ }
+
+ determinePriorityOrder(g.hands[i], us);
+ }
+
+
+ }
+
+ return g;
+}
+
+bool determineWinner(game g) //assumes no draws
+{
+ if (g.hands[0].handValue > g.hands[1].handValue)
+ return false;
+
+ if (g.hands[1].handValue > g.hands[0].handValue)
+ return true;
+
+ for (int i = 0; i < g.hands[0].cardValues.size(); ++i)
+ {
+ if (g.hands[0].cardValues[i] > g.hands[1].cardValues[i])
+ return false;
+
+ if (g.hands[1].cardValues[i] > g.hands[0].cardValues[i])
+ return true;
+ }
+
+ return true;
+}
+
+int Euler::PokerHands()
+{
+ int scores[2] = {0, 0};
+
+ std::ifstream fin;
+ fin.open("E:\\Euler Resources\\Euler 54.txt");
+ int idx = 0;
+
+ for (std::string line; std::getline(fin, line);)
+ ++scores[determineWinner(determineHands(EulerUtility::strTokenizer(line, ' ')))];
+
+ fin.close();
+
+ return scores[0];
+}+
\ No newline at end of file
diff --git a/Euler_55.cpp b/Euler_55.cpp
@@ -0,0 +1,53 @@
+#include <sstream>
+
+#include "Euler.h"
+
+bool isPalindrome(BigInteger i)
+{
+ std::ostringstream oss;
+ oss << i;
+
+ std::string temp = oss.str();
+
+ for (unsigned int j = 0; j < temp.length() / 2 + 1; ++j)
+ if (temp.at(j) != temp.at(temp.length() - 1 - j))
+ return false;
+
+ return true;
+}
+
+BigInteger reverse(BigInteger i)
+{
+ BigInteger reverse = 0;
+
+ while(i > 0)
+ {
+ reverse = reverse * 10 + (i % 10);
+ i /= 10;
+ }
+
+ return reverse;
+}
+
+BigInteger Euler::LychrelNumbers()
+{
+ int lychel = 9999;
+
+ for (int i = 1; i < 10000; ++i)
+ {
+ BigInteger current(i);
+
+ for (int j = 0; j < 50; ++j)
+ {
+ current = current + reverse(current);
+
+ if (isPalindrome(current))
+ {
+ --lychel;
+ break;
+ }
+ }
+ }
+
+ return lychel;
+}+
\ No newline at end of file
diff --git a/Euler_56.cpp b/Euler_56.cpp
@@ -0,0 +1,22 @@
+#include <numeric>
+
+#include "Euler.h"
+
+int Euler::PowerfulDigitSum()
+{
+ int highestDigitSum = 0;
+
+ for (int i = 1; i < 100; ++i)
+ {
+ for (int j = 1; j < 100; ++j)
+ {
+ std::vector<int> digits = EulerUtility::powerDigits(i,j);
+ int digitSum = std::accumulate(digits.begin(), digits.end(), 0);
+
+ if (digitSum > highestDigitSum)
+ highestDigitSum = digitSum;
+ }
+ }
+
+ return highestDigitSum;
+}+
\ No newline at end of file
diff --git a/Euler_57.cpp b/Euler_57.cpp
@@ -0,0 +1,19 @@
+#include "Euler.h"
+
+int Euler::SquareRootConvergents()
+{
+ BigInteger n = 3, d = 2;
+ int count = 0;
+
+ for (int i = 1; i < 1000; ++i)
+ {
+ n += d;
+ std::swap(n, d);
+ n += d;
+
+ if (EulerUtility::BigIntToDigits(n).size() > EulerUtility::BigIntToDigits(d).size())
+ ++count;
+ }
+
+ return count;
+}+
\ No newline at end of file
diff --git a/Euler_58.cpp b/Euler_58.cpp
@@ -0,0 +1,29 @@
+#include "Euler.h"
+
+ll Euler::SpiralPrimes()
+{
+ ll n = 8, d = 13, i = 26, count = 7, topRight = 31;
+ int mod3 = -1;
+
+ while ((n / (double)d) * 100 >= 10)
+ {
+ topRight += i;
+ count += 2;
+ d += 4;
+ i += 8;
+ mod3 = (mod3 + 1) % 3;
+
+ if (EulerUtility::isPrime(topRight + count - 1, 5))
+ ++n;
+
+ if (mod3 != 0)
+ if (EulerUtility::isPrime(topRight, 5))
+ ++n;
+
+ if (mod3 != 1)
+ if (EulerUtility::isPrime(topRight + (count * 2) - 2, 5))
+ ++n;
+ }
+
+ return count;
+}+
\ No newline at end of file
diff --git a/Euler_59.cpp b/Euler_59.cpp
@@ -0,0 +1,39 @@
+#include <fstream>
+#include <numeric>
+
+#include "Euler.h"
+
+int Euler::xorDecryption()
+{
+ const int file_size = 1201;
+
+ std::ifstream file;
+ std::vector<int> cypher;
+ std::string character;
+ std::string word = " the ";
+
+ file.open("E:\\Euler Resources\\Euler 59.txt");
+
+ while(getline(file, character, ','))
+ cypher.push_back(atoi(character.c_str()));
+
+ char message[file_size];
+ int pwd[3];
+
+ for (pwd[0] = 'a'; pwd[0] < 'z' + 1; ++pwd[0])
+ {
+ for (pwd[1] = 'a'; pwd[1] < 'z' + 1; ++pwd[1])
+ {
+ for (pwd[2] = 'a'; pwd[2] < 'z' + 1; ++pwd[2])
+ {
+ for (int i = 0; i < file_size; ++i)
+ message[i] = cypher[i] ^ pwd[i % 3];
+
+ if (std::string(message).find(word) != std::string::npos)
+ return std::accumulate(message, message + file_size, 0);
+ }
+ }
+ }
+
+ return 0;
+}+
\ No newline at end of file
diff --git a/Euler_6.cpp b/Euler_6.cpp
@@ -0,0 +1,15 @@
+#include "Euler.h"
+
+int Euler::DifferenceSumOfSquaresSquareOfSum100()
+{
+ int sumOfSquares = 0;
+ int squareOfSum = 0;
+
+ for (int i = 1; i <= 100; ++i) {
+ squareOfSum += i;
+ sumOfSquares += (int)pow(i, 2);
+ }
+
+ squareOfSum = (int)pow(squareOfSum, 2);
+ return squareOfSum - sumOfSquares;
+}+
\ No newline at end of file
diff --git a/Euler_60.cpp b/Euler_60.cpp
@@ -0,0 +1,65 @@
+#include <algorithm>
+#include <unordered_set>
+
+#include "Euler.h"
+
+int Euler::PrimePairSets()
+{
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(100000);
+
+ std::vector<std::vector<int>> concatPrimes(10000, std::vector<int>());
+
+ for (int i = 0; i < 10000; ++i)
+ {
+ if (EulerUtility::isPrime(i, 5))
+ {
+ for (int p : primes)
+ {
+ if (p < i)
+ {
+ std::vector<int> concat(1, i);
+ concat.push_back(p);
+
+ int c = EulerUtility::digitsToInteger(concat);
+
+ if (EulerUtility::isPrime(c, 5))
+ {
+ std::swap(concat[0], concat[1]);
+ c = EulerUtility::digitsToInteger(concat);
+
+ if (EulerUtility::isPrime(c, 5))
+ {
+ concatPrimes[i].push_back(p);
+ concatPrimes[p].push_back(i);
+ }
+ }
+ }
+ else
+ break;
+ }
+ }
+ }
+
+ for (int i = 0; i < 10000; ++i)
+ {
+ for (int j : concatPrimes[i])
+ {
+ std::vector<int> intersection_a = EulerUtility::intersect(concatPrimes[i], concatPrimes[j]);
+
+ for (int k : intersection_a)
+ {
+ std::vector<int> intersection_b = EulerUtility::intersect(intersection_a, concatPrimes[k]);
+
+ for (int l : intersection_b)
+ {
+ std::vector<int> intersection_c = EulerUtility::intersect(intersection_b, concatPrimes[l]);
+
+ if (intersection_c.size() > 0)
+ return i + j + k + l + intersection_c[0];
+ }
+ }
+ }
+ }
+
+ return 0;
+}+
\ No newline at end of file
diff --git a/Euler_61.cpp b/Euler_61.cpp
@@ -0,0 +1,74 @@
+#include <numeric>
+
+#include "Euler.h"
+
+bool match(int a, int b)
+{
+ std::vector<int> digits_a = EulerUtility::intToDigits(a);
+ std::vector<int> digits_b = EulerUtility::intToDigits(b);
+
+ return (digits_a[2] == digits_b[0] && digits_a[3] == digits_b[1]);
+}
+
+int recurseFigurates(std::vector<int> cycle, std::vector<std::vector<int>> &figurates, std::vector<int> indices, int index)
+{
+ for (int swap_index = index + 1; swap_index < 7; ++swap_index)
+ {
+ for (int i : figurates[indices[index]])
+ {
+ if (match(cycle[cycle.size() - 1], i))
+ {
+ cycle.push_back(i);
+
+ int answer = ((cycle.size() == 6) && (match(cycle[cycle.size() - 1], cycle[0]))) ?
+ std::accumulate(cycle.begin(), cycle.end(), 0) : ((cycle.size() == 6) || (index >= 5)) ? 0 :
+ recurseFigurates(cycle, figurates, indices, index + 1);
+
+ if (answer != 0)
+ {
+ return answer;
+ }
+
+ cycle.pop_back();
+ }
+ }
+
+ if (swap_index < 6)
+ {
+ int temp = indices[swap_index];
+ indices.erase(indices.begin() + swap_index);
+ indices.insert(indices.begin() + index, temp);
+ }
+ }
+
+ return 0;
+}
+
+int Euler::CyclicFigurateNumbers()
+{
+ std::vector<std::vector<int>> figurates;
+ std::vector<int> indices;
+ std::vector<int> cycle;
+
+ for (int i = 0; i < 6; ++i)
+ {
+ indices.push_back(i);
+ figurates.push_back(EulerUtility::getFigurates(i + 3, 1000, 10000));
+ }
+
+ for (int i : figurates[0])
+ {
+ cycle.push_back(i);
+
+ int answer = recurseFigurates(cycle, figurates, indices, 1);
+
+ if (answer != 0)
+ {
+ return answer;
+ }
+
+ cycle.pop_back();
+ }
+
+ return 0;
+}+
\ No newline at end of file
diff --git a/Euler_62.cpp b/Euler_62.cpp
@@ -0,0 +1,40 @@
+#include <algorithm>
+#include <map>
+
+#include "Euler.h"
+
+llui Euler::CubicPermutations()
+{
+ std::map<std::string, std::vector<llui>> cubicGroups;
+
+ for (llui i = 346;; ++i)
+ {
+ std::vector<int> cubeDigits = EulerUtility::lluiToDigits(i * i * i);
+ std::sort(cubeDigits.begin(), cubeDigits.end());
+
+ std::string key;
+
+ for (int j : cubeDigits)
+ key.push_back(j + '0');
+
+ std::map<std::string, std::vector<llui>>::iterator it = cubicGroups.find(key);
+
+ if (it == cubicGroups.end())
+ {
+ std::vector<llui> newGroup;
+ newGroup.push_back(i * i * i);
+ cubicGroups.insert(std::pair<std::string, std::vector<llui>>(key, newGroup));
+ }
+ else
+ {
+ it->second.push_back(i * i * i);
+
+ if (it->second.size() == 5)
+ {
+ return it->second[0];
+ }
+ }
+ }
+
+ return 0;
+}+
\ No newline at end of file
diff --git a/Euler_63.cpp b/Euler_63.cpp
@@ -0,0 +1,23 @@
+#include "Euler.h"
+
+int Euler::PowerfulDigitCounts()
+{
+ int count = 0;
+
+ for (BigInteger i = 1; i < 10; ++i)
+ {
+ for (int p = 1;; ++p)
+ {
+ if (EulerUtility::BigIntToDigits(EulerUtility::power(i, p)).size() == p)
+ {
+ ++count;
+ }
+ else
+ {
+ break;
+ }
+ }
+ }
+
+ return count;
+}+
\ No newline at end of file
diff --git a/Euler_64.cpp b/Euler_64.cpp
@@ -0,0 +1,84 @@
+//#include <boost/multiprecision/cpp_dec_float.hpp>
+
+#include "Euler.h"
+
+//namespace mp = boost::multiprecision;
+//
+//typedef mp::number<mp::cpp_dec_float<500>> cpp_dec_float_500;
+//
+//int Euler::OddPeriodSquareRoots()
+//{
+// int count = 0;
+//
+// for (cpp_dec_float_500 i = 1; i <= 10000; ++i)
+// {
+// int sequenceLength = 0;
+//
+// cpp_dec_float_500 value = mp::sqrt(i);
+// cpp_dec_float_500 floor = mp::floor(value);
+//
+// if (!EulerUtility::isPerfectSquare(i.convert_to<int>()))
+// {
+// bool sequenceDetermined = false;
+// bool sequenceIsOdd = false;
+//
+// while (!sequenceDetermined)
+// {
+// value = 1.0 / (value - mp::floor(value));
+//
+// if (mp::floor(value) == 2 * floor)
+// {
+// sequenceDetermined = true;
+// sequenceIsOdd = sequenceLength + 1 & 1;
+// }
+// else
+// {
+// ++sequenceLength;
+// }
+// }
+//
+// if (sequenceIsOdd)
+// {
+// ++count;
+// }
+// }
+// }
+//
+// return count;
+//}
+
+int period(int n)
+{
+ double n2 = std::sqrtl(n);
+ int a = n2, p = 0, q = 1, length = 0;
+
+ do
+ {
+ length++;
+ p = a * q - p;
+ q = ( n - p * p ) / q;
+ a = ( p + n2 ) /q;
+ } while ( q != 1 );
+
+ return length;
+}
+
+int Euler::OddPeriodSquareRoots()
+{
+ int odds = 0;
+
+ for (int n = 1; n <= 10000; n++)
+ {
+ int n2 = sqrt(n);
+
+ if (n2 * n2 != n)
+ {
+ if (period(n) & 1)
+ {
+ odds++;
+ }
+ }
+ }
+
+ return odds;
+}+
\ No newline at end of file
diff --git a/Euler_65.cpp b/Euler_65.cpp
@@ -0,0 +1,58 @@
+#include <numeric>
+
+#include "Euler.h"
+
+std::vector<BigInteger> recurseFraction2(std::vector<BigInteger> period, BigInteger n, std::vector<BigInteger> fraction)
+{
+ if (n > period.size() - 1)
+ return fraction;
+
+ std::swap(fraction[0], fraction[1]);
+
+ fraction[0] = (fraction[1] * period[period.size() - n.toInt() - 1]) + fraction[0];
+
+ return recurseFraction2(period, n + 1, fraction);
+}
+
+std::vector<BigInteger> recurseFraction2(std::vector<BigInteger> period, BigInteger n)
+{
+ std::vector<BigInteger> fraction;
+
+ fraction.push_back(period[period.size() - 1]);
+ fraction.push_back(1);
+
+ return recurseFraction2(period, 1, fraction);
+}
+
+BigInteger periodiuy()
+{
+ std::vector<BigInteger> period;
+
+ period.push_back(2);
+
+ int n = 2;
+
+ for (int i = 1; i < 100; ++i)
+ {
+ if (i % 3 == 2)
+ {
+ period.push_back(n);
+ n += 2;
+ }
+ else
+ {
+ period.push_back(1);
+ }
+ }
+
+
+ std::vector<BigInteger> approx = recurseFraction2(period, 0);
+ return approx[0];
+}
+
+int Euler::ConvergentsOfE()
+{
+ std::vector<int> digits = EulerUtility::BigIntToDigits(periodiuy());
+
+ return std::accumulate(digits.begin(), digits.end(), 0);
+}
diff --git a/Euler_66.cpp b/Euler_66.cpp
@@ -0,0 +1,74 @@
+#include "Euler.h"
+
+bool valueOfDiophantine(BigInteger x, BigInteger y, BigInteger n)
+{
+ return EulerUtility::power(x, 2) - (n * EulerUtility::power(y, 2)) == BigInteger(1);
+}
+
+std::vector<BigInteger> recurseFraction(std::vector<BigInteger> period, BigInteger n, std::vector<BigInteger> fraction)
+{
+ if (n > period.size() - 1)
+ return fraction;
+
+ std::swap(fraction[0], fraction[1]);
+
+ fraction[0] = (fraction[1] * period[period.size() - n.toInt() - 1]) + fraction[0];
+
+ return recurseFraction(period, n + 1, fraction);
+}
+
+std::vector<BigInteger> recurseFraction(std::vector<BigInteger> period, BigInteger n)
+{
+ std::vector<BigInteger> fraction;
+
+ fraction.push_back(period[period.size() - 1]);
+ fraction.push_back(1);
+
+ return recurseFraction(period, 1, fraction);
+}
+
+BigInteger valueOfX(BigInteger n)
+{
+ double n2 = std::sqrtl(n.toInt());
+ BigInteger a = (int)n2, p = 0, q = 1;
+
+ std::vector<BigInteger> period;
+ std::vector<BigInteger> approx;
+
+ period.push_back(a);
+
+ do
+ {
+ p = a * q - p;
+ q = ( n - p * p ) / q;
+ a = (long)(( p.toLong() + n2 ) /q.toLong());
+
+ period.push_back(a);
+ approx = recurseFraction(period, 0);
+
+ } while (valueOfDiophantine(approx[0], approx[1], n) != 1);
+
+ return approx[0];
+}
+
+int Euler::Diophantine()
+{
+ BigInteger currentMax = 0;
+ int valueOfD = 0;
+
+ for (int i = 2; i <= 1000; ++i)
+ {
+ if (!EulerUtility::isPerfectSquare(i))
+ {
+ BigInteger x = valueOfX(i);
+
+ if (x > currentMax)
+ {
+ currentMax = x;
+ valueOfD = i;
+ }
+ }
+ }
+
+ return valueOfD;
+}
diff --git a/Euler_68.cpp b/Euler_68.cpp
@@ -0,0 +1,87 @@
+#include <algorithm>
+#include <set>
+#include "Euler.h"
+
+std::string magicString(std::vector<int**> rows)
+{
+ int lowestIndex = 0;
+ int lowestVal = 11;
+
+ for (int i = 0; i < 5; ++i)
+ {
+ if (*rows[i][0] < lowestVal)
+ {
+ lowestVal = *rows[i][0];
+ lowestIndex = i;
+ }
+ }
+
+ std::string magic5;
+
+ for (int i = 0; i < 5; ++i)
+ {
+ int index = (i + lowestIndex) % 5;
+
+ if ( *rows[index][0] == 10)
+ {
+ magic5.push_back('1');
+ magic5.push_back('0');
+ }
+ else
+ {
+ magic5.push_back(*rows[index][0] + '0');
+ }
+
+ magic5.push_back(*rows[index][1] + '0');
+ magic5.push_back(*rows[index][2] + '0');
+ }
+
+ return magic5;
+}
+
+int sumRow(int* row[])
+{
+ return *row[0] + *row[1] + *row[2];
+}
+
+std::string Euler::Magic5GonRing()
+{
+ std::vector<int> nodes;
+ std::set<std::string> magicStrings;
+
+ for (int i = 1; i <= 10; ++i)
+ nodes.push_back(i);
+
+ int* row1[] = { &nodes[0], &nodes[1], &nodes[2] };
+ int* row2[] = { &nodes[3], &nodes[2], &nodes[4] };
+ int* row3[] = { &nodes[5], &nodes[4], &nodes[6] };
+ int* row4[] = { &nodes[7], &nodes[6], &nodes[8] };
+ int* row5[] = { &nodes[9], &nodes[8], &nodes[1] };
+
+ std::vector<int**> rows;
+
+ rows.push_back(row1);
+ rows.push_back(row2);
+ rows.push_back(row3);
+ rows.push_back(row4);
+ rows.push_back(row5);
+
+ for (int i = 1; i < EulerUtility::factorial(10); ++i)
+ {
+ std::next_permutation(nodes.begin(), nodes.end());
+
+ int val = sumRow(row1);
+
+ if ((*row1[0] == 10 || *row2[0] == 10 || *row3[0] == 10 || *row4[0] == 10 || *row5[0] == 10)
+ && ((sumRow(row2) == val) && (sumRow(row3) == val) && (sumRow(row4) == val) && (sumRow(row5) == val)))
+ magicStrings.insert(magicString(rows));
+ }
+
+ std::set<std::string>::iterator it;
+ std::string last;
+
+ for (it = magicStrings.begin(); it != magicStrings.end(); ++it)
+ last = *it;
+
+ return last;
+}+
\ No newline at end of file
diff --git a/Euler_69.cpp b/Euler_69.cpp
@@ -0,0 +1,21 @@
+#include "Euler.h"
+
+int Euler::EulerTotient()
+{
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(1e6);
+ std::vector<int> primesIndexed = EulerUtility::getPrimesUnderCeilingIndexed(1e6);
+ double NoverPhi = 0, n = 0;
+
+ for (double i = 2; i <= 1e6; ++i)
+ {
+ int p = EulerUtility::phi(i, primes, primesIndexed);
+
+ if (i / p > NoverPhi)
+ {
+ NoverPhi = i / p;
+ n = i;
+ }
+ }
+
+ return n;
+}+
\ No newline at end of file
diff --git a/Euler_7.cpp b/Euler_7.cpp
@@ -0,0 +1,29 @@
+#include "Euler.h"
+
+int Euler::Get10001stPrime()
+{
+ int noOfPrimes = 0;
+
+ bool is_prime;
+
+ int count = 2; //includes 2 & 3
+ int my_prime = 2; //set to first prime
+
+ for(int i = 5; count < 1000000; i += 2)
+ {
+ is_prime = true;
+
+ for(int j = 3; j * j <= i && is_prime; j += 2)
+ if(i % j == 0) is_prime = false;
+
+ if(is_prime) {
+ ++count;
+ my_prime = i;
+
+ if (count == 10001)
+ return i;
+ }
+ }
+
+ return 0;
+}
diff --git a/Euler_70.cpp b/Euler_70.cpp
@@ -0,0 +1,25 @@
+#include <algorithm>
+
+#include "Euler.h"
+
+int Euler::TotientPermutation()
+{
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(1e7);
+ std::vector<int> primesIndexed = EulerUtility::getPrimesUnderCeilingIndexed(1e7);
+ double NoverPhi = 1e8, n = 0;
+
+ for (double i = 2; i <= 1e7; ++i)
+ {
+ int p = EulerUtility::phi(i, primes, primesIndexed);
+
+ std::vector<int> digits = EulerUtility::intToDigits(i);
+
+ if ((std::is_permutation(digits.begin(), digits.end(), EulerUtility::intToDigits(p).begin())) && (NoverPhi > i / p))
+ {
+ NoverPhi = i / p;
+ n = i;
+ }
+ }
+
+ return n;
+}+
\ No newline at end of file
diff --git a/Euler_71.cpp b/Euler_71.cpp
@@ -0,0 +1,43 @@
+#include "Euler.h"
+
+int Euler::OrderedFractions()
+{
+ //I did this problem by with pen + paper, but here was my thought process.
+ //For me, this was the most obvious starting point for denominator d <= 1,000,000
+
+ EulerUtility::gcd(299999, 700000); //gcd = 7
+
+ //Ok, they aren't relatively prime; Divide them down.
+
+ EulerUtility::gcd(42857, 100000);
+
+ //At this point I noticed that this numerator was similar to the repeating decimal of 3/7 (0.(428571)*...).
+ //I remembered that you can represent a repeating pattern as a fraction by taking the sequence and dividing it by nines
+ //luckily the sequence allows for d <=1,000,000 (though in hindsight, the problem was most likely designed with
+ //this property in mind).
+
+ EulerUtility::gcd(428571, 999999); //equal to 3/7
+
+ EulerUtility::gcd(428570, 999999); //Removed 1, noticed that gcd = 1. Therefore relatively prime, and since there is
+ //no value of d larger except 1,000,000 itself (which seems very unlikely) then
+ //it is probably the answer. If it wasn't, then it would narrow the answer down to
+ //d = 1,000,000 which would be trivial to work out from there.
+
+ int xmax = 0, xmaxd = 2;
+
+ for (int d = 2; d <= 1000000; ++d)
+ {
+ int x = 3 * d / 7;
+
+ if ((d % 7) == 0)
+ {
+ --x;
+ }
+ if (x * xmaxd > xmax * d)
+ {
+ xmax = x, xmaxd = d;
+ }
+ }
+
+ return xmax; //As it happens, it was correct.
+}+
\ No newline at end of file
diff --git a/Euler_72.cpp b/Euler_72.cpp
@@ -0,0 +1,16 @@
+#include "Euler.h"
+
+llui Euler::CountingFractions()
+{
+ llui total = 0;
+
+ std::vector<int> primesIndexed = EulerUtility::getPrimesUnderCeilingIndexed(1e6);
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(1e6);
+
+ for (int i = 1; i <= 1e6; ++i)
+ {
+ total += EulerUtility::phi(i, primes, primesIndexed);
+ }
+
+ return total;
+}+
\ No newline at end of file
diff --git a/Euler_73.cpp b/Euler_73.cpp
@@ -0,0 +1,54 @@
+#include "Euler.h"
+
+//def farey( n, asc=True ):
+// """Python function to print the nth Farey sequence, either ascending or descending."""
+// if asc:
+// a, b, c, d = 0, 1, 1 , n # (*)
+// else:
+// a, b, c, d = 1, 1, n-1, n # (*)
+// print "%d/%d" % (a,b)
+// while (asc and c <= n) or (not asc and a > 0):
+// k = int((n + b)/d)
+// a, b, c, d = c, d, k*c - a, k*d - b
+// print "%d/%d" % (a,b)
+
+
+
+llui Euler::CountingRangedFractions()
+{
+ llui count = 0;
+ bool counting = false;
+
+ int n = 12000;
+ int a = 0;
+ int b = 1;
+ int c = 1;
+ int d = n;
+ int x = 0;
+
+ while (c <= n && !(a == 1 && b == 2))
+ {
+ int k = 0;
+
+ if (d != 0)
+ k = int((n + b)/d);
+ else
+ ++x;
+
+ int temp_a = a;
+ int temp_b = b;
+
+ a = c;
+ b = d;
+ c = k * c - temp_a;
+ d = k * d - temp_b;
+
+ if (counting)
+ ++count;
+
+ if (a == 1 && b == 3)
+ counting = true;
+ }
+
+ return count - 1;
+}+
\ No newline at end of file
diff --git a/Euler_74.cpp b/Euler_74.cpp
@@ -0,0 +1,93 @@
+#include <algorithm>
+#include <set>
+
+#include "Euler.h"
+
+int recurseChain(llui head, std::set<llui> &chain, int factorials[], int size)
+{
+ llui tempHead = head;
+ llui newHead = 0;
+
+ while (tempHead != 0)
+ {
+ newHead += factorials[tempHead % 10];
+ tempHead /= 10;
+ }
+
+ //found in problem 34
+ if (newHead == 1 || newHead == 2 || newHead == 145 || newHead == 40585)
+ return size + 1;
+
+ //cycles given in the problem
+ if (newHead == 871 || newHead == 872 || newHead == 45361 || newHead == 45362)
+ return size + 2;
+ if (newHead == 169 || newHead == 1454 || newHead == 363601)
+ return size + 3;
+
+ chain.insert(newHead);
+
+ if (chain.size() == size || chain.size() > 60)
+ {
+ return chain.size();
+ }
+
+ return recurseChain(newHead, chain, factorials, chain.size());
+}
+
+int Euler::DigitFactorialChains()
+{
+ int total = 0;
+ int factorials[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
+
+ std::vector<std::vector<int>> solutions;
+
+ for (int i = 1; i < 1e6; ++i)
+ {
+ bool ordered = true;
+
+ for (int temp = i; temp != 0; temp /= 10)
+ {
+ if (((temp % 10) < ((temp / 10) % 10)) && ((temp % 10) != 0))
+ {
+ ordered = false;
+ break;
+ }
+ }
+
+ //we only check ascending values, e.g. 1243 has the same chain as 1234.
+ //zero is a wild card, therfore 1034 counts as ascending.
+ if (ordered)
+ {
+ std::set<llui> chain;
+
+ chain.insert(i);
+
+ if (recurseChain(i, chain, factorials, chain.size()) == 60)
+ {
+ //this uniqueness check is necessary because solutions containing zero break the ascending rule
+ std::vector<int> digits = EulerUtility::intToDigits(i);
+ bool unique = true;
+
+ for (std::vector<int> s : solutions)
+ if (std::is_permutation(digits.begin(), digits.end(), s.begin()))
+ unique = false;
+
+ if (unique)
+ {
+ solutions.push_back(digits);
+
+ int sum = EulerUtility::factorial(digits.size()) / EulerUtility::factorial(digits.size() - std::set<int>(digits.begin(), digits.end()).size() + 1);
+
+ int zeroCount = std::count(digits.begin(), digits.end(), 0);
+
+ if (zeroCount > 0)
+ sum = ((sum / digits.size()) * (digits.size() - 1)) / EulerUtility::factorial(zeroCount);
+
+ total += sum;
+ }
+ }
+ }
+ }
+
+ return total;
+}+
\ No newline at end of file
diff --git a/Euler_75.cpp b/Euler_75.cpp
@@ -0,0 +1,39 @@
+#include <algorithm>
+
+#include "Euler.h"
+
+int Euler::UniquePerimeterRightAngledTriangles()
+{
+ int ceiling = 1500000;
+ double sqrtCeiling = sqrt(ceiling);
+ std::vector<int> perimeters(ceiling + 1, 0);
+
+ for (llui m = 2; m <= sqrtCeiling; ++m)
+ {
+ for (llui n = 1; n < m; ++n)
+ {
+ if (((m - n) & 1) && (EulerUtility::gcd(m,n) == 1))
+ {
+ llui m2 = pow(m, 2);
+ llui n2 = pow(n, 2);
+
+ if (m2 + n2 >= ceiling)
+ {
+ continue;
+ }
+
+ llui perimeter = (m2 - n2) + (2 * m * n) + (m2 + n2);
+
+ int k = 1;
+
+ while (perimeter * k <= ceiling)
+ {
+ ++perimeters[perimeter * k];
+ ++k;
+ }
+ }
+ }
+ }
+
+ return std::count(perimeters.begin(), perimeters.end(), 1);
+}+
\ No newline at end of file
diff --git a/Euler_76.cpp b/Euler_76.cpp
@@ -0,0 +1,44 @@
+#include "Euler.h"
+
+ll partition(int n, std::vector<int> &cache)
+{
+ ll p = 0;
+
+ if(n >= 0)
+ {
+ if(n == 0 || n == 1)
+ {
+ return 1;
+ }
+ if(cache[n - 1] != 0)
+ {
+ return cache[n - 1];
+ }
+
+ int k = 1;
+
+ ll s1 = 0;
+ ll s2 = 0;
+
+ while (n - s2 >= 0)
+ {
+ s1 = (k * (3 * k - 1)) / 2;
+ s2 = (k * (3 * k + 1)) / 2;
+
+ int sign = (k - 1) & 1 ? -1 : 1;
+
+ p += sign * partition(n - s1, cache);
+ p += sign * partition(n - s2, cache);
+ ++k;
+ }
+
+ cache[n - 1] = p;
+ }
+
+ return p;
+}
+
+int Euler::CountingSums()
+{
+ return partition(100, std::vector<int>(100, 0)) - 1;
+}+
\ No newline at end of file
diff --git a/Euler_77.cpp b/Euler_77.cpp
@@ -0,0 +1,34 @@
+#include "Euler.h"
+
+int primeSumRecurse(int n, int max, std::vector<int> &primes)
+{
+ int sum = 0;
+
+ for(int i = max; i < primes.size(); i++)
+ {
+ if (n - primes[i] == 0)
+ ++sum;
+ if (n - primes[i] > 0)
+ sum += primeSumRecurse(n - primes[i], i, primes);
+ }
+
+ return sum;
+}
+
+int Euler::PrimeSummations()
+{
+ int ceiling = 1000;
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(ceiling);
+ std::reverse(primes.begin(), primes.end());
+
+ int n = 0;
+ int i = -1;
+
+ while (n <= 5000)
+ {
+ ++i;
+ n = primeSumRecurse(i, 0, primes);
+ }
+
+ return i;
+}+
\ No newline at end of file
diff --git a/Euler_78.cpp b/Euler_78.cpp
@@ -0,0 +1,60 @@
+#include "Euler.h"
+
+BigInteger partition(BigInteger &n, std::vector<BigInteger> &cache)
+{
+ BigInteger p = 0;
+
+ if (n >= 0)
+ {
+ if (n == 0 || n == 1)
+ {
+ return 1;
+ }
+ if (cache[n.toInt() - 1] != 0)
+ {
+ return cache[n.toInt() - 1];
+ }
+
+ int k = 1;
+
+ BigInteger s1 = 0;
+ BigInteger s2 = 0;
+
+ while (n - s2 >= 0)
+ {
+ s1 = (k * (3 * k - 1)) / 2;
+ s2 = (k * (3 * k + 1)) / 2;
+
+ BigInteger sign = (k - 1) & 1 ? -1 : 1;
+
+ p += sign * partition(n - s1, cache);
+ p += sign * partition(n - s2, cache);
+ ++k;
+ }
+
+ cache[n.toInt() - 1] = p;
+ }
+
+ return p;
+}
+
+llui Euler::CoinPartitions()
+{
+ int ceiling = 100000;
+ std::vector<BigInteger> cache(ceiling, 0);
+
+ for (int i = 1; i < ceiling; ++i)
+ {
+ if ((i - 4) % 5 == 0)
+ {
+ BigInteger n = partition(BigInteger(i), cache);
+
+ if (n % 1000000 == 0)
+ {
+ return i;
+ }
+ }
+ }
+
+ return 0;
+}+
\ No newline at end of file
diff --git a/Euler_79.cpp b/Euler_79.cpp
@@ -0,0 +1,41 @@
+#include <fstream>
+#include <set>
+
+#include "Euler.h"
+
+std::string Euler::PasscodeDerivation()
+{
+ std::ifstream fin;
+ std::vector<std::string> numbers;
+
+ fin.open("E:\\Euler Resources\\Euler 79.txt");
+
+ std::string temp;
+ while(std::getline(fin, temp))
+ numbers.push_back(temp);
+
+ fin.close();
+
+ std::set<char> tokens;
+
+ for (std::string n : numbers)
+ for (char c : n)
+ tokens.insert(c);
+
+ std::string passcode(tokens.begin(),tokens.end());
+
+ for (std::string n : numbers)
+ {
+ int i = std::find(passcode.begin(), passcode.end(), n[0]) - passcode.begin();
+ int j = std::find(passcode.begin(), passcode.end(), n[1]) - passcode.begin();
+ int k = std::find(passcode.begin(), passcode.end(), n[2]) - passcode.begin();
+
+ if (i > j)
+ std::swap(passcode[i], passcode[j]);
+
+ if (j > k)
+ std::swap(passcode[j], passcode[k]);
+ }
+
+ return passcode;
+}+
\ No newline at end of file
diff --git a/Euler_8.cpp b/Euler_8.cpp
@@ -0,0 +1,33 @@
+#include <fstream>
+
+#include "Euler.h"
+
+llui Euler::FindGreatestProductOf13AdjacentDigits()
+{
+ std::ifstream fin;
+ fin.open("E:\\Euler Resources\\Euler 8.txt");
+
+ std::string number;
+
+ std::getline(fin, number);
+
+ fin.close();
+
+ llui greatestProduct = 0;
+
+ for (unsigned i = 0; i < number.length() - 13; ++i)
+ {
+ std::vector<int> digits;
+
+ llui temp = 1;
+
+ for (unsigned j = i; j < i + 13; ++j)
+ temp *= (number.at(j) - 48);
+
+ if (temp > greatestProduct) {
+ greatestProduct = temp;
+ }
+ }
+
+ return greatestProduct;
+}+
\ No newline at end of file
diff --git a/Euler_80.cpp b/Euler_80.cpp
@@ -0,0 +1,30 @@
+#include <boost/multiprecision/cpp_dec_float.hpp>
+
+#include "Euler.h"
+
+namespace mp = boost::multiprecision;
+
+typedef mp::number<mp::cpp_dec_float<120>> cpp_dec_float_120;
+
+int Euler::SquareRootDigitalExpansion()
+{
+ int total = 0;
+
+ for (cpp_dec_float_120 i = 1; i <= 100; ++i)
+ {
+ std::stringstream buffer;
+ buffer << std::setprecision(std::numeric_limits<cpp_dec_float_120>::digits) << mp::sqrt(i);
+
+ std::string irrational = buffer.str();
+
+ if (irrational.size() > 2)
+ {
+ total += irrational[0] - '0';
+
+ for (int i = 2; i < 101; ++i)
+ total += irrational[i] - '0';
+ }
+ }
+
+ return total;
+}+
\ No newline at end of file
diff --git a/Euler_9.cpp b/Euler_9.cpp
@@ -0,0 +1,17 @@
+#include <sstream>
+
+#include "Euler.h"
+
+int Euler::SpecialPythagoreanTriplet()
+{
+ for (int a = 1; a < 1000; ++a)
+ for (int b = 1; b < 1000; ++b)
+ {
+ double c = sqrt(a * a + b * b);
+
+ if ((a + b + c) == 1000)
+ return a * b * (int)c;
+ }
+
+ return 0;
+}+
\ No newline at end of file
diff --git a/README.md b/README.md
@@ -0,0 +1 @@
+# ProjectEuler
diff --git a/main.cpp b/main.cpp
@@ -0,0 +1,93 @@
+#include <iostream>
+#include <ctime>
+
+#include "Euler.h"
+
+void main() {
+ Euler e;
+ std::clock_t start = std::clock();
+
+ //std::cout << e.SumOfMultiplesOf3And5Ceiling1000() << std::endl;
+ //std::cout << e.SumOfEvenFibonacciNumbersCeiling4m() << std::endl;
+ //std::cout << e.LargestPrimeFactor() << std::endl;
+ //std::cout << e.LargestPalindromeFrom3DigitProduct() << std::endl;
+ //std::cout << e.DivisibleBy1To20() << std::endl;
+ //std::cout << e.DifferenceSumOfSquaresSquareOfSum100() << std::endl;
+ //std::cout << e.Get10001stPrime() << std::endl;
+ //std::cout << e.FindGreatestProductOf13AdjacentDigits() << std::endl;
+ //std::cout << e.SpecialPythagoreanTriplet() << std::endl;
+ //std::cout << e.SumOfPrimesUnder2m() << std::endl;
+ //std::cout << e.LargestProductInGrid() << std::endl;
+ //std::cout << e.TriangleNoWithGreaterThan500Divisors() << std::endl;
+ //std::cout << e.LargeSum() << std::endl;
+ //std::cout << e.CollatzConjecture() << std::endl;
+ //std::cout << e.LatticePaths() << std::endl;
+ //std::cout << e.DigitSum() << std::endl;
+ //std::cout << e.LetterCounter() << std::endl;
+ //std::cout << e.MaximumPathSum() << std::endl;
+ //std::cout << e.SundayCount() << std::endl;
+ //std::cout << e.FactorialDigitSum() << std::endl;
+ //std::cout << e.AmicableNumbers() << std::endl;
+ //std::cout << e.NameScores() << std::endl;
+ //std::cout << e.NonAbundantSums() << std::endl;
+ //std::cout << e.LexicographicPermutations() << std::endl;
+ //std::cout << e.ThousandDigitFibonacciNumber() << std::endl;
+ //std::cout << e.ReciprocalCycles() << std::endl;
+ //std::cout << e.QuadraticPrimes() << std::endl;
+ //std::cout << e.SpiralDiagonals() << std::endl;
+ //std::cout << e.DistinctPowers() << std::endl;
+ //std::cout << e.DigitFifthPowers() << std::endl;
+ //std::cout << e.CoinSums() << std::endl;
+ //std::cout << e.PanDigitalProducts() << std::endl;
+ //std::cout << e.DigitCancellingFractionsDenominator() << std::endl;
+ //std::cout << e.DigitFactorials() << std::endl;
+ //std::cout << e.NoOfCircularPrimes() << std::endl;
+ //std::cout << e.DoubleBasedPalindromes() << std::endl;
+ //std::cout << e.TruncatablePrimes() << std::endl;
+ //std::cout << e.PanDigitalMultiples() << std::endl;
+ //std::cout << e.MaximumRightAngledTriangles() << std::endl;
+ //std::cout << e.ChampernowneConstant() << std::endl;
+ //std::cout << e.PanDigitalPrime() << std::endl;
+ //std::cout << e.CodedTriangleNumbers() << std::endl;
+ //std::cout << e.SubStringDivisibility() << std::endl;
+ //std::cout << e.MinimizedPentagonalDifference() << std::endl;
+ //std::cout << e.TriangularPentagonalHexagonal() << std::endl;
+ //std::cout << e.GoldbachsOtherConjecture() << std::endl;
+ //std::cout << e.DistinctPrimeFactors() << std::endl;
+ //std::cout << e.SelfPowers() << std::endl;
+ //std::cout << e.PrimePermutations() << std::endl;
+ //std::cout << e.ConsecutivePrimeSum() << std::endl;
+ //std::cout << e.PrimeDigitReplacements() << std::endl;
+ //std::cout << e.PermutedMultiples() << std::endl;
+ //std::cout << e.CombinatoricSelections() << std::endl;
+ //std::cout << e.PokerHands() << std::endl;
+ //std::cout << e.LychrelNumbers() << std::endl;
+ //std::cout << e.PowerfulDigitSum() << std::endl;
+ //std::cout << e.SquareRootConvergents() << std::endl;
+ //std::cout << e.SpiralPrimes() << std::endl;
+ //std::cout << e.xorDecryption() << std::endl;
+ //std::cout << e.PrimePairSets() << std::endl;
+ //std::cout << e.CyclicFigurateNumbers() << std::endl;
+ //std::cout << e.CubicPermutations() << std::endl;
+ //std::cout << e.PowerfulDigitCounts() << std::endl;
+ //std::cout << e.OddPeriodSquareRoots() << std::endl;
+ //std::cout << e.ConvergentsOfE() << std::endl;
+ //std::cout << e.Diophantine() << std::endl;
+ //std::cout << e.Magic5GonRing() << std::endl;
+ //std::cout << e.EulerTotient() << std::endl;
+ //std::cout << e.TotientPermutation() << std::endl;
+ //std::cout << e.OrderedFractions() << std::endl;
+ //std::cout << e.CountingFractions() << std::endl;
+ //std::cout << e.CountingRangedFractions() << std::endl;
+ //std::cout << e.DigitFactorialChains() << std::endl;
+ //std::cout << e.UniquePerimeterRightAngledTriangles() << std::endl;
+ //std::cout << e.CountingSums() << std::endl;
+ //std::cout << e.PrimeSummations() << std::endl;
+ //std::cout << e.CoinPartitions() << std::endl;
+ //std::cout << e.PasscodeDerivation() << std::endl;
+ std::cout << e.SquareRootDigitalExpansion() << std::endl;
+
+ std::cout << "duration: " << std::clock() - start << "ms" << std::endl;
+
+ std::cin.get();
+}+
\ No newline at end of file
