commit b1fa56b363c7c8d5a5d55a85c8f987078a4572a5
parent 6267324a68f2086213eb9f70a82d65ef2d6e15e5
Author: mpizzzle <m@michaelpercival.xyz>
Date: Sun, 27 Sep 2020 20:54:14 +0100
safety commit
Diffstat:
6 files changed, 138 insertions(+), 36 deletions(-)
diff --git a/Euler.h b/Euler.h
@@ -86,4 +86,6 @@ public:
uint64_t CuboidRoute();
uint64_t AlmostEquilateralTriangles();
int AmicableChains();
+ uint64_t ArrangedProbability();
+ uint64_t CubeDigitPairs();
};
diff --git a/Euler_100.cpp b/Euler_100.cpp
@@ -0,0 +1,78 @@
+#include "Euler.h"
+
+// (15 / 21) * (14 / 20) = 1 / 2
+// (5 / 7) * (7 / 10) = 1 / 2
+// x = 3, y = 2, a = 5, b = 7 all primes?
+// (a / b) * (b / 2a) = 1 / 2
+//
+// solution = min(x * a) where x * b > 10^12
+// and x * b = (y * 2a) + 1
+// and (a / b) * (b / 2a) = 1 / 2
+// or bx = 2ay + 1
+//
+// ((a * x) / (b * x)) * ((b * y) / (2 * a * y)) = 1 / 2
+// (a * x) / (b * x) = 1 / (2 * ((b * y) / (2 * a * y)))
+// b * x = (a * x) / (1 / (2 * ((b * y) / (2 * a * y))))
+
+// sub x * b = (y * 2a) + 1
+// (y * 2 * a) + 1 = (a * x) / (1 / (2 * ((b * y) / (2 * a * y))))
+// (y * 2 * a) + 1 = (a * x) / (1 / (2 * (b / (2 * a))))
+// (y * 2 * a) + 1 = (a * x) / (1 / (b / a))
+// (y * 2 * a) + 1 = (a * x) / (a / b))
+// (y * 2 * a) + 1 = b * x // lol, ok different approach
+
+// ((a * x) / (b * x)) * (((a * x) - 1) / ((b * x) - 1)) = 1 / 2
+// (a / b) * (((a * x) - 1) / ((b * x) - 1)) = 1 / 2
+// ((a * ((a * x) - 1)) / (b * ((b * x) - 1))) = 1 / 2
+// ((((a ^ 2) * x) - a) / (((b ^ 2) * x) - b)) = 1 / 2
+
+// a < b
+//
+// (85 / 120) * (84 / 119) = 1 / 2
+// (17 / 24) * (12 / 17) = 1 / 2
+// (a / 2b) * (b / a) = 1 / 2
+// x = 5, y = 7, a = 17, b = 12 (x and y always prime? co-prime?)
+//
+// a > b
+//
+// solution = min(x * a) where x * 2b > 10^12
+// and x * 2b = (y * a) + 1
+// or 2bx = ay + 1
+//
+// can I derive x * a in terms of anything?
+// I doubt it unless we make some assumptions about the relationship between x and y
+// (e.g. assume they are always contiguous primes)
+//
+// lets say
+// x = 11, y = 13
+// there may be a solution for either
+// 11b = 26a + 1
+// 22b = 13a + 1
+// b = (26a + 1) / 11 e.g. if 26a + 1 % 11 == 0 then we have a, plug back in a to get b
+// found a solution a = 8, b = 19
+// therefore 11 * 8 / 11 * 19 is a valid solution? apparently not.
+// found a solution a = 690, b = 1631
+// is 11 * 690 / 11 * 1631 a valid solution? nope. lets try the other equation
+// b = (13a + 1) / 22 e.g. if (13a + 1) % 22 == 0 then we have a, plug back in a to get b
+// found a solution a = 5, b = 6
+// is (11 * 5) / (2 * 11 * 6) a solution? I can already see it's going to be less than 1/2.
+// found a solution a = 995, b = 1176
+// "((11 * 995) / (2 * 11 * 1176)) * (((11 * 995) - 1) / ((2 * 11 * 1176) - 1))" = .17895697570126191251
+//
+// this doesn't seem to be a good way of identifying solutions without more constraints.
+// time for wikipedia
+
+uint64_t Euler::ArrangedProbability()
+{
+ std::vector<int> a;
+ std::vector<int> b;
+
+ for (int i = 0; i < 1000; ++i) {
+ if (((13 * i) + 1) % 22 == 0) {
+ a.push_back(i);
+ b.push_back(((13 * i) + 1) / 22);
+ }
+ }
+
+ return 0;
+}
diff --git a/Euler_90.cpp b/Euler_90.cpp
@@ -0,0 +1,15 @@
+#include "Euler.h"
+
+uint64_t Euler::CubeDigitPairs()
+{
+ //std::vector<std::string> squares = { "01", "04", "09", "16", "25", "36", "49", "64", "81" };
+
+ // most important 9 / 6
+ // second most 0, 1, 4
+ // third most 2, 5, 3, 8
+ // trash 7
+ //{ 2, 1, 3, 4 }
+ //{ 5, 0, 6, 8 }
+
+ return 0;
+}
diff --git a/Euler_95.cpp b/Euler_95.cpp
@@ -17,14 +17,14 @@ int sumProperDivisors(int n)
int Euler::AmicableChains()
{
- int one_million = 200000;
+ int one_million = 100000;
int longest = 0;
int solution = 0;
- std::vector<int> divisors(one_million + 1, 0);
+ std::vector<int> cache(one_million + 1, 0);
- for (int n = 0; n <= one_million; ++n) {
- std::cout << n << std::endl;
- divisors[n] = sumProperDivisors(n);
+ for (int i = 0; i <= one_million; ++i) {
+ cache[i] = sumProperDivisors(i);
+ std::cout << i << std::endl;
}
std::cout << std::endl << "precalc done." << std::endl;
@@ -37,50 +37,55 @@ int Euler::AmicableChains()
std::cout << n << ": ";
while(true) {
- length += 1;
-
if (fast_ptr <= 1 || slow_ptr > one_million || fast_ptr > one_million) {
std::cout << "no bueno." << std::endl;
break;
}
- fast_ptr = divisors[fast_ptr];
+ fast_ptr = cache[fast_ptr];
- if (slow_ptr < candidate) {
- candidate = slow_ptr;
+ if (fast_ptr <= 1 || fast_ptr > one_million) {
+ std::cout << "no bueno." << std::endl;
+ break;
}
if (slow_ptr == fast_ptr) {
- if (length > longest) {
- solution = candidate;
- longest = length;
- std::cout << "chicken dinner!" << std::endl;
- std::cout << "current solution: " << solution << std::endl;
-
- int blerp = n;
- int fast_blerp = divisors[n];
-
- std::cout << n << " -> ";// << std::endl;
- while (blerp != fast_blerp) {
- blerp = divisors[blerp];
- fast_blerp = divisors[divisors[fast_blerp]];
- std::cout << blerp << " -> ";// << std::endl;
+ while (true) {
+ std::cout << slow_ptr << " -> ";
+ length++;
+ fast_ptr = cache[fast_ptr];
+
+ if (slow_ptr < candidate) {
+ candidate = slow_ptr;
}
- std::cout << std::endl << "current length: " << length << std::endl;
- }
- else {
- std::cout << "not a winner." << std::endl;
+ if (slow_ptr == fast_ptr) {
+ if (length > longest) {
+ solution = candidate;
+ longest = length;
+ std::cout << "chicken dinner!" << std::endl;
+ std::cout << "current solution: " << solution << std::endl;
+ std::cout << std::endl << "current length: " << length << std::endl;
+ }
+ else {
+ std::cout << "not a winner." << std::endl;
+ }
+
+ cache[solution] = 0;
+ break;
+ }
+
+ slow_ptr = cache[slow_ptr];
+ fast_ptr = cache[fast_ptr];
}
- divisors[solution] = 1;
break;
}
- slow_ptr = divisors[slow_ptr];
- fast_ptr = divisors[fast_ptr];
+ slow_ptr = cache[slow_ptr];
+ fast_ptr = cache[fast_ptr];
}
}
- return (int)solution;
+ return solution;
}
diff --git a/Makefile b/Makefile
@@ -12,8 +12,8 @@ _OBJ = main.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_86.o Euler_87.o
- Euler_94.o Euler_95.o
+ Euler_86.o Euler_87.o Euler_90.o
+ Euler_94.o Euler_95.o Euler_100.o
EulerUtility.o
OBJ = $(patsubst %,$(ODIR)/%,$(_OBJ))
diff --git a/main.cpp b/main.cpp
@@ -90,8 +90,10 @@ int main() {
//std::cout << "problem 80: " << e.SquareRootDigitalExpansion() << std::endl;
//std::cout << "problem 86: " << e.CuboidRoute() << std::endl;
//std::cout << "problem 87: " << e.PrimePowerTriples() << std::endl;
- //std::cout << "problem 94: " << e.AlmostEquilateralTriangles() << std::endl;
- std::cout << "problem 95: " << e.AmicableChains() << std::endl;
+ //std::cout << "problem 90: " << e.CubeDigitPairs() << std::endl; //in progress
+ //std::cout << "problem 94: " << e.AlmostEquilateralTriangles() << std::endl; //in progress
+ std::cout << "problem 95: " << e.AmicableChains() << std::endl; //in progress
+ //std::cout << "problem 100: " << e.ArrangedProbability() << std::endl; //in progress
std::cout << "duration: " << 1000.0 * (std::clock() - start) / CLOCKS_PER_SEC << "ms" << std::endl;
return 0;
