commit b65c7e90e8a9657873a9c281e541449a609afbb8
parent ed6c70872922bdec41b371723931b5b64772be6a
Author: mpizzzle <m@michaelpercival.xyz>
Date: Mon, 21 Sep 2020 14:59:38 +0100
substituting tabs for spaces
Diffstat:
| M | Euler.h | | | 158 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | EulerUtility.cpp | | | 522 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | EulerUtility.h | | | 64 | ++++++++++++++++++++++++++++++++-------------------------------- |
| M | Euler_1.cpp | | | 12 | ++++++------ |
| M | Euler_10.cpp | | | 26 | +++++++++++++------------- |
| M | Euler_11.cpp | | | 98 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | Euler_12.cpp | | | 84 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | Euler_13.cpp | | | 108 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | Euler_14.cpp | | | 58 | +++++++++++++++++++++++++++++----------------------------- |
| M | Euler_15.cpp | | | 2 | +- |
| M | Euler_16.cpp | | | 46 | +++++++++++++++++++++++----------------------- |
| M | Euler_17.cpp | | | 26 | +++++++++++++------------- |
| M | Euler_18.cpp | | | 28 | ++++++++++++++-------------- |
| M | Euler_19.cpp | | | 34 | +++++++++++++++++----------------- |
| M | Euler_2.cpp | | | 20 | ++++++++++---------- |
| M | Euler_20.cpp | | | 4 | ++-- |
| M | Euler_21.cpp | | | 16 | ++++++++-------- |
| M | Euler_22.cpp | | | 22 | +++++++++++----------- |
| M | Euler_23.cpp | | | 26 | +++++++++++++------------- |
| M | Euler_24.cpp | | | 8 | ++++---- |
| M | Euler_25.cpp | | | 64 | ++++++++++++++++++++++++++++++++-------------------------------- |
| M | Euler_26.cpp | | | 34 | +++++++++++++++++----------------- |
| M | Euler_27.cpp | | | 8 | ++++---- |
| M | Euler_28.cpp | | | 8 | ++++---- |
| M | Euler_29.cpp | | | 110 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | Euler_3.cpp | | | 56 | ++++++++++++++++++++++++++++---------------------------- |
| M | Euler_30.cpp | | | 22 | +++++++++++----------- |
| M | Euler_31.cpp | | | 28 | ++++++++++++++-------------- |
| M | Euler_32.cpp | | | 48 | ++++++++++++++++++++++++------------------------ |
| M | Euler_33.cpp | | | 84 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | Euler_34.cpp | | | 24 | ++++++++++++------------ |
| M | Euler_35.cpp | | | 74 | +++++++++++++++++++++++++++++++++++++------------------------------------- |
| M | Euler_36.cpp | | | 34 | +++++++++++++++++----------------- |
| M | Euler_37.cpp | | | 28 | ++++++++++++++-------------- |
| M | Euler_38.cpp | | | 28 | ++++++++++++++-------------- |
| M | Euler_39.cpp | | | 34 | +++++++++++++++++----------------- |
| M | Euler_4.cpp | | | 46 | +++++++++++++++++++++++----------------------- |
| M | Euler_40.cpp | | | 22 | +++++++++++----------- |
| M | Euler_41.cpp | | | 22 | +++++++++++----------- |
| M | Euler_42.cpp | | | 22 | +++++++++++----------- |
| M | Euler_43.cpp | | | 62 | +++++++++++++++++++++++++++++++------------------------------- |
| M | Euler_44.cpp | | | 22 | +++++++++++----------- |
| M | Euler_45.cpp | | | 16 | ++++++++-------- |
| M | Euler_46.cpp | | | 44 | ++++++++++++++++++++++---------------------- |
| M | Euler_47.cpp | | | 50 | +++++++++++++++++++++++++------------------------- |
| M | Euler_48.cpp | | | 8 | ++++---- |
| M | Euler_49.cpp | | | 70 | +++++++++++++++++++++++++++++++++++----------------------------------- |
| M | Euler_5.cpp | | | 54 | +++++++++++++++++++++++++++--------------------------- |
| M | Euler_50.cpp | | | 96 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | Euler_51.cpp | | | 90 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | Euler_52.cpp | | | 26 | +++++++++++++------------- |
| M | Euler_53.cpp | | | 12 | ++++++------ |
| M | Euler_54.cpp | | | 358 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | Euler_55.cpp | | | 58 | +++++++++++++++++++++++++++++----------------------------- |
| M | Euler_56.cpp | | | 24 | ++++++++++++------------ |
| M | Euler_57.cpp | | | 22 | +++++++++++----------- |
| M | Euler_58.cpp | | | 38 | +++++++++++++++++++------------------- |
| M | Euler_59.cpp | | | 48 | ++++++++++++++++++++++++------------------------ |
| M | Euler_6.cpp | | | 16 | ++++++++-------- |
| M | Euler_60.cpp | | | 94 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | Euler_61.cpp | | | 104 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | Euler_62.cpp | | | 64 | ++++++++++++++++++++++++++++++++-------------------------------- |
| M | Euler_63.cpp | | | 32 | ++++++++++++++++---------------- |
| M | Euler_64.cpp | | | 106 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | Euler_65.cpp | | | 66 | +++++++++++++++++++++++++++++++++--------------------------------- |
| M | Euler_66.cpp | | | 86 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | Euler_68.cpp | | | 124 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | Euler_69.cpp | | | 26 | +++++++++++++------------- |
| M | Euler_7.cpp | | | 34 | +++++++++++++++++----------------- |
| M | Euler_70.cpp | | | 28 | ++++++++++++++-------------- |
| M | Euler_71.cpp | | | 56 | ++++++++++++++++++++++++++++---------------------------- |
| M | Euler_72.cpp | | | 18 | +++++++++--------- |
| M | Euler_73.cpp | | | 54 | +++++++++++++++++++++++++++--------------------------- |
| M | Euler_74.cpp | | | 164 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | Euler_75.cpp | | | 64 | ++++++++++++++++++++++++++++++++-------------------------------- |
| M | Euler_76.cpp | | | 54 | +++++++++++++++++++++++++++--------------------------- |
| M | Euler_77.cpp | | | 26 | +++++++++++++------------- |
| M | Euler_78.cpp | | | 86 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | Euler_79.cpp | | | 48 | ++++++++++++++++++++++++------------------------ |
| M | Euler_8.cpp | | | 34 | +++++++++++++++++----------------- |
| M | Euler_80.cpp | | | 28 | ++++++++++++++-------------- |
| M | Euler_9.cpp | | | 16 | ++++++++-------- |
| M | Euler_97.py | | | 30 | +++++++++++++++--------------- |
| M | Euler_99.py | | | 14 | +++++++------- |
| M | Makefile | | | 42 | ++++++++++++++++++++---------------------- |
85 files changed, 2384 insertions(+), 2386 deletions(-)
diff --git a/Euler.h b/Euler.h
@@ -3,83 +3,83 @@
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();
+ 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
@@ -13,189 +13,189 @@ int EulerUtility::multiply(int x, int y)
int EulerUtility::sumOfDivisors(int n)
{
- int prod = 1;
+ int prod = 1;
- for(int k = 2; k * k <= n; ++k)
- {
- int p = 1;
+ for(int k = 2; k * k <= n; ++k)
+ {
+ int p = 1;
- while(n % k == 0)
- {
- p = p * k + 1;
- n /= k;
- }
+ while(n % k == 0)
+ {
+ p = p * k + 1;
+ n /= k;
+ }
- prod *= p;
- }
+ prod *= p;
+ }
- if(n > 1)
- prod *= 1 + n;
+ if(n > 1)
+ prod *= 1 + n;
- return prod;
+ return prod;
}
std::vector<int> EulerUtility::getPrimesUnderCeiling(int ceiling)
{
- std::vector<int> primes;
+ std::vector<int> primes;
- primes.push_back(2);
- primes.push_back(3);
+ primes.push_back(2);
+ primes.push_back(3);
- bool is_prime;
+ bool is_prime;
- for(int i = 5; i < ceiling; i += 2)
- {
- is_prime = true;
+ 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;
+ 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);
- }
+ if(is_prime)
+ primes.push_back(i);
+ }
- return primes;
+ return primes;
}
std::vector<int> EulerUtility::getPrimesUnderCeilingIndexed(int ceiling)
{
- std::vector<int> primes;
+ std::vector<int> primes;
- primes.push_back(-1);
- primes.push_back(-1);
- primes.push_back(2);
- primes.push_back(3);
- primes.push_back(-1);
+ primes.push_back(-1);
+ primes.push_back(-1);
+ primes.push_back(2);
+ primes.push_back(3);
+ primes.push_back(-1);
- bool is_prime;
+ bool is_prime;
- for(int i = 5; i < ceiling; i += 2)
- {
- is_prime = true;
+ 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;
+ 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);
- }
- }
+ if(is_prime)
+ {
+ primes.push_back(i);
+ primes.push_back(-1);
+ }
+ else
+ {
+ primes.push_back(-1);
+ primes.push_back(-1);
+ }
+ }
- return primes;
+ 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())));
+ 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;
+ 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));
+ std::istringstream split(s);
+ std::vector<std::string> tokens;
+ for (std::string each; std::getline(split, each, delim); tokens.push_back(each));
- return tokens;
+ 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> 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;
+ 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);
+ 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);
+ 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));
+ return EulerUtility::bigFactorial(n) / (EulerUtility::bigFactorial(k) * EulerUtility::bigFactorial(n - k));
}
bool EulerUtility::isPerfectSquare(llui n)
{
- if (n < 0)
- return false;
+ if (n < 0)
+ return false;
- llui tst = (llui)(sqrt(n) + 0.5);
- return tst*tst == n;
+ llui tst = (llui)(sqrt(n) + 0.5);
+ return tst*tst == n;
}
bool EulerUtility::isPerfectCube(llui n)
{
- if (n < 0)
- return false;
+ if (n < 0)
+ return false;
llui tst = (llui)std::floor(std::pow(n, 1/3.) + 0.5);
return n == tst * tst * tst;
@@ -203,90 +203,90 @@ bool EulerUtility::isPerfectCube(llui n)
std::vector<int> EulerUtility::intToDigits(int n)
{
- std::vector<int> digitArray;
+ std::vector<int> digitArray;
- while (n != 0)
- {
- digitArray.push_back(n % 10);
- n /= 10;
- }
+ while (n != 0)
+ {
+ digitArray.push_back(n % 10);
+ n /= 10;
+ }
- std::reverse(digitArray.begin(), digitArray.end());
+ std::reverse(digitArray.begin(), digitArray.end());
- return digitArray;
+ return digitArray;
}
std::vector<int> EulerUtility::lluiToDigits(llui n)
{
- std::vector<int> digitArray;
+ std::vector<int> digitArray;
- while (n != 0)
- {
- digitArray.push_back(n % 10);
- n /= 10;
- }
+ while (n != 0)
+ {
+ digitArray.push_back(n % 10);
+ n /= 10;
+ }
- std::reverse(digitArray.begin(), digitArray.end());
+ std::reverse(digitArray.begin(), digitArray.end());
- return digitArray;
+ return digitArray;
}
std::vector<int> EulerUtility::BigIntToDigits(BigInteger n)
{
- std::vector<int> digitArray;
+ std::vector<int> digitArray;
- while (n != 0)
- {
- digitArray.push_back((n % 10).toInt());
- n /= 10;
- }
+ while (n != 0)
+ {
+ digitArray.push_back((n % 10).toInt());
+ n /= 10;
+ }
- std::reverse(digitArray.begin(), digitArray.end());
+ std::reverse(digitArray.begin(), digitArray.end());
- return digitArray;
+ return digitArray;
}
int EulerUtility::digitsToInteger(std::vector<int> d)
{
- std::stringstream ss;
+ std::stringstream ss;
- for (int i : d)
- ss << i;
+ for (int i : d)
+ ss << i;
- int integer;
- ss >> integer;
+ int integer;
+ ss >> integer;
- return integer;
+ return integer;
}
llui EulerUtility::digitsTollui(std::string s)
{
- std::stringstream ss;
+ std::stringstream ss;
- for (char c : s)
- ss << c;
+ for (char c : s)
+ ss << c;
- llui digits;
- ss >> digits;
+ llui digits;
+ ss >> digits;
- return digits;
+ return digits;
}
bool EulerUtility::hasUniqueDigits(int n, bool allowZero)
{
- std::vector<int> digits = EulerUtility::intToDigits(n);
+ std::vector<int> digits = EulerUtility::intToDigits(n);
- std::unordered_set<int> uniqueDigits;
+ std::unordered_set<int> uniqueDigits;
- for (int digit : digits)
- {
- if (digit == 0 && !allowZero)
- return false;
+ for (int digit : digits)
+ {
+ if (digit == 0 && !allowZero)
+ return false;
- uniqueDigits.insert(digit);
- }
+ uniqueDigits.insert(digit);
+ }
- return digits.size() == uniqueDigits.size();
+ return digits.size() == uniqueDigits.size();
}
/*
@@ -294,17 +294,17 @@ bool EulerUtility::hasUniqueDigits(int n, bool allowZero)
*/
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;
+ ll x = 0,y = a % mod;
+ while (b > 0)
+ {
+ if (b % 2 == 1)
+ x = (x + y) % mod;
- y = (y * 2) % mod;
- b /= 2;
- }
+ y = (y * 2) % mod;
+ b /= 2;
+ }
- return x % mod;
+ return x % mod;
}
/*
@@ -312,19 +312,19 @@ ll mulmod(ll a, ll b, ll mod)
*/
ll modulo(ll base, ll exponent, ll mod)
{
- ll x = 1;
- ll y = base;
+ ll x = 1;
+ ll y = base;
- while (exponent > 0)
- {
- if (exponent % 2 == 1)
- x = (x * y) % mod;
+ while (exponent > 0)
+ {
+ if (exponent % 2 == 1)
+ x = (x * y) % mod;
- y = (y * y) % mod;
- exponent = exponent / 2;
- }
+ y = (y * y) % mod;
+ exponent = exponent / 2;
+ }
- return x % mod;
+ return x % mod;
}
/*
@@ -332,45 +332,45 @@ ll modulo(ll base, ll exponent, ll mod)
*/
bool EulerUtility::isPrime(ll p, int iteration)
{
- if ((p < 2) || (p != 2 && p % 2 == 0))
- return false;
+ if ((p < 2) || (p != 2 && p % 2 == 0))
+ return false;
- ll s = p - 1;
+ ll s = p - 1;
- while (s % 2 == 0)
- s /= 2;
+ 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);
+ 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;
- }
+ 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;
- }
+ if (mod != p - 1 && temp % 2 == 0)
+ return false;
+ }
- return true;
+ return true;
}
bool EulerUtility::isTriangle(int n)
{
- return std::floor(sqrt(2 * n + 0.25) - 0.5) == sqrt(2 * n + 0.25) - 0.5;
+ 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;
+ 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::ifstream file;
std::vector<std::string> names;
std::string name;
file.open(filename);
@@ -378,104 +378,104 @@ std::vector<std::string> EulerUtility::openWordFile(std::string filename)
while(getline(file, name, ','))
names.push_back(name.substr(1, name.size() - 2));
- return names;
+ return names;
}
BigInteger EulerUtility::power(BigInteger i, int p)
{
- if (p <= 0)
- return 1;
+ if (p <= 0)
+ return 1;
- return i * power(i, p - 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);
+ std::vector<int> digits = intToDigits(n);
+ int digitSum = std::accumulate(digits.begin(), digits.end(), 0);
- if (digitSum > 9)
- return digitalRoot(digitSum);
+ if (digitSum > 9)
+ return digitalRoot(digitSum);
- return digitSum;
+ return digitSum;
}
int EulerUtility::digitalRoot(BigInteger n)
{
- std::vector<int> digits = BigIntToDigits(n);
- int digitSum = std::accumulate(digits.begin(), digits.end(), 0);
+ std::vector<int> digits = BigIntToDigits(n);
+ int digitSum = std::accumulate(digits.begin(), digits.end(), 0);
- if (digitSum > 9)
- return digitalRoot(digitSum);
+ if (digitSum > 9)
+ return digitalRoot(digitSum);
- return 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> 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;
+ std::vector<int> figurates;
- if (sides < 3)
- return 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));
+ 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 >= floor && figurate < ceiling)
+ figurates.push_back(figurate);
- if (figurate > ceiling)
- return figurates;
- }
+ if (figurate > ceiling)
+ return figurates;
+ }
- 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);
- }
+ // 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
@@ -9,36 +9,36 @@ 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);
+ 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
@@ -2,12 +2,12 @@
int Euler::SumOfMultiplesOf3And5Ceiling1000()
{
- int sumOfMultiples = 0;
+ int sumOfMultiples = 0;
- for (int i = 0; i < 1000; ++i) {
- if ((i % 3 == 0) || (i % 5 == 0))
- sumOfMultiples += i;
- }
+ for (int i = 0; i < 1000; ++i) {
+ if ((i % 3 == 0) || (i % 5 == 0))
+ sumOfMultiples += i;
+ }
- return sumOfMultiples;
+ return sumOfMultiples;
}
No newline at end of file
diff --git a/Euler_10.cpp b/Euler_10.cpp
@@ -2,23 +2,23 @@
llui Euler::SumOfPrimesUnder2m()
{
- int noOfPrimes = 0;
+ int noOfPrimes = 0;
- bool is_prime;
+ bool is_prime;
- llui count = 2; //includes 2 & 3
+ llui count = 2; //includes 2 & 3
- for(int i = 3; i < 2000000; i += 2)
- {
- is_prime = true;
+ 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;
+ for(int j = 3; j * j <= i && is_prime; j += 2)
+ if(i % j == 0) is_prime = false;
- if(is_prime) {
- count += i;
- }
- }
+ if(is_prime) {
+ count += i;
+ }
+ }
- return count;
+ return count;
}
No newline at end of file
diff --git a/Euler_11.cpp b/Euler_11.cpp
@@ -4,74 +4,74 @@
void SumDigits(std::vector<int> &digits, int &greatestProduct)
{
- int temp = digits[0];
+ int temp = digits[0];
- for(unsigned int j = 1; j < digits.size(); ++j)
- temp *= digits[j];
+ for(unsigned int j = 1; j < digits.size(); ++j)
+ temp *= digits[j];
- if (temp > greatestProduct)
- greatestProduct = temp;
+ 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::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, ' ');
+ std::vector<int> numGrid = EulerUtility::tokenizer(grid, ' ');
- int greatestProduct = 0;
+ int greatestProduct = 0;
- for (int i = 0; i < 20; ++i) {
- for (int j = 0; j <= 20 - 4; ++j)
- {
- std::vector<int> digits;
+ 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]);
+ for (int k = 0; k < 4; ++k)
+ digits.push_back(numGrid[i * 20 + j + k]);
- SumDigits(digits, greatestProduct);
- }
- }
+ SumDigits(digits, greatestProduct);
+ }
+ }
- for (int i = 0; i <= 20 - 4; ++i){
- for (int j = 0; j < 20; ++j)
- {
- std::vector<int> digits;
+ 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]);
+ for (int k = 0; k < 4; ++k)
+ digits.push_back(numGrid[i + j * 20 + k]);
- SumDigits(digits, greatestProduct);
- }
- }
+ 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 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]);
+ for (int k = 0; k < 4; ++k)
+ digits.push_back(numGrid[(i + k) * 20 + j + k]);
- SumDigits(digits, greatestProduct);
- }
- }
+ SumDigits(digits, greatestProduct);
+ }
+ }
- for (int i = 0; i < 20 - 4; ++i) {
- for (int j = 19; j >= 3; --j)
- {
- std::vector<int> digits;
+ 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]);
+ for (int k = 0; k < 4; ++k)
+ digits.push_back(numGrid[(i + k) * 20 + j - k]);
- SumDigits(digits, greatestProduct);
- }
- }
+ SumDigits(digits, greatestProduct);
+ }
+ }
- return greatestProduct;
+ return greatestProduct;
}
No newline at end of file
diff --git a/Euler_12.cpp b/Euler_12.cpp
@@ -2,53 +2,53 @@
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;
+ 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;
+ llui currentTriangle = 1;
- std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(100000);
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(100000);
- for (int i = 2; getNumberOfDivisorsFromPrimeFactors(currentTriangle, primes) <= 500; ++i)
- currentTriangle += i;
+ for (int i = 2; getNumberOfDivisorsFromPrimeFactors(currentTriangle, primes) <= 500; ++i)
+ currentTriangle += i;
- return currentTriangle;
+ return currentTriangle;
}
No newline at end of file
diff --git a/Euler_13.cpp b/Euler_13.cpp
@@ -5,84 +5,84 @@
std::vector<int> getIndividualDigits(int number)
{
- std::vector<int> digits;
+ std::vector<int> digits;
- std::string s = std::to_string(number);
+ 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()));
+ for (int i = s.length() - 1; i >= 0 ; --i)
+ digits.push_back(atoi(s.substr(i, 1).c_str()));
- return digits;
+ return digits;
}
std::string getSum(std::vector<int> digits)
{
- std::string s;
+ std::string s;
- for (int i = digits.size() - 1; i >= 0; --i)
- {
- s += std::to_string(digits[i]);
- }
+ for (int i = digits.size() - 1; i >= 0; --i)
+ {
+ s += std::to_string(digits[i]);
+ }
- return s;
+ return s;
}
std::string Euler::LargeSum() {
- std::ifstream fin;
- std::vector<std::string> numbers;
+ std::ifstream fin;
+ std::vector<std::string> numbers;
- fin.open("E:\Euler Resources\Euler 13.txt");
+ fin.open("E:\Euler Resources\Euler 13.txt");
- std::string temp;
- while(std::getline(fin, temp))
- numbers.push_back(temp);
+ std::string temp;
+ while(std::getline(fin, temp))
+ numbers.push_back(temp);
- fin.close();
+ fin.close();
- std::vector<int> sumDigits;
+ std::vector<int> sumDigits;
- for (int i = numbers[0].size() - 1; i >= 0; --i)
- {
- int exp = 0;
+ 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);
+ for (unsigned j = 0; j < numbers.size(); ++j)
+ {
+ std::stringstream strValue;
+ strValue << numbers[j].at(i);
- unsigned int sumDigit;
- strValue >> sumDigit;
+ unsigned int sumDigit;
+ strValue >> sumDigit;
- exp += sumDigit;
- }
+ exp += sumDigit;
+ }
- sumDigits.push_back(exp);
- }
+ sumDigits.push_back(exp);
+ }
- std::vector<int> digits = getIndividualDigits(sumDigits[0]);
+ std::vector<int> digits = getIndividualDigits(sumDigits[0]);
- for (unsigned i = 1; i < sumDigits.size(); ++i)
- {
- std::vector<int> temp = getIndividualDigits(sumDigits[i]);
+ 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]);
- }
+ 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;
- }
- }
+ 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);
+ return getSum(digits).substr(0, 10);
}
No newline at end of file
diff --git a/Euler_14.cpp b/Euler_14.cpp
@@ -2,40 +2,40 @@
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;
+ 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;
+ int longestChain = 0;
+ int idx = 0;
- for (int i = 0; i < 1000000; ++i)
- {
- int length = lengthOfChain(i);
+ for (int i = 0; i < 1000000; ++i)
+ {
+ int length = lengthOfChain(i);
- if (length > longestChain)
- {
- longestChain = length;
- idx = i;
- }
- }
+ if (length > longestChain)
+ {
+ longestChain = length;
+ idx = i;
+ }
+ }
- return idx;
+ return idx;
}
No newline at end of file
diff --git a/Euler_15.cpp b/Euler_15.cpp
@@ -2,5 +2,5 @@
BigInteger Euler::LatticePaths()
{
- return EulerUtility::choose(40,20);
+ return EulerUtility::choose(40,20);
}
No newline at end of file
diff --git a/Euler_16.cpp b/Euler_16.cpp
@@ -4,32 +4,32 @@
int Euler::DigitSum()
{
- std::vector<int> digits;
+ std::vector<int> digits;
- digits.push_back(2);
+ digits.push_back(2);
- for (int i = 1; i < 1000; ++i)
- {
- for (unsigned j = 0; j < digits.size(); ++j)
- digits[j] *=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;
+ 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;
- }
- }
- }
- }
+ if (j == digits.size() - 1)
+ {
+ digits.push_back(1);
+ }
+ else
+ {
+ digits[j + 1] += 1;
+ }
+ }
+ }
+ }
- return std::accumulate(digits.begin(), digits.end(), 0);
+ return std::accumulate(digits.begin(), digits.end(), 0);
}
No newline at end of file
diff --git a/Euler_17.cpp b/Euler_17.cpp
@@ -2,36 +2,36 @@
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;
+ 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;
+ return (j == 1) ? ((k == 0) ? ten : 0) : ten;
}
int and(int count)
{
- return ((count >= 100) && (count % 100 != 0)) ? std::string("and").length() : 0;
+ 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
+ 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"};
+ 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
+ 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);
+ 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;
+ return sum;
}
No newline at end of file
diff --git a/Euler_18.cpp b/Euler_18.cpp
@@ -4,25 +4,25 @@
int Euler::MaximumPathSum()
{
- std::ifstream fin;
- std::vector<std::string> str_rows;
+ std::ifstream fin;
+ std::vector<std::string> str_rows;
- fin.open("E:\Euler Resources\Euler 67.txt");
+ fin.open("E:\Euler Resources\Euler 67.txt");
- std::string temp;
- while(std::getline(fin, temp))
- str_rows.push_back(temp);
+ std::string temp;
+ while(std::getline(fin, temp))
+ str_rows.push_back(temp);
- fin.close();
+ fin.close();
- std::vector<std::vector<int>> rows;
+ std::vector<std::vector<int>> rows;
- for (std::string s :str_rows)
- rows.push_back(EulerUtility::tokenizer(s, ' '));
+ 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];
+ 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];
+ return rows[0][0];
}
No newline at end of file
diff --git a/Euler_19.cpp b/Euler_19.cpp
@@ -2,29 +2,29 @@
int daysInFebruary(int year)
{
- return (year % 4 == 0) ? ((year % 100 == 0) ? ((year % 400 == 0) ? 29 : 28) : 29) : 28;
+ return (year % 4 == 0) ? ((year % 100 == 0) ? ((year % 400 == 0) ? 29 : 28) : 29) : 28;
}
int Euler::SundayCount()
{
- int weekday = 1;
- int sundays = 0;
+ 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 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;
+ for (int month : months)
+ {
+ for (int day = 0; day < month; ++day)
+ {
+ if ((weekday == 0) && (day == 0) && (year > 1900))
+ ++sundays;
- ++weekday %= 7;
- }
- }
- }
+ ++weekday %= 7;
+ }
+ }
+ }
- return sundays;
+ return sundays;
}
No newline at end of file
diff --git a/Euler_2.cpp b/Euler_2.cpp
@@ -2,17 +2,17 @@
int Euler::SumOfEvenFibonacciNumbersCeiling4m()
{
- int sumOfEvenFibNumbers = 0;
+ int sumOfEvenFibNumbers = 0;
- for (int i = 1, j = 2; j < 4000000;)
- {
- if (j % 2 == 0)
- sumOfEvenFibNumbers += j;
+ for (int i = 1, j = 2; j < 4000000;)
+ {
+ if (j % 2 == 0)
+ sumOfEvenFibNumbers += j;
- int temp = j;
- j += i;
- i = temp;
- }
+ int temp = j;
+ j += i;
+ i = temp;
+ }
- return sumOfEvenFibNumbers;
+ return sumOfEvenFibNumbers;
}
No newline at end of file
diff --git a/Euler_20.cpp b/Euler_20.cpp
@@ -4,7 +4,7 @@
llui Euler::FactorialDigitSum()
{
- std::vector<int> digits = EulerUtility::factorialDigits(100);
+ std::vector<int> digits = EulerUtility::factorialDigits(100);
- return std::accumulate(digits.begin(), digits.end(), 0);
+ return std::accumulate(digits.begin(), digits.end(), 0);
}
No newline at end of file
diff --git a/Euler_21.cpp b/Euler_21.cpp
@@ -2,16 +2,16 @@
int Euler::AmicableNumbers()
{
- std::vector<unsigned> sumDivisors(10001, 0);
+ std::vector<unsigned> sumDivisors(10001, 0);
- for(int i = 2; i < 10000; ++i)
- sumDivisors[i] = EulerUtility::sumOfDivisors(i) - i;
+ for(int i = 2; i < 10000; ++i)
+ sumDivisors[i] = EulerUtility::sumOfDivisors(i) - i;
- int sum = 0;
+ 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;
+ for (unsigned i = 0; i < sumDivisors.size(); ++i)
+ if (sumDivisors[i] < sumDivisors.size() && sumDivisors[sumDivisors[i]] == i && sumDivisors[i] != i)
+ sum += i;
- return sum;
+ return sum;
}
No newline at end of file
diff --git a/Euler_22.cpp b/Euler_22.cpp
@@ -4,21 +4,21 @@
llui Euler::NameScores()
{
- std::vector<std::string> names = EulerUtility::openWordFile("E:\Euler Resources\Euler 22.txt");
+ 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;
+ llui sum = 0;
+ int count = 0;
- for (std::string name : names)
- {
- int namesum = 0;
+ for (std::string name : names)
+ {
+ int namesum = 0;
- for (char n : name)
- namesum += n - 64;
+ for (char n : name)
+ namesum += n - 64;
- sum += namesum * ++count;
- }
+ sum += namesum * ++count;
+ }
- return sum;
+ return sum;
}
No newline at end of file
diff --git a/Euler_23.cpp b/Euler_23.cpp
@@ -3,21 +3,21 @@
int Euler::NonAbundantSums()
{
- int ceiling = 28123;
- std::vector<int> abundantNumbers;
- std::vector<int> nonAbundantSums(ceiling * 2 + 1, 0);
+ 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);
+ for (int i = 1; i <= ceiling; ++i)
+ {
+ if(EulerUtility::sumOfDivisors(i) > 2 * i)
+ abundantNumbers.push_back(i);
- nonAbundantSums[i - 1] = i;
- }
+ nonAbundantSums[i - 1] = i;
+ }
- for (int abnum : abundantNumbers)
- for (int abnum2 : abundantNumbers)
- nonAbundantSums[abnum + abnum2 - 1] = 0;
+ for (int abnum : abundantNumbers)
+ for (int abnum2 : abundantNumbers)
+ nonAbundantSums[abnum + abnum2 - 1] = 0;
- return std::accumulate(nonAbundantSums.begin(), nonAbundantSums.end(), 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
@@ -3,10 +3,10 @@
std::string Euler::LexicographicPermutations()
{
- std::string lexicon = "0123456789";
+ std::string lexicon = "0123456789";
- for (int i = 1; i < 1e6; ++i)
- std::next_permutation(lexicon.begin(), lexicon.end());
+ for (int i = 1; i < 1e6; ++i)
+ std::next_permutation(lexicon.begin(), lexicon.end());
- return lexicon;
+ return lexicon;
}
No newline at end of file
diff --git a/Euler_25.cpp b/Euler_25.cpp
@@ -2,36 +2,36 @@
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;
+ 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
@@ -2,26 +2,26 @@
int Euler::ReciprocalCycles()
{
- std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(1000);
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(1000);
- for (int j = primes.size() - 1; j >= 0; --j)
- {
- bool highestReciprocalCycle = true;
+ 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);
+ 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 (((bi % primes[j] == 1) && (i != (primes[j] - 1))) || ((bi % primes[j] != 1) && (i == (primes[j] - 1))))
+ {
+ highestReciprocalCycle = false;
+ break;
+ }
+ }
- if (highestReciprocalCycle)
- return primes[j];
- }
+ if (highestReciprocalCycle)
+ return primes[j];
+ }
- return 0;
+ return 0;
}
No newline at end of file
diff --git a/Euler_27.cpp b/Euler_27.cpp
@@ -2,9 +2,9 @@
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);
+ 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;
+ return 0;
}
No newline at end of file
diff --git a/Euler_28.cpp b/Euler_28.cpp
@@ -2,10 +2,10 @@
long Euler::SpiralDiagonals()
{
- long sum = 1;
+ long sum = 1;
- for (int i = 3; i <= 1001; i += 2)
- sum += ((int)(pow(i, 2)) * 4) - (i * 6) + 6;
+ for (int i = 3; i <= 1001; i += 2)
+ sum += ((int)(pow(i, 2)) * 4) - (i * 6) + 6;
- return sum;
+ return sum;
}
No newline at end of file
diff --git a/Euler_29.cpp b/Euler_29.cpp
@@ -4,74 +4,74 @@
std::vector<int> getPowers(int ceiling)
{
- std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(ceiling);
- std::vector<int> powers(ceiling + 1, 0);
+ 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;
+ 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;
- }
+ 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;
+ if (p_factors.size() > 1)
+ {
+ std::unordered_set<int> unique_p_factors;
- for (int p : p_factors)
- unique_p_factors.insert(p);
+ 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;
- }
- }
+ if (unique_p_factors.size() == 1)
+ powers[j] = p_factors.size();
+ else if (EulerUtility::isPerfectSquare(j))
+ powers[j] = 2;
+ }
+ }
- return powers;
+ return powers;
}
int Euler::DistinctPowers()
{
- int ceiling = 100;
- std::vector<int> powers = getPowers(ceiling);
+ int ceiling = 100;
+ std::vector<int> powers = getPowers(ceiling);
- int sum = 0;
+ 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 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;
- }
- }
+ 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;
- }
- }
- }
+ if (unique)
+ ++sum;
+ }
+ }
+ }
- return sum;
+ return sum;
}
No newline at end of file
diff --git a/Euler_3.cpp b/Euler_3.cpp
@@ -4,49 +4,49 @@
llui lpf(llui x)
{
- bool is_prime;
+ bool is_prime;
- llui count = 1;
- llui my_prime = 2; //set to first 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 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;
+ 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;
+ if(is_prime) {
+ if (x % i == 0)
+ return i;
- ++count;
- my_prime = i;
- }
- }
+ ++count;
+ my_prime = i;
+ }
+ }
- return 0; //prime factor does not exist (1 does not count as prime)
+ return 0; //prime factor does not exist (1 does not count as prime)
}
llui Euler::LargestPrimeFactor()
{
- std::vector<llui> primes;
+ std::vector<llui> primes;
- primes.push_back(1);
+ primes.push_back(1);
- llui x = 600851475143;
+ llui x = 600851475143;
- while (x > 1)
- {
- x /= primes.back();
+ while (x > 1)
+ {
+ x /= primes.back();
- llui y = lpf(x);
+ llui y = lpf(x);
- if (y != 0)
- primes.push_back(y);
- }
+ if (y != 0)
+ primes.push_back(y);
+ }
- std::sort (primes.begin(), primes.end());
+ std::sort (primes.begin(), primes.end());
- return primes.back();
+ return primes.back();
}
No newline at end of file
diff --git a/Euler_30.cpp b/Euler_30.cpp
@@ -2,20 +2,20 @@
long Euler::DigitFifthPowers()
{
- long sum = 0;
+ long sum = 0;
- for (int j = 0 ; j < 500000; ++j)
- {
- long currentPowerTotal = 0;
+ for (int j = 0 ; j < 500000; ++j)
+ {
+ long currentPowerTotal = 0;
- std::string current = std::to_string(j);
+ std::string current = std::to_string(j);
- for (unsigned i = 0; i < current.length(); i++)
- currentPowerTotal += (int)pow(current.at(i) - 48, 5);
+ for (unsigned i = 0; i < current.length(); i++)
+ currentPowerTotal += (int)pow(current.at(i) - 48, 5);
- if (j == currentPowerTotal)
- sum += currentPowerTotal;
- }
+ if (j == currentPowerTotal)
+ sum += currentPowerTotal;
+ }
- return sum - 1;
+ return sum - 1;
}
diff --git a/Euler_31.cpp b/Euler_31.cpp
@@ -7,14 +7,14 @@ int coinSumRecurse(int money, int maxcoin)
int sum = 0;
if(maxcoin == 7)
- return 1;
+ return 1;
for(int i = maxcoin; i < 8; i++)
{
if (money - coins[i] == 0)
- ++sum;
+ ++sum;
if (money - coins[i] > 0)
- sum += coinSumRecurse(money - coins[i], i);
+ sum += coinSumRecurse(money - coins[i], i);
}
return sum;
@@ -27,17 +27,17 @@ int Euler::CoinSums()
//int Euler::CoinSums() //original solution
//{
-// int sum = 0;
+// 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;
+// 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;
+// return sum + 1;
//}
No newline at end of file
diff --git a/Euler_32.cpp b/Euler_32.cpp
@@ -6,39 +6,39 @@
int getSubInt(unsigned it1, unsigned it2, std::vector<int> &sub_lex)
{
- int integer = 0;
+ int integer = 0;
- for (unsigned i = it1; i < it2; ++i)
- {
- integer *= 10;
- integer += sub_lex[i];
- }
+ for (unsigned i = it1; i < it2; ++i)
+ {
+ integer *= 10;
+ integer += sub_lex[i];
+ }
- return integer;
+ 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));
+ 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;
+ 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);
+ 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);
- }
+ if (multiplicand * multiplier == product)
+ products.insert(product);
+ }
- std::next_permutation(lex.begin(), lex.end());
- }
+ std::next_permutation(lex.begin(), lex.end());
+ }
- return std::accumulate(products.begin(), products.end(), 0);
+ return std::accumulate(products.begin(), products.end(), 0);
}
No newline at end of file
diff --git a/Euler_33.cpp b/Euler_33.cpp
@@ -2,66 +2,66 @@
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];
+ 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;
- }
+ i = 0;
+ }
+ else
+ ++i;
+ }
- std::vector<int> l;
+ std::vector<int> l;
- l.push_back(n);
- l.push_back(d);
+ l.push_back(n);
+ l.push_back(d);
- return l;
+ 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);
- }
+ 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<int> primes = EulerUtility::getPrimesUnderCeiling(52);
- std::vector<std::vector<int>> dc_fractions;
+ std::vector<std::vector<int>> dc_fractions;
- for (int denominator = 10; denominator < 100; ++ denominator)
- {
- std::vector<int> denom = EulerUtility::intToDigits(denominator);
+ 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);
+ 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);
- }
- }
+ addDigitCancellingFraction(denom, numer, primes, dc_fractions, numerator, denominator, true);
+ addDigitCancellingFraction(denom, numer, primes, dc_fractions, numerator, denominator, false);
+ }
+ }
- int n = 1, d = 1;
+ int n = 1, d = 1;
- for (std::vector<int> fraction : dc_fractions)
- {
- n *= fraction[0];
- d *= fraction[1];
- }
+ for (std::vector<int> fraction : dc_fractions)
+ {
+ n *= fraction[0];
+ d *= fraction[1];
+ }
- std::vector<int> lowestProduct = lowestTerm(n, d, primes);
+ std::vector<int> lowestProduct = lowestTerm(n, d, primes);
- return lowestProduct[1];
+ return lowestProduct[1];
}
No newline at end of file
diff --git a/Euler_34.cpp b/Euler_34.cpp
@@ -2,21 +2,21 @@
llui Euler::DigitFactorials()
{
- int factorials[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
- llui sum = 0;
+ 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;
+ for (unsigned i = 0 ; i < 50000; ++i)
+ {
+ long currentTotal = 0;
- std::vector<int> digits = EulerUtility::intToDigits(i);
+ std::vector<int> digits = EulerUtility::intToDigits(i);
- for (int digit : digits)
- currentTotal += factorials[digit];
+ for (int digit : digits)
+ currentTotal += factorials[digit];
- if (i == currentTotal)
- sum += currentTotal;
- }
+ if (i == currentTotal)
+ sum += currentTotal;
+ }
- return sum - 3;
+ return sum - 3;
}
No newline at end of file
diff --git a/Euler_35.cpp b/Euler_35.cpp
@@ -2,41 +2,41 @@
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;
+ 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
@@ -5,36 +5,36 @@
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;
+ for (unsigned int i = 0; i < n.length(); ++i)
+ if (n.at(i) != n.at(n.length() - 1 - i))
+ return false;
- return true;
+ return true;
}
bool isPalindromeInTwoBases(int i)
{
- std::ostringstream oss;
- oss << i;
+ std::ostringstream oss;
+ oss << i;
- std::string b10 = oss.str();
+ std::string b10 = oss.str();
- if (!isPalindrome(b10))
- return false;
+ if (!isPalindrome(b10))
+ return false;
- std::string b2 = std::bitset<32>(i).to_string();
- b2 = b2.substr(b2.find('1'));
+ std::string b2 = std::bitset<32>(i).to_string();
+ b2 = b2.substr(b2.find('1'));
- return isPalindrome(b2);
+ return isPalindrome(b2);
}
llui Euler::DoubleBasedPalindromes()
{
- llui sum = 0;
+ llui sum = 0;
- for (int i = 1; i < 1e6; ++i)
- if (isPalindromeInTwoBases(i))
- sum += i;
+ for (int i = 1; i < 1e6; ++i)
+ if (isPalindromeInTwoBases(i))
+ sum += i;
- return sum;
+ return sum;
}
No newline at end of file
diff --git a/Euler_37.cpp b/Euler_37.cpp
@@ -2,26 +2,26 @@
bool isTruncPrime(std::string &p, std::vector<int> &primes, bool left)
{
- bool isPrime = primes[atoi(p.c_str())] != -1;
+ bool isPrime = primes[atoi(p.c_str())] != -1;
- if (p.size() == 1)
- return isPrime;
+ if (p.size() == 1)
+ return isPrime;
- return (isPrime) ? isTruncPrime(p.substr(left, p.size() - 1), primes, left) : false;
+ 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
+ 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;
- }
+ 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;
+ return sum;
}
No newline at end of file
diff --git a/Euler_38.cpp b/Euler_38.cpp
@@ -2,21 +2,21 @@
int Euler::PanDigitalMultiples()
{
- int greatestPanDigitalMultiple = 918273645;
+ 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());
+ 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;
- }
- }
- }
+ if ((EulerUtility::hasUniqueDigits(potentialPanDigital, false)) && (potentialPanDigital > greatestPanDigitalMultiple))
+ greatestPanDigitalMultiple = potentialPanDigital;
+ }
+ }
+ }
- return greatestPanDigitalMultiple;
+ return greatestPanDigitalMultiple;
}
No newline at end of file
diff --git a/Euler_39.cpp b/Euler_39.cpp
@@ -2,25 +2,25 @@
int Euler::MaximumRightAngledTriangles()
{
- int perimeter = 120;
- int maximum = 3;
+ int perimeter = 120;
+ int maximum = 3;
- for (int p = 121; p <= 1000; ++p)
- {
- int solutions = 0;
+ 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;
+ 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;
- }
- }
+ if (solutions > maximum)
+ {
+ maximum = solutions;
+ perimeter = p;
+ }
+ }
- return perimeter;
+ return perimeter;
}
No newline at end of file
diff --git a/Euler_4.cpp b/Euler_4.cpp
@@ -5,34 +5,34 @@
bool isPalindrome(int i)
{
- std::ostringstream oss;
- oss << i;
+ std::ostringstream oss;
+ oss << i;
- std::string temp = oss.str();
+ 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;
+ for (unsigned int i = 0; i < temp.length(); ++i)
+ if (temp.at(i) != temp.at(temp.length() - 1 - i))
+ return false;
- return true;
+ 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();
+ 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
@@ -2,23 +2,23 @@
int product(std::string champ, int pos)
{
- if (pos == 1)
- return 1;
+ if (pos == 1)
+ return 1;
- return (champ[pos - 1] - 48) * product (champ, pos / 10);
+ return (champ[pos - 1] - 48) * product (champ, pos / 10);
}
int Euler::ChampernowneConstant()
{
- std::string champernowne;
+ std::string champernowne;
- for (int i = 1; i <= 1e6; ++i)
- {
- champernowne += std::to_string(i);
+ for (int i = 1; i <= 1e6; ++i)
+ {
+ champernowne += std::to_string(i);
- if (champernowne.size() >= 1e6)
- break;
- }
+ if (champernowne.size() >= 1e6)
+ break;
+ }
- return product(champernowne, 1e6);
+ return product(champernowne, 1e6);
}
No newline at end of file
diff --git a/Euler_41.cpp b/Euler_41.cpp
@@ -4,23 +4,23 @@
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;
+ 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;
+ if ((mod % 2 != 0) && (mod != 5))
+ if (EulerUtility::isPrime(potentialPanPrime, 5))
+ return potentialPanPrime;
- std::prev_permutation(lexicon.begin(), lexicon.end());
- }
+ std::prev_permutation(lexicon.begin(), lexicon.end());
+ }
- return determinePanPrime(lexicon.substr(1, lexicon.size() - 1));
+ return determinePanPrime(lexicon.substr(1, lexicon.size() - 1));
}
int Euler::PanDigitalPrime()
{
- return determinePanPrime("987654321");
+ return determinePanPrime("987654321");
}
No newline at end of file
diff --git a/Euler_42.cpp b/Euler_42.cpp
@@ -2,20 +2,20 @@
int Euler::CodedTriangleNumbers()
{
- std::vector<std::string> names = EulerUtility::openWordFile("E:\Euler Resources\Euler 42.txt");
+ std::vector<std::string> names = EulerUtility::openWordFile("E:\Euler Resources\Euler 42.txt");
- int count = 0;
+ int count = 0;
- for (std::string name : names)
- {
- int total = 0;
+ for (std::string name : names)
+ {
+ int total = 0;
- for (char n : name)
- total += n - 64;
+ for (char n : name)
+ total += n - 64;
- if (EulerUtility::isTriangle(total))
- ++count;
- }
+ if (EulerUtility::isTriangle(total))
+ ++count;
+ }
- return count;
+ return count;
}
No newline at end of file
diff --git a/Euler_43.cpp b/Euler_43.cpp
@@ -5,49 +5,49 @@
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);
- }
- }
+ 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 (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]));
+ 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;
+ 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));
+ 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);
+ findDivisiblePermutations(divisiblePermutations, potentialSubLex, 6);
- BigInteger i = 0;
+ BigInteger i = 0;
- for (unsigned long ul : divisiblePermutations)
- i += ul;
+ for (unsigned long ul : divisiblePermutations)
+ i += ul;
- return i;
+ return i;
}
No newline at end of file
diff --git a/Euler_44.cpp b/Euler_44.cpp
@@ -2,22 +2,22 @@
int getPentagonal(int n)
{
- return (n * ((3 * n) - 1)) / 2;
+ return (n * ((3 * n) - 1)) / 2;
}
int Euler::MinimizedPentagonalDifference()
{
- std::vector<int> pentaNos(1, 1);
- std::vector<int> potential_D;
+ std::vector<int> pentaNos(1, 1);
+ std::vector<int> potential_D;
- for (;;)
- {
- pentaNos.push_back(getPentagonal(pentaNos.size() + 1));
+ 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];
- }
+ 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;
+ return 0;
}
No newline at end of file
diff --git a/Euler_45.cpp b/Euler_45.cpp
@@ -2,18 +2,18 @@
llui getTriangular(llui n)
{
- return (n * (n + 1)) / 2;
+ return (n * (n + 1)) / 2;
}
llui Euler::TriangularPentagonalHexagonal()
{
- for (int i = 286;; ++i)
- {
- llui tri = getTriangular(i);
+ for (int i = 286;; ++i)
+ {
+ llui tri = getTriangular(i);
- if ((i & 1) && EulerUtility::isPentagonal(tri))
- return tri;
- }
+ if ((i & 1) && EulerUtility::isPentagonal(tri))
+ return tri;
+ }
- return 0;
+ return 0;
}
No newline at end of file
diff --git a/Euler_46.cpp b/Euler_46.cpp
@@ -2,30 +2,30 @@
llui Euler::GoldbachsOtherConjecture()
{
- std::vector<int> primes = EulerUtility::getPrimesUnderCeilingIndexed(1000000);
+ 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 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;
- }
- }
- }
+ 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;
- }
- }
+ if (!conjecture_holds)
+ return i;
+ }
+ }
- return 0;
+ return 0;
}
No newline at end of file
diff --git a/Euler_47.cpp b/Euler_47.cpp
@@ -4,36 +4,36 @@
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;
+ 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);
+ int consecutive = 0;
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(1000000);
- for (int i = 647; ; ++i)
- {
- consecutive = (distinctPrimeFactors(i, primes).size() == 4) ? consecutive + 1 : 0;
+ for (int i = 647; ; ++i)
+ {
+ consecutive = (distinctPrimeFactors(i, primes).size() == 4) ? consecutive + 1 : 0;
- if (consecutive == 4)
- return i - 3;
- }
+ if (consecutive == 4)
+ return i - 3;
+ }
- return 0;
+ return 0;
}
No newline at end of file
diff --git a/Euler_48.cpp b/Euler_48.cpp
@@ -2,10 +2,10 @@
BigInteger Euler::SelfPowers()
{
- BigInteger i;
+ BigInteger i;
- for (int j = 1; j <= 1000; ++j)
- i += EulerUtility::power(j, j);
+ for (int j = 1; j <= 1000; ++j)
+ i += EulerUtility::power(j, j);
- return i;
+ return i;
}
No newline at end of file
diff --git a/Euler_49.cpp b/Euler_49.cpp
@@ -4,39 +4,39 @@
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;
+ 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
@@ -5,38 +5,38 @@
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];
+ 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);
+ 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 = 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]);
+ 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);
+ 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
@@ -4,52 +4,52 @@
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;
+ 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
@@ -3,63 +3,63 @@
struct pair
{
- int prime;
- int digit;
+ int prime;
+ int digit;
};
int Euler::PrimeDigitReplacements()
{
- std::vector<int> primes = EulerUtility::getPrimesUnderCeilingIndexed(1000000);
- std::vector<pair> candidates;
+ 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);
+ for (int prime : primes)
+ {
+ if (prime != -1)
+ {
+ std::vector<int> digits = EulerUtility::intToDigits(prime);
- int repeatedDigits[3] = {0, 0, 0};
+ 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 < 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 (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 (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 < 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;
+ 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 (primes[EulerUtility::digitsToInteger(digits)] > 0)
+ ++sizeOfFamily;
+ }
+ }
- if (sizeOfFamily >= 8)
- return p.prime;
- }
+ if (sizeOfFamily >= 8)
+ return p.prime;
+ }
- return 0;
+ return 0;
}
No newline at end of file
diff --git a/Euler_52.cpp b/Euler_52.cpp
@@ -3,21 +3,21 @@
int Euler::PermutedMultiples()
{
- for (int i = 1;;++i)
- {
- std::vector<int> digits = EulerUtility::intToDigits(i);
+ 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);
+ 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 (!std::is_permutation(digits.begin(), digits.end(), multiple.begin()))
+ break;
- if (j == 6)
- return i;
- }
- }
+ if (j == 6)
+ return i;
+ }
+ }
- return 0;
+ return 0;
}
No newline at end of file
diff --git a/Euler_53.cpp b/Euler_53.cpp
@@ -2,12 +2,12 @@
int Euler::CombinatoricSelections()
{
- int total = 0;
+ int total = 0;
- for (int i = 1; i <= 100; ++i)
- for (int j = 1; j <= i; ++j)
- if (EulerUtility::choose(i, j) > 1000000)
- ++total;
+ for (int i = 1; i <= 100; ++i)
+ for (int j = 1; j <= i; ++j)
+ if (EulerUtility::choose(i, j) > 1000000)
+ ++total;
- return total;
+ return total;
}
No newline at end of file
diff --git a/Euler_54.cpp b/Euler_54.cpp
@@ -7,239 +7,239 @@
struct hand
{
- int handValue;
- std::vector<int> cardValues;
+ int handValue;
+ std::vector<int> cardValues;
};
struct game
{
- hand hands[2];
+ 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];
+ char c = hand[0][1];
- for (int i = 1; i < hand.size(); ++i)
- if (hand[i][1] != c)
- return false;
+ for (int i = 1; i < hand.size(); ++i)
+ if (hand[i][1] != c)
+ return false;
- return true;
+ 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;
+ for (int i = 1; i < indices.size(); ++i)
+ if (indices[i] != indices[i - 1] - 1)
+ return false;
- return true;
+ 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;
+ 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 j : us)
+ {
+ int total = 0;
- for (int k = 0; k < cardValues.size(); ++k)
- if (j == cardValues[k])
- ++total;
+ for (int k = 0; k < cardValues.size(); ++k)
+ if (j == cardValues[k])
+ ++total;
- if (total == t)
- return high;
- }
+ if (total == t)
+ return high;
+ }
- return def;
+ 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;
+ 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;
- }
+ 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;
+ 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[0].handValue > g.hands[1].handValue)
+ return false;
- if (g.hands[1].handValue > g.hands[0].handValue)
- return true;
+ 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;
+ 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;
- }
+ if (g.hands[1].cardValues[i] > g.hands[0].cardValues[i])
+ return true;
+ }
- return true;
+ return true;
}
int Euler::PokerHands()
{
- int scores[2] = {0, 0};
+ int scores[2] = {0, 0};
- std::ifstream fin;
- fin.open("E:\Euler Resources\Euler 54.txt");
- int idx = 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, ' ')))];
+ for (std::string line; std::getline(fin, line);)
+ ++scores[determineWinner(determineHands(EulerUtility::strTokenizer(line, ' ')))];
- fin.close();
+ fin.close();
- return scores[0];
+ return scores[0];
}
No newline at end of file
diff --git a/Euler_55.cpp b/Euler_55.cpp
@@ -4,50 +4,50 @@
bool isPalindrome(BigInteger i)
{
- std::ostringstream oss;
- oss << i;
+ std::ostringstream oss;
+ oss << i;
- std::string temp = oss.str();
+ 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;
+ 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;
+ return true;
}
BigInteger reverse(BigInteger i)
{
- BigInteger reverse = 0;
+ BigInteger reverse = 0;
- while(i > 0)
- {
- reverse = reverse * 10 + (i % 10);
- i /= 10;
- }
+ while(i > 0)
+ {
+ reverse = reverse * 10 + (i % 10);
+ i /= 10;
+ }
- return reverse;
+ return reverse;
}
BigInteger Euler::LychrelNumbers()
{
- int lychel = 9999;
+ int lychel = 9999;
- for (int i = 1; i < 10000; ++i)
- {
- BigInteger current(i);
+ for (int i = 1; i < 10000; ++i)
+ {
+ BigInteger current(i);
- for (int j = 0; j < 50; ++j)
- {
- current = current + reverse(current);
+ for (int j = 0; j < 50; ++j)
+ {
+ current = current + reverse(current);
- if (isPalindrome(current))
- {
- --lychel;
- break;
- }
- }
- }
+ if (isPalindrome(current))
+ {
+ --lychel;
+ break;
+ }
+ }
+ }
- return lychel;
+ return lychel;
}
No newline at end of file
diff --git a/Euler_56.cpp b/Euler_56.cpp
@@ -4,19 +4,19 @@
int Euler::PowerfulDigitSum()
{
- int highestDigitSum = 0;
+ 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);
+ 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;
- }
- }
+ if (digitSum > highestDigitSum)
+ highestDigitSum = digitSum;
+ }
+ }
- return highestDigitSum;
+ return highestDigitSum;
}
No newline at end of file
diff --git a/Euler_57.cpp b/Euler_57.cpp
@@ -2,18 +2,18 @@
int Euler::SquareRootConvergents()
{
- BigInteger n = 3, d = 2;
- int count = 0;
+ BigInteger n = 3, d = 2;
+ int count = 0;
- for (int i = 1; i < 1000; ++i)
- {
- n += d;
- std::swap(n, d);
- n += d;
+ 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;
- }
+ if (EulerUtility::BigIntToDigits(n).size() > EulerUtility::BigIntToDigits(d).size())
+ ++count;
+ }
- return count;
+ return count;
}
No newline at end of file
diff --git a/Euler_58.cpp b/Euler_58.cpp
@@ -2,28 +2,28 @@
ll Euler::SpiralPrimes()
{
- ll n = 8, d = 13, i = 26, count = 7, topRight = 31;
- int mod3 = -1;
+ 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;
+ 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 (EulerUtility::isPrime(topRight + count - 1, 5))
+ ++n;
- if (mod3 != 0)
- if (EulerUtility::isPrime(topRight, 5))
- ++n;
+ if (mod3 != 0)
+ if (EulerUtility::isPrime(topRight, 5))
+ ++n;
- if (mod3 != 1)
- if (EulerUtility::isPrime(topRight + (count * 2) - 2, 5))
- ++n;
- }
+ if (mod3 != 1)
+ if (EulerUtility::isPrime(topRight + (count * 2) - 2, 5))
+ ++n;
+ }
- return count;
+ return count;
}
No newline at end of file
diff --git a/Euler_59.cpp b/Euler_59.cpp
@@ -5,35 +5,35 @@
int Euler::xorDecryption()
{
- const int file_size = 1201;
+ const int file_size = 1201;
- std::ifstream file;
- std::vector<int> cypher;
- std::string character;
- std::string word = " the ";
+ std::ifstream file;
+ std::vector<int> cypher;
+ std::string character;
+ std::string word = " the ";
- file.open("E:\Euler Resources\Euler 59.txt");
+ file.open("E:\Euler Resources\Euler 59.txt");
- while(getline(file, character, ','))
- cypher.push_back(atoi(character.c_str()));
+ while(getline(file, character, ','))
+ cypher.push_back(atoi(character.c_str()));
- char message[file_size];
- int pwd[3];
+ 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];
+ 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);
- }
- }
- }
+ if (std::string(message).find(word) != std::string::npos)
+ return std::accumulate(message, message + file_size, 0);
+ }
+ }
+ }
- return 0;
+ return 0;
}
No newline at end of file
diff --git a/Euler_6.cpp b/Euler_6.cpp
@@ -2,14 +2,14 @@
int Euler::DifferenceSumOfSquaresSquareOfSum100()
{
- int sumOfSquares = 0;
- int squareOfSum = 0;
+ int sumOfSquares = 0;
+ int squareOfSum = 0;
- for (int i = 1; i <= 100; ++i) {
- squareOfSum += i;
- sumOfSquares += (int)pow(i, 2);
- }
+ for (int i = 1; i <= 100; ++i) {
+ squareOfSum += i;
+ sumOfSquares += (int)pow(i, 2);
+ }
- squareOfSum = (int)pow(squareOfSum, 2);
- return squareOfSum - sumOfSquares;
+ squareOfSum = (int)pow(squareOfSum, 2);
+ return squareOfSum - sumOfSquares;
}
No newline at end of file
diff --git a/Euler_60.cpp b/Euler_60.cpp
@@ -5,61 +5,61 @@
int Euler::PrimePairSets()
{
- std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(100000);
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(100000);
- std::vector<std::vector<int>> concatPrimes(10000, std::vector<int>());
+ 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);
+ 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);
+ 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))
+ {
+ 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;
- }
- }
- }
+ 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 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 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]);
+ 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];
- }
- }
- }
- }
+ if (intersection_c.size() > 0)
+ return i + j + k + l + intersection_c[0];
+ }
+ }
+ }
+ }
- return 0;
+ return 0;
}
No newline at end of file
diff --git a/Euler_61.cpp b/Euler_61.cpp
@@ -4,71 +4,71 @@
bool match(int a, int b)
{
- std::vector<int> digits_a = EulerUtility::intToDigits(a);
- std::vector<int> digits_b = EulerUtility::intToDigits(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]);
+ 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;
+ 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;
+ 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 = 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);
+ for (int i : figurates[0])
+ {
+ cycle.push_back(i);
- int answer = recurseFigurates(cycle, figurates, indices, 1);
+ int answer = recurseFigurates(cycle, figurates, indices, 1);
- if (answer != 0)
- {
- return answer;
- }
+ if (answer != 0)
+ {
+ return answer;
+ }
- cycle.pop_back();
- }
+ cycle.pop_back();
+ }
- return 0;
+ return 0;
}
No newline at end of file
diff --git a/Euler_62.cpp b/Euler_62.cpp
@@ -5,36 +5,36 @@
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;
+ 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
@@ -2,22 +2,22 @@
int Euler::PowerfulDigitCounts()
{
- int count = 0;
+ 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;
- }
- }
- }
+ 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;
+ return count;
}
No newline at end of file
diff --git a/Euler_64.cpp b/Euler_64.cpp
@@ -8,77 +8,77 @@
//
//int Euler::OddPeriodSquareRoots()
//{
-// int count = 0;
+// int count = 0;
//
-// for (cpp_dec_float_500 i = 1; i <= 10000; ++i)
-// {
-// int sequenceLength = 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);
+// 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;
+// if (!EulerUtility::isPerfectSquare(i.convert_to<int>()))
+// {
+// bool sequenceDetermined = false;
+// bool sequenceIsOdd = false;
//
-// while (!sequenceDetermined)
-// {
-// value = 1.0 / (value - mp::floor(value));
+// while (!sequenceDetermined)
+// {
+// value = 1.0 / (value - mp::floor(value));
//
-// if (mp::floor(value) == 2 * floor)
-// {
-// sequenceDetermined = true;
-// sequenceIsOdd = sequenceLength + 1 & 1;
-// }
-// else
-// {
-// ++sequenceLength;
-// }
-// }
+// if (mp::floor(value) == 2 * floor)
+// {
+// sequenceDetermined = true;
+// sequenceIsOdd = sequenceLength + 1 & 1;
+// }
+// else
+// {
+// ++sequenceLength;
+// }
+// }
//
-// if (sequenceIsOdd)
-// {
-// ++count;
-// }
-// }
-// }
+// if (sequenceIsOdd)
+// {
+// ++count;
+// }
+// }
+// }
//
-// return count;
+// return count;
//}
int period(int n)
{
- double n2 = std::sqrtl(n);
- int a = n2, p = 0, q = 1, length = 0;
+ 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 );
+ do
+ {
+ length++;
+ p = a * q - p;
+ q = ( n - p * p ) / q;
+ a = ( p + n2 ) /q;
+ } while ( q != 1 );
- return length;
+ return length;
}
int Euler::OddPeriodSquareRoots()
{
- int odds = 0;
+ int odds = 0;
- for (int n = 1; n <= 10000; n++)
- {
- int n2 = sqrt(n);
+ for (int n = 1; n <= 10000; n++)
+ {
+ int n2 = sqrt(n);
- if (n2 * n2 != n)
- {
- if (period(n) & 1)
- {
- odds++;
- }
- }
- }
+ if (n2 * n2 != n)
+ {
+ if (period(n) & 1)
+ {
+ odds++;
+ }
+ }
+ }
- return odds;
+ return odds;
}
No newline at end of file
diff --git a/Euler_65.cpp b/Euler_65.cpp
@@ -4,55 +4,55 @@
std::vector<BigInteger> recurseFraction2(std::vector<BigInteger> period, BigInteger n, std::vector<BigInteger> fraction)
{
- if (n > period.size() - 1)
- return fraction;
+ if (n > period.size() - 1)
+ return fraction;
- std::swap(fraction[0], fraction[1]);
+ std::swap(fraction[0], fraction[1]);
- fraction[0] = (fraction[1] * period[period.size() - n.toInt() - 1]) + fraction[0];
+ fraction[0] = (fraction[1] * period[period.size() - n.toInt() - 1]) + fraction[0];
- return recurseFraction2(period, n + 1, fraction);
+ return recurseFraction2(period, n + 1, fraction);
}
std::vector<BigInteger> recurseFraction2(std::vector<BigInteger> period, BigInteger n)
{
- std::vector<BigInteger> fraction;
+ std::vector<BigInteger> fraction;
- fraction.push_back(period[period.size() - 1]);
- fraction.push_back(1);
+ fraction.push_back(period[period.size() - 1]);
+ fraction.push_back(1);
- return recurseFraction2(period, 1, fraction);
+ 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];
+ 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());
+ std::vector<int> digits = EulerUtility::BigIntToDigits(periodiuy());
- return std::accumulate(digits.begin(), digits.end(), 0);
+ return std::accumulate(digits.begin(), digits.end(), 0);
}
diff --git a/Euler_66.cpp b/Euler_66.cpp
@@ -2,73 +2,73 @@
bool valueOfDiophantine(BigInteger x, BigInteger y, BigInteger n)
{
- return EulerUtility::power(x, 2) - (n * EulerUtility::power(y, 2)) == BigInteger(1);
+ 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;
+ if (n > period.size() - 1)
+ return fraction;
- std::swap(fraction[0], fraction[1]);
+ std::swap(fraction[0], fraction[1]);
- fraction[0] = (fraction[1] * period[period.size() - n.toInt() - 1]) + fraction[0];
+ fraction[0] = (fraction[1] * period[period.size() - n.toInt() - 1]) + fraction[0];
- return recurseFraction(period, n + 1, fraction);
+ return recurseFraction(period, n + 1, fraction);
}
std::vector<BigInteger> recurseFraction(std::vector<BigInteger> period, BigInteger n)
{
- std::vector<BigInteger> fraction;
+ std::vector<BigInteger> fraction;
- fraction.push_back(period[period.size() - 1]);
- fraction.push_back(1);
+ fraction.push_back(period[period.size() - 1]);
+ fraction.push_back(1);
- return recurseFraction(period, 1, fraction);
+ return recurseFraction(period, 1, fraction);
}
BigInteger valueOfX(BigInteger n)
{
- double n2 = std::sqrtl(n.toInt());
- BigInteger a = (int)n2, p = 0, q = 1;
+ double n2 = std::sqrtl(n.toInt());
+ BigInteger a = (int)n2, p = 0, q = 1;
- std::vector<BigInteger> period;
- std::vector<BigInteger> approx;
+ std::vector<BigInteger> period;
+ std::vector<BigInteger> approx;
- period.push_back(a);
+ 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);
+ 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);
+ } while (valueOfDiophantine(approx[0], approx[1], n) != 1);
- return approx[0];
+ 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;
+ 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
@@ -4,84 +4,84 @@
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 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];
+ return *row[0] + *row[1] + *row[2];
}
std::string Euler::Magic5GonRing()
{
- std::vector<int> nodes;
- std::set<std::string> magicStrings;
+ std::vector<int> nodes;
+ std::set<std::string> magicStrings;
- for (int i = 1; i <= 10; ++i)
- nodes.push_back(i);
+ 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] };
+ 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;
+ std::vector<int**> rows;
- rows.push_back(row1);
- rows.push_back(row2);
- rows.push_back(row3);
- rows.push_back(row4);
- rows.push_back(row5);
+ 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());
+ for (int i = 1; i < EulerUtility::factorial(10); ++i)
+ {
+ std::next_permutation(nodes.begin(), nodes.end());
- int val = sumRow(row1);
+ 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));
- }
+ 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;
+ std::set<std::string>::iterator it;
+ std::string last;
- for (it = magicStrings.begin(); it != magicStrings.end(); ++it)
- last = *it;
+ for (it = magicStrings.begin(); it != magicStrings.end(); ++it)
+ last = *it;
- return last;
+ return last;
}
No newline at end of file
diff --git a/Euler_69.cpp b/Euler_69.cpp
@@ -2,20 +2,20 @@
int Euler::EulerTotient()
{
- std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(1e6);
- std::vector<int> primesIndexed = EulerUtility::getPrimesUnderCeilingIndexed(1e6);
- double NoverPhi = 0, n = 0;
+ 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);
+ for (double i = 2; i <= 1e6; ++i)
+ {
+ int p = EulerUtility::phi(i, primes, primesIndexed);
- if (i / p > NoverPhi)
- {
- NoverPhi = i / p;
- n = i;
- }
- }
+ if (i / p > NoverPhi)
+ {
+ NoverPhi = i / p;
+ n = i;
+ }
+ }
- return n;
+ return n;
}
No newline at end of file
diff --git a/Euler_7.cpp b/Euler_7.cpp
@@ -2,28 +2,28 @@
int Euler::Get10001stPrime()
{
- int noOfPrimes = 0;
+ int noOfPrimes = 0;
- bool is_prime;
+ bool is_prime;
- int count = 2; //includes 2 & 3
- int my_prime = 2; //set to first 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 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;
+ 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(is_prime) {
+ ++count;
+ my_prime = i;
- if (count == 10001)
- return i;
- }
- }
+ if (count == 10001)
+ return i;
+ }
+ }
- return 0;
+ return 0;
}
diff --git a/Euler_70.cpp b/Euler_70.cpp
@@ -4,22 +4,22 @@
int Euler::TotientPermutation()
{
- std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(1e7);
- std::vector<int> primesIndexed = EulerUtility::getPrimesUnderCeilingIndexed(1e7);
- double NoverPhi = 1e8, n = 0;
+ 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);
+ for (double i = 2; i <= 1e7; ++i)
+ {
+ int p = EulerUtility::phi(i, primes, primesIndexed);
- std::vector<int> digits = EulerUtility::intToDigits(i);
+ 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;
- }
- }
+ if ((std::is_permutation(digits.begin(), digits.end(), EulerUtility::intToDigits(p).begin())) && (NoverPhi > i / p))
+ {
+ NoverPhi = i / p;
+ n = i;
+ }
+ }
- return n;
+ return n;
}
No newline at end of file
diff --git a/Euler_71.cpp b/Euler_71.cpp
@@ -2,42 +2,42 @@
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
+ //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
+ EulerUtility::gcd(299999, 700000); //gcd = 7
- //Ok, they aren't relatively prime; Divide them down.
+ //Ok, they aren't relatively prime; Divide them down.
- EulerUtility::gcd(42857, 100000);
+ 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).
+ //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(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.
+ 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;
+ int xmax = 0, xmaxd = 2;
- for (int d = 2; d <= 1000000; ++d)
- {
- int x = 3 * d / 7;
+ 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;
- }
- }
+ if ((d % 7) == 0)
+ {
+ --x;
+ }
+ if (x * xmaxd > xmax * d)
+ {
+ xmax = x, xmaxd = d;
+ }
+ }
- return xmax; //As it happens, it was correct.
+ return xmax; //As it happens, it was correct.
}
No newline at end of file
diff --git a/Euler_72.cpp b/Euler_72.cpp
@@ -2,15 +2,15 @@
llui Euler::CountingFractions()
{
- llui total = 0;
-
- std::vector<int> primesIndexed = EulerUtility::getPrimesUnderCeilingIndexed(1e6);
- std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(1e6);
+ 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);
- }
+ for (int i = 1; i <= 1e6; ++i)
+ {
+ total += EulerUtility::phi(i, primes, primesIndexed);
+ }
- return total;
+ return total;
}
No newline at end of file
diff --git a/Euler_73.cpp b/Euler_73.cpp
@@ -16,39 +16,39 @@
llui Euler::CountingRangedFractions()
{
- llui count = 0;
- bool counting = false;
+ llui count = 0;
+ bool counting = false;
- int n = 12000;
- int a = 0;
- int b = 1;
- int c = 1;
- int d = n;
- int x = 0;
+ 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;
+ while (c <= n && !(a == 1 && b == 2))
+ {
+ int k = 0;
- if (d != 0)
- k = int((n + b)/d);
- else
- ++x;
+ if (d != 0)
+ k = int((n + b)/d);
+ else
+ ++x;
- int temp_a = a;
- int temp_b = b;
+ int temp_a = a;
+ int temp_b = b;
- a = c;
- b = d;
- c = k * c - temp_a;
- d = k * d - temp_b;
+ a = c;
+ b = d;
+ c = k * c - temp_a;
+ d = k * d - temp_b;
- if (counting)
- ++count;
+ if (counting)
+ ++count;
- if (a == 1 && b == 3)
- counting = true;
- }
+ if (a == 1 && b == 3)
+ counting = true;
+ }
- return count - 1;
+ return count - 1;
}
No newline at end of file
diff --git a/Euler_74.cpp b/Euler_74.cpp
@@ -4,90 +4,90 @@
#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());
+{
+ 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;
+ 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
@@ -4,36 +4,36 @@
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);
+ 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
@@ -2,43 +2,43 @@
ll partition(int n, std::vector<int> &cache)
{
- ll p = 0;
+ ll p = 0;
- if(n >= 0)
- {
- if(n == 0 || n == 1)
- {
- return 1;
- }
- if(cache[n - 1] != 0)
- {
- return cache[n - 1];
- }
+ if(n >= 0)
+ {
+ if(n == 0 || n == 1)
+ {
+ return 1;
+ }
+ if(cache[n - 1] != 0)
+ {
+ return cache[n - 1];
+ }
- int k = 1;
+ int k = 1;
- ll s1 = 0;
- ll s2 = 0;
+ ll s1 = 0;
+ ll s2 = 0;
- while (n - s2 >= 0)
- {
- s1 = (k * (3 * k - 1)) / 2;
- s2 = (k * (3 * k + 1)) / 2;
+ while (n - s2 >= 0)
+ {
+ s1 = (k * (3 * k - 1)) / 2;
+ s2 = (k * (3 * k + 1)) / 2;
- int sign = (k - 1) & 1 ? -1 : 1;
+ int sign = (k - 1) & 1 ? -1 : 1;
- p += sign * partition(n - s1, cache);
- p += sign * partition(n - s2, cache);
- ++k;
- }
+ p += sign * partition(n - s1, cache);
+ p += sign * partition(n - s2, cache);
+ ++k;
+ }
- cache[n - 1] = p;
- }
+ cache[n - 1] = p;
+ }
- return p;
+ return p;
}
int Euler::CountingSums()
{
- return partition(100, std::vector<int>(100, 0)) - 1;
+ 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
@@ -7,9 +7,9 @@ int primeSumRecurse(int n, int max, std::vector<int> &primes)
for(int i = max; i < primes.size(); i++)
{
if (n - primes[i] == 0)
- ++sum;
+ ++sum;
if (n - primes[i] > 0)
- sum += primeSumRecurse(n - primes[i], i, primes);
+ sum += primeSumRecurse(n - primes[i], i, primes);
}
return sum;
@@ -17,18 +17,18 @@ int primeSumRecurse(int n, int max, std::vector<int> &primes)
int Euler::PrimeSummations()
{
- int ceiling = 1000;
- std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(ceiling);
- std::reverse(primes.begin(), primes.end());
+ int ceiling = 1000;
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(ceiling);
+ std::reverse(primes.begin(), primes.end());
- int n = 0;
- int i = -1;
+ int n = 0;
+ int i = -1;
- while (n <= 5000)
- {
- ++i;
- n = primeSumRecurse(i, 0, primes);
- }
+ while (n <= 5000)
+ {
+ ++i;
+ n = primeSumRecurse(i, 0, primes);
+ }
- return i;
+ return i;
}
No newline at end of file
diff --git a/Euler_78.cpp b/Euler_78.cpp
@@ -2,59 +2,59 @@
BigInteger partition(BigInteger &n, std::vector<BigInteger> &cache)
{
- BigInteger p = 0;
+ BigInteger p = 0;
- if (n >= 0)
- {
- if (n == 0 || n == 1)
- {
- return 1;
- }
- if (cache[n.toInt() - 1] != 0)
- {
- return cache[n.toInt() - 1];
- }
+ if (n >= 0)
+ {
+ if (n == 0 || n == 1)
+ {
+ return 1;
+ }
+ if (cache[n.toInt() - 1] != 0)
+ {
+ return cache[n.toInt() - 1];
+ }
- int k = 1;
+ int k = 1;
- BigInteger s1 = 0;
- BigInteger s2 = 0;
+ BigInteger s1 = 0;
+ BigInteger s2 = 0;
- while (n - s2 >= 0)
- {
- s1 = (k * (3 * k - 1)) / 2;
- s2 = (k * (3 * k + 1)) / 2;
+ while (n - s2 >= 0)
+ {
+ s1 = (k * (3 * k - 1)) / 2;
+ s2 = (k * (3 * k + 1)) / 2;
- BigInteger sign = (k - 1) & 1 ? -1 : 1;
+ BigInteger sign = (k - 1) & 1 ? -1 : 1;
- p += sign * partition(n - s1, cache);
- p += sign * partition(n - s2, cache);
- ++k;
- }
+ p += sign * partition(n - s1, cache);
+ p += sign * partition(n - s2, cache);
+ ++k;
+ }
- cache[n.toInt() - 1] = p;
- }
+ cache[n.toInt() - 1] = p;
+ }
- return 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;
+ 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
@@ -5,37 +5,37 @@
std::string Euler::PasscodeDerivation()
{
- std::ifstream fin;
- std::vector<std::string> numbers;
+ std::ifstream fin;
+ std::vector<std::string> numbers;
- fin.open("E:\Euler Resources\Euler 79.txt");
+ fin.open("E:\Euler Resources\Euler 79.txt");
- std::string temp;
- while(std::getline(fin, temp))
- numbers.push_back(temp);
+ std::string temp;
+ while(std::getline(fin, temp))
+ numbers.push_back(temp);
- fin.close();
-
- std::set<char> tokens;
+ fin.close();
+
+ std::set<char> tokens;
- for (std::string n : numbers)
- for (char c : n)
- tokens.insert(c);
+ for (std::string n : numbers)
+ for (char c : n)
+ tokens.insert(c);
- std::string passcode(tokens.begin(),tokens.end());
+ 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();
+ 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 (i > j)
+ std::swap(passcode[i], passcode[j]);
- if (j > k)
- std::swap(passcode[j], passcode[k]);
- }
+ if (j > k)
+ std::swap(passcode[j], passcode[k]);
+ }
- return passcode;
+ return passcode;
}
No newline at end of file
diff --git a/Euler_8.cpp b/Euler_8.cpp
@@ -4,30 +4,30 @@
llui Euler::FindGreatestProductOf13AdjacentDigits()
{
- std::ifstream fin;
- fin.open("E:\Euler Resources\Euler 8.txt");
+ std::ifstream fin;
+ fin.open("E:\Euler Resources\Euler 8.txt");
- std::string number;
+ std::string number;
- std::getline(fin, number);
+ std::getline(fin, number);
- fin.close();
+ fin.close();
- llui greatestProduct = 0;
+ llui greatestProduct = 0;
- for (unsigned i = 0; i < number.length() - 13; ++i)
- {
- std::vector<int> digits;
+ for (unsigned i = 0; i < number.length() - 13; ++i)
+ {
+ std::vector<int> digits;
- llui temp = 1;
+ llui temp = 1;
- for (unsigned j = i; j < i + 13; ++j)
- temp *= (number.at(j) - 48);
+ for (unsigned j = i; j < i + 13; ++j)
+ temp *= (number.at(j) - 48);
- if (temp > greatestProduct) {
- greatestProduct = temp;
- }
- }
+ if (temp > greatestProduct) {
+ greatestProduct = temp;
+ }
+ }
- return greatestProduct;
+ return greatestProduct;
}
No newline at end of file
diff --git a/Euler_80.cpp b/Euler_80.cpp
@@ -8,23 +8,23 @@ typedef mp::number<mp::cpp_dec_float<120>> cpp_dec_float_120;
int Euler::SquareRootDigitalExpansion()
{
- int total = 0;
+ 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);
+ 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();
+ std::string irrational = buffer.str();
- if (irrational.size() > 2)
- {
- total += irrational[0] - '0';
+ if (irrational.size() > 2)
+ {
+ total += irrational[0] - '0';
- for (int i = 2; i < 101; ++i)
- total += irrational[i] - '0';
- }
- }
+ for (int i = 2; i < 101; ++i)
+ total += irrational[i] - '0';
+ }
+ }
- return total;
+ return total;
}
No newline at end of file
diff --git a/Euler_9.cpp b/Euler_9.cpp
@@ -4,14 +4,14 @@
int Euler::SpecialPythagoreanTriplet()
{
- for (int a = 1; a < 1000; ++a)
- for (int b = 1; b < 1000; ++b)
- {
- double c = sqrt(a * a + b * b);
+ 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;
- }
+ if ((a + b + c) == 1000)
+ return a * b * (int)c;
+ }
- return 0;
+ return 0;
}
No newline at end of file
diff --git a/Euler_97.py b/Euler_97.py
@@ -3,21 +3,21 @@ import math
from datetime import datetime
def find_last_x_digits(base, exponent, x):
- mod = 10 ** x
- exp = 1
- squares = []
- squares.append(base % mod)
- result = 1
-
- while exp < exponent:
- squares.append((squares[-1] ** 2) % mod)
- exp = exp * 2
-
- for i in range(len(squares)):
- if (2 ** i) & exponent:
- result = (result * squares[i]) % mod
-
- return result
+ mod = 10 ** x
+ exp = 1
+ squares = []
+ squares.append(base % mod)
+ result = 1
+
+ while exp < exponent:
+ squares.append((squares[-1] ** 2) % mod)
+ exp = exp * 2
+
+ for i in range(len(squares)):
+ if (2 ** i) & exponent:
+ result = (result * squares[i]) % mod
+
+ return result
base = 2
exponent = 7830457
diff --git a/Euler_99.py b/Euler_99.py
@@ -5,19 +5,19 @@ from datetime import datetime
with open('files/p099_base_exp.txt') as f:
pairs = f.read().splitlines()
-
+
line_number = 0
most_digits = 0.0
a = datetime.now()
for i, line in enumerate(pairs):
- base_exp = re.split(',',line)
- num_of_digits = float(base_exp[1]) * math.log10(float(base_exp[0]))
-
- if num_of_digits > most_digits:
- line_number = i + 1
- most_digits = num_of_digits
+ base_exp = re.split(',',line)
+ num_of_digits = float(base_exp[1]) * math.log10(float(base_exp[0]))
+
+ if num_of_digits > most_digits:
+ line_number = i + 1
+ most_digits = num_of_digits
delta = datetime.now() - a
diff --git a/Makefile b/Makefile
@@ -2,33 +2,33 @@
all:
%.o: %.cpp
- clang++ -O2 -Wall -Wextra -pedantic -std=c++11 $<
+ clang++ -O2 -Wall -Wextra -pedantic -std=c++11 $<
program =euler
euler-objects =
- main.o
- EulerUtility.o
- Euler_15.o
+ main.o
+ EulerUtility.o
+ Euler_15.o
euler-headers =
- EulerUtility.h
- Euler.h
+ EulerUtility.h
+ Euler.h
bigint-objects =
- BigUnsigned.o
- BigInteger.o
- BigIntegerAlgorithms.o
- BigUnsignedInABase.o
- BigIntegerUtils.o
+ BigUnsigned.o
+ BigInteger.o
+ BigIntegerAlgorithms.o
+ BigUnsignedInABase.o
+ BigIntegerUtils.o
bigint-headers =
- NumberlikeArray.hh
- BigUnsigned.hh
- BigInteger.hh
- BigIntegerAlgorithms.hh
- BigUnsignedInABase.hh
- BigIntegerLibrary.hh
+ NumberlikeArray.hh
+ BigUnsigned.hh
+ BigInteger.hh
+ BigIntegerAlgorithms.hh
+ BigUnsignedInABase.hh
+ BigIntegerLibrary.hh
bigint: $(bigint-objects)
@@ -37,10 +37,8 @@ $(bigint-objects): $(bigint-headers)
$(euler-objects): $(euler-headers) $(bigint-headers)
$(program) : $(euler-objects) $(bigint-objects)
- g++ $^ -o $@
+ g++ $^ -o $@
-clean :
- rm -f $(bigint-objects) $(program-objects) $(program)
+clean : rm -f $(bigint-objects) $(program-objects) $(program)
-all:
- make $(program)
+all: make $(program)
