Euler_100.cpp (2609B)
1 #include "Euler.h" 2 3 // (15 / 21) * (14 / 20) = 1 / 2 4 // (5 / 7) * (7 / 10) = 1 / 2 5 // x = 3, y = 2, a = 5, b = 7 all primes? 6 // (a / b) * (b / 2a) = 1 / 2 7 // 8 // solution = min(x * a) where x * b > 10^12 9 // and x * b = (y * 2a) + 1 10 // and (a / b) * (b / 2a) = 1 / 2 11 // or bx = 2ay + 1 12 // 13 // ((a * x) / (b * x)) * ((b * y) / (2 * a * y)) = 1 / 2 14 // (a * x) / (b * x) = 1 / (2 * ((b * y) / (2 * a * y))) 15 // b * x = (a * x) / (1 / (2 * ((b * y) / (2 * a * y)))) 16 17 // sub x * b = (y * 2a) + 1 18 // (y * 2 * a) + 1 = (a * x) / (1 / (2 * ((b * y) / (2 * a * y)))) 19 // (y * 2 * a) + 1 = (a * x) / (1 / (2 * (b / (2 * a)))) 20 // (y * 2 * a) + 1 = (a * x) / (1 / (b / a)) 21 // (y * 2 * a) + 1 = (a * x) / (a / b)) 22 // (y * 2 * a) + 1 = b * x // lol, ok different approach 23 24 // ((a * x) / (b * x)) * (((a * x) - 1) / ((b * x) - 1)) = 1 / 2 25 // (a / b) * (((a * x) - 1) / ((b * x) - 1)) = 1 / 2 26 // ((a * ((a * x) - 1)) / (b * ((b * x) - 1))) = 1 / 2 27 // ((((a ^ 2) * x) - a) / (((b ^ 2) * x) - b)) = 1 / 2 28 29 // a < b 30 // 31 // (85 / 120) * (84 / 119) = 1 / 2 32 // (17 / 24) * (12 / 17) = 1 / 2 33 // (a / 2b) * (b / a) = 1 / 2 34 // x = 5, y = 7, a = 17, b = 12 (x and y always prime? co-prime?) 35 // 36 // a > b 37 // 38 // solution = min(x * a) where x * 2b > 10^12 39 // and x * 2b = (y * a) + 1 40 // or 2bx = ay + 1 41 // 42 // can I derive x * a in terms of anything? 43 // I doubt it unless we make some assumptions about the relationship between x and y 44 // (e.g. assume they are always contiguous primes) 45 // 46 // lets say 47 // x = 11, y = 13 48 // there may be a solution for either 49 // 11b = 26a + 1 50 // 22b = 13a + 1 51 // b = (26a + 1) / 11 e.g. if 26a + 1 % 11 == 0 then we have a, plug back in a to get b 52 // found a solution a = 8, b = 19 53 // therefore 11 * 8 / 11 * 19 is a valid solution? apparently not. 54 // found a solution a = 690, b = 1631 55 // is 11 * 690 / 11 * 1631 a valid solution? nope. lets try the other equation 56 // b = (13a + 1) / 22 e.g. if (13a + 1) % 22 == 0 then we have a, plug back in a to get b 57 // found a solution a = 5, b = 6 58 // is (11 * 5) / (2 * 11 * 6) a solution? I can already see it's going to be less than 1/2. 59 // found a solution a = 995, b = 1176 60 // "((11 * 995) / (2 * 11 * 1176)) * (((11 * 995) - 1) / ((2 * 11 * 1176) - 1))" = .17895697570126191251 61 // 62 // this doesn't seem to be a good way of identifying solutions without more constraints. 63 // time for wikipedia 64 65 uint64_t Euler::ArrangedProbability() 66 { 67 std::vector<int> a; 68 std::vector<int> b; 69 70 for (int i = 0; i < 1000; ++i) { 71 if (((13 * i) + 1) % 22 == 0) { 72 a.push_back(i); 73 b.push_back(((13 * i) + 1) / 22); 74 } 75 } 76 77 return 0; 78 }