commit d6c219beecaf1e22a8b3d87ec3975042f5326cb3
parent d59548f49d8acdcccf9ef43ca5c6f1fb949d9ffc
Author: mpizzzle <m@michaelpercival.xyz>
Date: Mon, 21 Sep 2020 22:35:57 +0100
replacing bootleg BigInt library with boost headers
Diffstat:
26 files changed, 430 insertions(+), 443 deletions(-)
diff --git a/Euler.h b/Euler.h
@@ -17,7 +17,7 @@ public:
llui TriangleNoWithGreaterThan500Divisors();
std::string LargeSum();
llui CollatzConjecture();
- //BigInteger LatticePaths();
+ cpp_int LatticePaths();
int DigitSum();
int LetterCounter();
int MaximumPathSum();
@@ -45,19 +45,19 @@ public:
int ChampernowneConstant();
int PanDigitalPrime();
int CodedTriangleNumbers();
- //BigInteger SubStringDivisibility();
+ cpp_int SubStringDivisibility();
int MinimizedPentagonalDifference();
llui TriangularPentagonalHexagonal();
llui GoldbachsOtherConjecture();
int DistinctPrimeFactors();
- //BigInteger SelfPowers();
+ cpp_int SelfPowers();
std::string PrimePermutations();
int ConsecutivePrimeSum();
int PrimeDigitReplacements();
int PermutedMultiples();
int CombinatoricSelections();
int PokerHands();
- //BigInteger LychrelNumbers();
+ cpp_int LychrelNumbers();
int PowerfulDigitSum();
int SquareRootConvergents();
ll SpiralPrimes();
diff --git a/EulerUtility.cpp b/EulerUtility.cpp
@@ -158,12 +158,12 @@ std::vector<int> EulerUtility::powerDigits(int n, int p)
return digits;
}
-/*BigInteger EulerUtility::bigFactorial(BigInteger n)
+cpp_int EulerUtility::bigFactorial(cpp_int n)
{
if (n == 0)
return 1;
return n * bigFactorial(n - 1);
-}*/
+}
int EulerUtility::factorial(int n)
{
@@ -172,10 +172,10 @@ int EulerUtility::factorial(int n)
return n * factorial(n - 1);
}
-/*BigInteger EulerUtility::choose(int n, int k)
+cpp_int EulerUtility::choose(int n, int k)
{
return EulerUtility::bigFactorial(n) / (EulerUtility::bigFactorial(k) * EulerUtility::bigFactorial(n - k));
-}*/
+}
bool EulerUtility::isPerfectSquare(llui n)
{
@@ -219,20 +219,15 @@ std::vector<int> EulerUtility::lluiToDigits(llui n)
return digitArray;
}
-/*std::vector<int> EulerUtility::BigIntToDigits(BigInteger n)
+std::vector<int> EulerUtility::BigIntToDigits(cpp_int n)
{
std::vector<int> digitArray;
-
- while (n != 0)
- {
- digitArray.push_back((n % 10).toInt());
- n /= 10;
- }
+ export_bits(n, std::back_inserter(digitArray), 32);
std::reverse(digitArray.begin(), digitArray.end());
return digitArray;
-}*/
+}
int EulerUtility::digitsToInteger(std::vector<int> d)
{
@@ -369,13 +364,13 @@ std::vector<std::string> EulerUtility::openWordFile(std::string filename)
return names;
}
-/*BigInteger EulerUtility::power(BigInteger i, int p)
+cpp_int EulerUtility::power(cpp_int i, int p)
{
if (p <= 0)
return 1;
return i * power(i, p - 1);
-}*/
+}
int EulerUtility::digitalRoot(int n)
{
@@ -388,7 +383,7 @@ int EulerUtility::digitalRoot(int n)
return digitSum;
}
-/*int EulerUtility::digitalRoot(BigInteger n)
+int EulerUtility::digitalRoot(cpp_int n)
{
std::vector<int> digits = BigIntToDigits(n);
int digitSum = std::accumulate(digits.begin(), digits.end(), 0);
@@ -397,7 +392,7 @@ int EulerUtility::digitalRoot(int n)
return digitalRoot(digitSum);
return digitSum;
-}*/
+}
std::vector<int> EulerUtility::intersect(std::vector<int>& a, std::vector<int>& b)
{
diff --git a/EulerUtility.h b/EulerUtility.h
@@ -3,11 +3,13 @@
#include <string>
#include <vector>
-//#include "BigIntegerLibrary.hh"
+#include <boost/multiprecision/cpp_int.hpp>
typedef long long unsigned int llui;
typedef long long int ll;
+using namespace boost::multiprecision;
+
class EulerUtility
{
public:
@@ -20,24 +22,24 @@ public:
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 cpp_int bigFactorial(cpp_int n);
+ static cpp_int 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 std::vector<int> BigIntToDigits(cpp_int 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 isPrime(cpp_int& 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 cpp_int power(cpp_int i, int p);
static int digitalRoot(int n);
- //static int digitalRoot(BigInteger n);
+ static int digitalRoot(cpp_int 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);
diff --git a/Euler_15.cpp b/Euler_15.cpp
@@ -0,0 +1,6 @@
+#include "Euler.h"
+
+cpp_int Euler::LatticePaths()
+{
+ return EulerUtility::choose(40,20);
+}+
No newline at end of file
diff --git a/Euler_26.cpp b/Euler_26.cpp
@@ -0,0 +1,27 @@
+#include "Euler.h"
+
+int Euler::ReciprocalCycles()
+{
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(1000);
+
+ for (int j = primes.size() - 1; j >= 0; --j)
+ {
+ bool highestReciprocalCycle = true;
+
+ for (int i = 1; i < primes[j]; ++i)
+ {
+ cpp_int bi = EulerUtility::power(10, i);
+
+ if (((bi % primes[j] == 1) && (i != (primes[j] - 1))) || ((bi % primes[j] != 1) && (i == (primes[j] - 1))))
+ {
+ highestReciprocalCycle = false;
+ break;
+ }
+ }
+
+ if (highestReciprocalCycle)
+ return primes[j];
+ }
+
+ return 0;
+}+
No newline at end of file
diff --git a/Euler_43.cpp b/Euler_43.cpp
@@ -0,0 +1,53 @@
+#include <algorithm>
+#include <numeric>
+
+#include "Euler.h"
+
+void recursePermutations(std::string ¤t, std::vector<llui> &dps, std::vector<std::vector<std::string>> &psl, int pos)
+{
+ for (std::string s : psl[pos])
+ if (s.substr(1, 2) == current.substr(0, 2))
+ {
+ if (current.find(s.substr(0, 1)) == std::string::npos)
+ {
+ std::string concat = s.substr(0, 1) + current;
+
+ if (pos == 0)
+ dps.push_back(EulerUtility::digitsTollui(concat));
+ else
+ recursePermutations(concat, dps, psl, pos - 1);
+ }
+ }
+}
+
+void findDivisiblePermutations(std::vector<llui> &dps, std::vector<std::vector<std::string>> &psl, int pos)
+{
+ for (std::string s : psl[pos])
+ recursePermutations(s, dps, psl, pos - 1);
+
+ for (unsigned i = 0; i < dps.size(); ++i)
+ for (int j = 0; j <= 9; ++j)
+ if (std::to_string(dps[i]).find(std::to_string(j)) == std::string::npos)
+ dps[i] = EulerUtility::digitsTollui(std::to_string(j) + std::to_string(dps[i]));
+}
+
+cpp_int Euler::SubStringDivisibility()
+{
+ std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(18);
+ std::vector<std::vector<std::string>> potentialSubLex(7, std::vector<std::string>());
+ std::vector<llui> divisiblePermutations;
+
+ for (int i = 0; i < 7; ++i)
+ for (int j = 12; j <= 987; ++j)
+ if ((j % primes[i] == 0) && (EulerUtility::hasUniqueDigits(j, true)))
+ potentialSubLex[i].push_back(((j < 100) ? "0" : "") + std::to_string(j));
+
+ findDivisiblePermutations(divisiblePermutations, potentialSubLex, 6);
+
+ cpp_int i = 0;
+
+ for (uint64_t ul : divisiblePermutations)
+ i += ul;
+
+ return i;
+}+
No newline at end of file
diff --git a/Euler_48.cpp b/Euler_48.cpp
@@ -0,0 +1,11 @@
+#include "Euler.h"
+
+cpp_int Euler::SelfPowers()
+{
+ cpp_int i;
+
+ for (int j = 1; j <= 1000; ++j)
+ i += EulerUtility::power(j, j);
+
+ return i;
+}+
No newline at end of file
diff --git a/bigint/Euler_53.cpp b/Euler_53.cpp
diff --git a/Euler_55.cpp b/Euler_55.cpp
@@ -0,0 +1,53 @@
+#include <sstream>
+
+#include "Euler.h"
+
+bool isPalindrome(cpp_int i)
+{
+ std::ostringstream oss;
+ oss << i;
+
+ std::string temp = oss.str();
+
+ for (unsigned int j = 0; j < temp.length() / 2 + 1; ++j)
+ if (temp.at(j) != temp.at(temp.length() - 1 - j))
+ return false;
+
+ return true;
+}
+
+cpp_int reverse(cpp_int i)
+{
+ cpp_int reverse = 0;
+
+ while(i > 0)
+ {
+ reverse = reverse * 10 + (i % 10);
+ i /= 10;
+ }
+
+ return reverse;
+}
+
+cpp_int Euler::LychrelNumbers()
+{
+ int lychel = 9999;
+
+ for (int i = 1; i < 10000; ++i)
+ {
+ cpp_int current(i);
+
+ for (int j = 0; j < 50; ++j)
+ {
+ current = current + reverse(current);
+
+ if (isPalindrome(current))
+ {
+ --lychel;
+ break;
+ }
+ }
+ }
+
+ return lychel;
+}+
No newline at end of file
diff --git a/Euler_57.cpp b/Euler_57.cpp
@@ -0,0 +1,19 @@
+#include "Euler.h"
+
+int Euler::SquareRootConvergents()
+{
+ cpp_int n = 3, d = 2;
+ int count = 0;
+
+ for (int i = 1; i < 1000; ++i)
+ {
+ n += d;
+ std::swap(n, d);
+ n += d;
+
+ if (EulerUtility::BigIntToDigits(n).size() > EulerUtility::BigIntToDigits(d).size())
+ ++count;
+ }
+
+ return count;
+}+
No newline at end of file
diff --git a/Euler_63.cpp b/Euler_63.cpp
@@ -0,0 +1,23 @@
+#include "Euler.h"
+
+int Euler::PowerfulDigitCounts()
+{
+ int count = 0;
+
+ for (cpp_int i = 1; i < 10; ++i)
+ {
+ for (int p = 1;; ++p)
+ {
+ if (EulerUtility::BigIntToDigits(EulerUtility::power(i, p)).size() == p)
+ {
+ ++count;
+ }
+ else
+ {
+ break;
+ }
+ }
+ }
+
+ return count;
+}+
No newline at end of file
diff --git a/Euler_65.cpp b/Euler_65.cpp
@@ -0,0 +1,58 @@
+#include <numeric>
+
+#include "Euler.h"
+
+std::vector<cpp_int> recurseFraction2(std::vector<cpp_int> period, cpp_int n, std::vector<cpp_int> fraction)
+{
+ if (n > period.size() - 1)
+ return fraction;
+
+ std::swap(fraction[0], fraction[1]);
+
+ fraction[0] = (fraction[1] * period[period.size() - n - 1]) + fraction[0];
+
+ return recurseFraction2(period, n + 1, fraction);
+}
+
+std::vector<cpp_int> recurseFraction2(std::vector<cpp_int> period, cpp_int n)
+{
+ std::vector<cpp_int> fraction;
+
+ fraction.push_back(period[period.size() - 1]);
+ fraction.push_back(1);
+
+ return recurseFraction2(period, 1, fraction);
+}
+
+cpp_int periodiuy()
+{
+ std::vector<cpp_int> 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<cpp_int> approx = recurseFraction2(period, 0);
+ return approx[0];
+}
+
+int Euler::ConvergentsOfE()
+{
+ std::vector<int> digits = EulerUtility::BigIntToDigits(periodiuy());
+
+ return std::accumulate(digits.begin(), digits.end(), 0);
+}
diff --git a/Euler_66.cpp b/Euler_66.cpp
@@ -0,0 +1,74 @@
+#include "Euler.h"
+
+bool valueOfDiophantine(cpp_int x, cpp_int y, cpp_int n)
+{
+ return EulerUtility::power(x, 2) - (n * EulerUtility::power(y, 2)) == cpp_int(1);
+}
+
+std::vector<cpp_int> recurseFraction(std::vector<cpp_int> period, cpp_int n, std::vector<cpp_int> fraction)
+{
+ if (n > period.size() - 1)
+ return fraction;
+
+ std::swap(fraction[0], fraction[1]);
+
+ fraction[0] = (fraction[1] * period[period.size() - n.toInt() - 1]) + fraction[0];
+
+ return recurseFraction(period, n + 1, fraction);
+}
+
+std::vector<cpp_int> recurseFraction(std::vector<cpp_int> period, cpp_int n)
+{
+ std::vector<cpp_int> fraction;
+
+ fraction.push_back(period[period.size() - 1]);
+ fraction.push_back(1);
+
+ return recurseFraction(period, 1, fraction);
+}
+
+cpp_int valueOfX(cpp_int n)
+{
+ double n2 = std::sqrtl(n.toInt());
+ cpp_int a = (int)n2, p = 0, q = 1;
+
+ std::vector<cpp_int> period;
+ std::vector<cpp_int> approx;
+
+ period.push_back(a);
+
+ do
+ {
+ p = a * q - p;
+ q = ( n - p * p ) / q;
+ a = (long)(( p.toLong() + n2 ) /q.toLong());
+
+ period.push_back(a);
+ approx = recurseFraction(period, 0);
+
+ } while (valueOfDiophantine(approx[0], approx[1], n) != 1);
+
+ return approx[0];
+}
+
+int Euler::Diophantine()
+{
+ cpp_int currentMax = 0;
+ int valueOfD = 0;
+
+ for (int i = 2; i <= 1000; ++i)
+ {
+ if (!EulerUtility::isPerfectSquare(i))
+ {
+ cpp_int x = valueOfX(i);
+
+ if (x > currentMax)
+ {
+ currentMax = x;
+ valueOfD = i;
+ }
+ }
+ }
+
+ return valueOfD;
+}
diff --git a/Euler_78.cpp b/Euler_78.cpp
@@ -0,0 +1,60 @@
+#include "Euler.h"
+
+cpp_int partition(cpp_int &n, std::vector<cpp_int> &cache)
+{
+ cpp_int p = 0;
+
+ if (n >= 0)
+ {
+ if (n == 0 || n == 1)
+ {
+ return 1;
+ }
+ if (cache[n.toInt() - 1] != 0)
+ {
+ return cache[n.toInt() - 1];
+ }
+
+ int k = 1;
+
+ cpp_int s1 = 0;
+ cpp_int s2 = 0;
+
+ while (n - s2 >= 0)
+ {
+ s1 = (k * (3 * k - 1)) / 2;
+ s2 = (k * (3 * k + 1)) / 2;
+
+ cpp_int sign = (k - 1) & 1 ? -1 : 1;
+
+ p += sign * partition(n - s1, cache);
+ p += sign * partition(n - s2, cache);
+ ++k;
+ }
+
+ cache[n.toInt() - 1] = p;
+ }
+
+ return p;
+}
+
+llui Euler::CoinPartitions()
+{
+ int ceiling = 100000;
+ std::vector<cpp_int> cache(ceiling, 0);
+
+ for (int i = 1; i < ceiling; ++i)
+ {
+ if ((i - 4) % 5 == 0)
+ {
+ cpp_int n = partition(cpp_int(i), cache);
+
+ if (n % 1000000 == 0)
+ {
+ return i;
+ }
+ }
+ }
+
+ return 0;
+}+
No newline at end of file
diff --git a/Makefile b/Makefile
@@ -5,12 +5,12 @@ DEPS = Euler.h EulerUtility.h $(BOOST)
ODIR = obj
_OBJ = main.o
Euler_1.o Euler_2.o Euler_3.o Euler_4.o Euler_5.o Euler_6.o Euler_7.o Euler_8.o Euler_9.o Euler_10.o
- Euler_11.o Euler_12.o Euler_13.o Euler_14.o Euler_16.o Euler_17.o Euler_18.o Euler_19.o Euler_20.o
- Euler_21.o Euler_22.o Euler_23.o Euler_24.o Euler_25.o Euler_27.o Euler_28.o Euler_29.o Euler_30.o
+ Euler_11.o Euler_12.o Euler_13.o Euler_14.o Euler_15.o Euler_16.o Euler_17.o Euler_18.o Euler_19.o Euler_20.o
+ Euler_21.o Euler_22.o Euler_23.o Euler_24.o Euler_25.o Euler_26.o Euler_27.o Euler_28.o Euler_29.o Euler_30.o
Euler_31.o Euler_32.o Euler_33.o Euler_34.o Euler_35.o Euler_36.o Euler_37.o Euler_38.o Euler_39.o Euler_40.o
- Euler_41.o Euler_42.o Euler_44.o Euler_45.o Euler_46.o Euler_47.o Euler_49.o Euler_50.o
- Euler_51.o Euler_52.o Euler_54.o Euler_56.o Euler_58.o Euler_59.o Euler_60.o
- Euler_61.o Euler_62.o Euler_64.o Euler_68.o Euler_69.o Euler_70.o
+ Euler_41.o Euler_42.o Euler_43.o Euler_44.o Euler_45.o Euler_46.o Euler_47.o Euler_48.o Euler_49.o Euler_50.o
+ Euler_51.o Euler_52.o Euler_53.o Euler_54.o Euler_55.o Euler_56.o Euler_57.o Euler_58.o Euler_59.o Euler_60.o
+ Euler_61.o Euler_62.o Euler_63.o Euler_64.o Euler_68.o Euler_69.o Euler_70.o
Euler_71.o Euler_72.o Euler_73.o Euler_74.o Euler_75.o Euler_76.o Euler_77.o Euler_79.o Euler_80.o
Euler_87.o
EulerUtility.o
diff --git a/bigint/Euler_15.cpp b/bigint/Euler_15.cpp
@@ -1,6 +0,0 @@
-#include "Euler.h"
-
-BigInteger Euler::LatticePaths()
-{
- return EulerUtility::choose(40,20);
-}-
No newline at end of file
diff --git a/bigint/Euler_26.cpp b/bigint/Euler_26.cpp
@@ -1,27 +0,0 @@
-#include "Euler.h"
-
-int Euler::ReciprocalCycles()
-{
- std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(1000);
-
- for (int j = primes.size() - 1; j >= 0; --j)
- {
- bool highestReciprocalCycle = true;
-
- for (int i = 1; i < primes[j]; ++i)
- {
- BigInteger bi = EulerUtility::power(10, i);
-
- if (((bi % primes[j] == 1) && (i != (primes[j] - 1))) || ((bi % primes[j] != 1) && (i == (primes[j] - 1))))
- {
- highestReciprocalCycle = false;
- break;
- }
- }
-
- if (highestReciprocalCycle)
- return primes[j];
- }
-
- return 0;
-}-
No newline at end of file
diff --git a/bigint/Euler_43.cpp b/bigint/Euler_43.cpp
@@ -1,53 +0,0 @@
-#include <algorithm>
-#include <numeric>
-
-#include "Euler.h"
-
-void recursePermutations(std::string ¤t, std::vector<llui> &dps, std::vector<std::vector<std::string>> &psl, int pos)
-{
- for (std::string s : psl[pos])
- if (s.substr(1, 2) == current.substr(0, 2))
- {
- if (current.find(s.substr(0, 1)) == std::string::npos)
- {
- std::string concat = s.substr(0, 1) + current;
-
- if (pos == 0)
- dps.push_back(EulerUtility::digitsTollui(concat));
- else
- recursePermutations(concat, dps, psl, pos - 1);
- }
- }
-}
-
-void findDivisiblePermutations(std::vector<llui> &dps, std::vector<std::vector<std::string>> &psl, int pos)
-{
- for (std::string s : psl[pos])
- recursePermutations(s, dps, psl, pos - 1);
-
- for (unsigned i = 0; i < dps.size(); ++i)
- for (int j = 0; j <= 9; ++j)
- if (std::to_string(dps[i]).find(std::to_string(j)) == std::string::npos)
- dps[i] = EulerUtility::digitsTollui(std::to_string(j) + std::to_string(dps[i]));
-}
-
-BigInteger Euler::SubStringDivisibility()
-{
- std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(18);
- std::vector<std::vector<std::string>> potentialSubLex(7, std::vector<std::string>());
- std::vector<llui> divisiblePermutations;
-
- for (int i = 0; i < 7; ++i)
- for (int j = 12; j <= 987; ++j)
- if ((j % primes[i] == 0) && (EulerUtility::hasUniqueDigits(j, true)))
- potentialSubLex[i].push_back(((j < 100) ? "0" : "") + std::to_string(j));
-
- findDivisiblePermutations(divisiblePermutations, potentialSubLex, 6);
-
- BigInteger i = 0;
-
- for (uint64_t ul : divisiblePermutations)
- i += ul;
-
- return i;
-}-
No newline at end of file
diff --git a/bigint/Euler_48.cpp b/bigint/Euler_48.cpp
@@ -1,11 +0,0 @@
-#include "Euler.h"
-
-BigInteger Euler::SelfPowers()
-{
- BigInteger i;
-
- for (int j = 1; j <= 1000; ++j)
- i += EulerUtility::power(j, j);
-
- return i;
-}-
No newline at end of file
diff --git a/bigint/Euler_55.cpp b/bigint/Euler_55.cpp
@@ -1,53 +0,0 @@
-#include <sstream>
-
-#include "Euler.h"
-
-bool isPalindrome(BigInteger i)
-{
- std::ostringstream oss;
- oss << i;
-
- std::string temp = oss.str();
-
- for (unsigned int j = 0; j < temp.length() / 2 + 1; ++j)
- if (temp.at(j) != temp.at(temp.length() - 1 - j))
- return false;
-
- return true;
-}
-
-BigInteger reverse(BigInteger i)
-{
- BigInteger reverse = 0;
-
- while(i > 0)
- {
- reverse = reverse * 10 + (i % 10);
- i /= 10;
- }
-
- return reverse;
-}
-
-BigInteger Euler::LychrelNumbers()
-{
- int lychel = 9999;
-
- for (int i = 1; i < 10000; ++i)
- {
- BigInteger current(i);
-
- for (int j = 0; j < 50; ++j)
- {
- current = current + reverse(current);
-
- if (isPalindrome(current))
- {
- --lychel;
- break;
- }
- }
- }
-
- return lychel;
-}-
No newline at end of file
diff --git a/bigint/Euler_57.cpp b/bigint/Euler_57.cpp
@@ -1,19 +0,0 @@
-#include "Euler.h"
-
-int Euler::SquareRootConvergents()
-{
- BigInteger n = 3, d = 2;
- int count = 0;
-
- for (int i = 1; i < 1000; ++i)
- {
- n += d;
- std::swap(n, d);
- n += d;
-
- if (EulerUtility::BigIntToDigits(n).size() > EulerUtility::BigIntToDigits(d).size())
- ++count;
- }
-
- return count;
-}-
No newline at end of file
diff --git a/bigint/Euler_63.cpp b/bigint/Euler_63.cpp
@@ -1,23 +0,0 @@
-#include "Euler.h"
-
-int Euler::PowerfulDigitCounts()
-{
- int count = 0;
-
- for (BigInteger i = 1; i < 10; ++i)
- {
- for (int p = 1;; ++p)
- {
- if (EulerUtility::BigIntToDigits(EulerUtility::power(i, p)).size() == p)
- {
- ++count;
- }
- else
- {
- break;
- }
- }
- }
-
- return count;
-}-
No newline at end of file
diff --git a/bigint/Euler_65.cpp b/bigint/Euler_65.cpp
@@ -1,58 +0,0 @@
-#include <numeric>
-
-#include "Euler.h"
-
-std::vector<BigInteger> recurseFraction2(std::vector<BigInteger> period, BigInteger n, std::vector<BigInteger> fraction)
-{
- if (n > period.size() - 1)
- return fraction;
-
- std::swap(fraction[0], fraction[1]);
-
- fraction[0] = (fraction[1] * period[period.size() - n.toInt() - 1]) + fraction[0];
-
- return recurseFraction2(period, n + 1, fraction);
-}
-
-std::vector<BigInteger> recurseFraction2(std::vector<BigInteger> period, BigInteger n)
-{
- std::vector<BigInteger> fraction;
-
- fraction.push_back(period[period.size() - 1]);
- fraction.push_back(1);
-
- return recurseFraction2(period, 1, fraction);
-}
-
-BigInteger periodiuy()
-{
- std::vector<BigInteger> period;
-
- period.push_back(2);
-
- int n = 2;
-
- for (int i = 1; i < 100; ++i)
- {
- if (i % 3 == 2)
- {
- period.push_back(n);
- n += 2;
- }
- else
- {
- period.push_back(1);
- }
- }
-
-
- std::vector<BigInteger> approx = recurseFraction2(period, 0);
- return approx[0];
-}
-
-int Euler::ConvergentsOfE()
-{
- std::vector<int> digits = EulerUtility::BigIntToDigits(periodiuy());
-
- return std::accumulate(digits.begin(), digits.end(), 0);
-}
diff --git a/bigint/Euler_66.cpp b/bigint/Euler_66.cpp
@@ -1,74 +0,0 @@
-#include "Euler.h"
-
-bool valueOfDiophantine(BigInteger x, BigInteger y, BigInteger n)
-{
- return EulerUtility::power(x, 2) - (n * EulerUtility::power(y, 2)) == BigInteger(1);
-}
-
-std::vector<BigInteger> recurseFraction(std::vector<BigInteger> period, BigInteger n, std::vector<BigInteger> fraction)
-{
- if (n > period.size() - 1)
- return fraction;
-
- std::swap(fraction[0], fraction[1]);
-
- fraction[0] = (fraction[1] * period[period.size() - n.toInt() - 1]) + fraction[0];
-
- return recurseFraction(period, n + 1, fraction);
-}
-
-std::vector<BigInteger> recurseFraction(std::vector<BigInteger> period, BigInteger n)
-{
- std::vector<BigInteger> fraction;
-
- fraction.push_back(period[period.size() - 1]);
- fraction.push_back(1);
-
- return recurseFraction(period, 1, fraction);
-}
-
-BigInteger valueOfX(BigInteger n)
-{
- double n2 = std::sqrtl(n.toInt());
- BigInteger a = (int)n2, p = 0, q = 1;
-
- std::vector<BigInteger> period;
- std::vector<BigInteger> approx;
-
- period.push_back(a);
-
- do
- {
- p = a * q - p;
- q = ( n - p * p ) / q;
- a = (long)(( p.toLong() + n2 ) /q.toLong());
-
- period.push_back(a);
- approx = recurseFraction(period, 0);
-
- } while (valueOfDiophantine(approx[0], approx[1], n) != 1);
-
- return approx[0];
-}
-
-int Euler::Diophantine()
-{
- BigInteger currentMax = 0;
- int valueOfD = 0;
-
- for (int i = 2; i <= 1000; ++i)
- {
- if (!EulerUtility::isPerfectSquare(i))
- {
- BigInteger x = valueOfX(i);
-
- if (x > currentMax)
- {
- currentMax = x;
- valueOfD = i;
- }
- }
- }
-
- return valueOfD;
-}
diff --git a/bigint/Euler_78.cpp b/bigint/Euler_78.cpp
@@ -1,60 +0,0 @@
-#include "Euler.h"
-
-BigInteger partition(BigInteger &n, std::vector<BigInteger> &cache)
-{
- BigInteger p = 0;
-
- if (n >= 0)
- {
- if (n == 0 || n == 1)
- {
- return 1;
- }
- if (cache[n.toInt() - 1] != 0)
- {
- return cache[n.toInt() - 1];
- }
-
- int k = 1;
-
- BigInteger s1 = 0;
- BigInteger s2 = 0;
-
- while (n - s2 >= 0)
- {
- s1 = (k * (3 * k - 1)) / 2;
- s2 = (k * (3 * k + 1)) / 2;
-
- BigInteger sign = (k - 1) & 1 ? -1 : 1;
-
- p += sign * partition(n - s1, cache);
- p += sign * partition(n - s2, cache);
- ++k;
- }
-
- cache[n.toInt() - 1] = p;
- }
-
- return p;
-}
-
-llui Euler::CoinPartitions()
-{
- int ceiling = 100000;
- std::vector<BigInteger> cache(ceiling, 0);
-
- for (int i = 1; i < ceiling; ++i)
- {
- if ((i - 4) % 5 == 0)
- {
- BigInteger n = partition(BigInteger(i), cache);
-
- if (n % 1000000 == 0)
- {
- return i;
- }
- }
- }
-
- return 0;
-}-
No newline at end of file
diff --git a/main.cpp b/main.cpp
@@ -21,8 +21,7 @@ int main() {
std::cout << e.TriangleNoWithGreaterThan500Divisors() << std::endl;
std::cout << e.LargeSum() << std::endl;
std::cout << e.CollatzConjecture() << std::endl;
- std::cout << "(skipped)" << std::endl;
- //std::cout << e.LatticePaths() << std::endl;
+ std::cout << e.LatticePaths() << std::endl;
std::cout << e.DigitSum() << std::endl;
std::cout << e.LetterCounter() << std::endl;
std::cout << e.MaximumPathSum() << std::endl;
@@ -33,8 +32,7 @@ int main() {
std::cout << e.NonAbundantSums() << std::endl;
std::cout << e.LexicographicPermutations() << std::endl;
std::cout << e.ThousandDigitFibonacciNumber() << std::endl;
- std::cout << "(skipped)" << std::endl;
- //std::cout << e.ReciprocalCycles() << std::endl;
+ std::cout << e.ReciprocalCycles() << std::endl;
std::cout << e.QuadraticPrimes() << std::endl;
std::cout << e.SpiralDiagonals() << std::endl;
std::cout << e.DistinctPowers() << std::endl;
@@ -51,33 +49,27 @@ int main() {
std::cout << e.ChampernowneConstant() << std::endl;
std::cout << e.PanDigitalPrime() << std::endl;
std::cout << e.CodedTriangleNumbers() << std::endl; //wrong
- std::cout << "(skipped)" << std::endl;
- //std::cout << e.SubStringDivisibility() << std::endl;
+ std::cout << e.SubStringDivisibility() << std::endl;
std::cout << e.MinimizedPentagonalDifference() << std::endl;
std::cout << e.TriangularPentagonalHexagonal() << std::endl;
std::cout << e.GoldbachsOtherConjecture() << std::endl;
std::cout << e.DistinctPrimeFactors() << std::endl;
- std::cout << "(skipped)" << std::endl;
- //std::cout << e.SelfPowers() << std::endl;
+ std::cout << e.SelfPowers() << std::endl;
std::cout << e.PrimePermutations() << std::endl;
std::cout << e.ConsecutivePrimeSum() << std::endl;
std::cout << e.PrimeDigitReplacements() << std::endl;
std::cout << e.PermutedMultiples() << std::endl;
- std::cout << "(skipped)" << std::endl;
- //std::cout << e.CombinatoricSelections() << std::endl;
+ std::cout << e.CombinatoricSelections() << std::endl;
std::cout << e.PokerHands() << std::endl;
- std::cout << "(skipped)" << std::endl;
- //std::cout << e.LychrelNumbers() << std::endl;
+ std::cout << e.LychrelNumbers() << std::endl;
std::cout << e.PowerfulDigitSum() << std::endl;
- std::cout << "(skipped)" << std::endl;
- //std::cout << e.SquareRootConvergents() << std::endl;
+ std::cout << e.SquareRootConvergents() << std::endl;
std::cout << e.SpiralPrimes() << std::endl;
std::cout << e.xorDecryption() << std::endl; //wrong
std::cout << e.PrimePairSets() << std::endl;
std::cout << e.CyclicFigurateNumbers() << std::endl;
std::cout << e.CubicPermutations() << std::endl;
- std::cout << "(skipped)" << std::endl;
- //std::cout << e.PowerfulDigitCounts() << std::endl;
+ std::cout << e.PowerfulDigitCounts() << std::endl;
std::cout << e.OddPeriodSquareRoots() << std::endl;
std::cout << "(skipped)" << std::endl;
//std::cout << e.ConvergentsOfE() << std::endl;
@@ -91,13 +83,11 @@ int main() {
std::cout << e.CountingRangedFractions() << std::endl;
std::cout << e.DigitFactorialChains() << std::endl;
std::cout << e.UniquePerimeterRightAngledTriangles() << std::endl;
- std::cout << "(skipped)" << std::endl;
- //std::cout << e.CountingSums() << std::endl;
+ std::cout << e.CountingSums() << std::endl;
std::cout << e.PrimeSummations() << std::endl;
std::cout << "(skipped)" << std::endl;
//std::cout << e.CoinPartitions() << std::endl;
std::cout << e.PasscodeDerivation() << std::endl; //wrong
- std::cout << "(skipped)" << std::endl;
std::cout << e.SquareRootDigitalExpansion() << std::endl;
std::cout << e.PrimePowerTriples() << std::endl;
