Greedy algorithm for Egyptian fractions: Difference between revisions

Content added Content deleted

Inline

@@ Line 460: / Line 460: @@
 The C++ standard library does not have a "big integer" type, so this solution uses the Boost library.
 <lang cpp>#include <iostream>
+#include <optional>
 #include <vector>
 #include <string>
@@ Line 466: / Line 467: @@
 typedef boost::multiprecision::cpp_int integer;
+struct fraction {
+    fraction(const integer& n, const integer& d) : numerator(n), denominator(d) {}
+    integer numerator;
+    integer denominator;
+};
 integer mod(const integer& x, const integer& y) {
@@ Line 477: / Line 484: @@
 }
-std::string integer_to_string(const integer& i) {
+std::string to_string(const integer& i) {
     const int max_digits = 20;
     std::ostringstream os;
@@ Line 488: / Line 495: @@
 }
+std::ostream& operator<<(std::ostream& out, const fraction& f) {
-void egyptian(integer x, integer y, std::vector<integer>& result) {
+    return out << to_string(f.numerator) << '/' << to_string(f.denominator);
+}
+void egyptian(const fraction& f, std::vector<fraction>& result) {
     result.clear();
+    integer x = f.numerator, y = f.denominator;
     while (x > 0) {
         integer z = (y + x - 1)/x;
-        result.push_back(z);
+        result.emplace_back(1, z);
         x = mod(-y, x);
         y = y * z;
@@ Line 498: / Line 510: @@
 }
-void print_egyptian(const std::vector<integer>& result) {
+void print_egyptian(const std::vector<fraction>& result) {
     if (result.empty())
         return;
     auto i = result.begin();
-    std::cout << "1/" << integer_to_string(*i++);
+    std::cout << *i++;
     for (; i != result.end(); ++i)
-        std::cout << " + 1/" << integer_to_string(*i);
+        std::cout << " + " << *i;
-    std::cout << "\n\n";
+    std::cout << '\n';
 }
-void print_egyptian(integer x, integer y) {
+void print_egyptian(const fraction& f) {
-    std::cout << "Egyptian fraction for " << x << "/" << y << ": ";
+    std::cout << "Egyptian fraction for " << f << ": ";
+    integer x = f.numerator, y = f.denominator;
     if (x > y) {
         std::cout << "[" << x/y << "] ";
         x = x % y;
     }
-    std::vector<integer> result;
+    std::vector<fraction> result;
-    egyptian(x, y, result);
+    egyptian(fraction(x, y), result);
     print_egyptian(result);
+    std::cout << '\n';
 }
 void show_max_terms_and_max_denominator(const integer& limit) {
     size_t max_terms = 0;
+    std::optional<fraction> max_terms_fraction, max_denominator_fraction;
-    integer max_terms_numerator, max_terms_denominator;
+    std::vector<fraction> max_terms_result;
-    integer max_denominator_numerator, max_denominator_denominator;
-    std::vector<integer> max_terms_result;
     integer max_denominator = 0;
-    std::vector<integer> max_denominator_result;
+    std::vector<fraction> max_denominator_result;
-    std::vector<integer> result;
+    std::vector<fraction> result;
     for (integer b = 2; b < limit; ++b) {
         for (integer a = 1; a < b; ++a) {
-            egyptian(a, b, result);
+            fraction f(a, b);
+            egyptian(f, result);
             if (result.size() > max_terms) {
                 max_terms = result.size();
                 max_terms_result = result;
-                max_terms_numerator = a;
+                max_terms_fraction = f;
-                max_terms_denominator = b;
             }
-            integer largest_denominator = result.back();
+            const integer& denominator = result.back().denominator;
-            if (largest_denominator > max_denominator) {
+            if (denominator > max_denominator) {
-                max_denominator = largest_denominator;
+                max_denominator = denominator;
                 max_denominator_result = result;
-                max_denominator_numerator = a;
+                max_denominator_fraction = f;
-                max_denominator_denominator = b;
             }
         }
     }
     std::cout << "Proper fractions with most terms and largest denominator, limit = " << limit << ":\n\n";
-    std::cout << "Most terms (" << max_terms << "): " << max_terms_numerator
+    std::cout << "Most terms (" << max_terms << "): " << max_terms_fraction.value() << " = ";
-        << '/' << max_terms_denominator << " = ";
     print_egyptian(max_terms_result);
-    std::cout << "Largest denominator (" << count_digits(max_denominator_result.back()) << " digits): "
+    std::cout << "\nLargest denominator (" << count_digits(max_denominator_result.back().denominator)
-        << max_denominator_numerator << '/' << max_denominator_denominator << " = ";
+        << " digits): " << max_denominator_fraction.value() << " = ";
     print_egyptian(max_denominator_result);
 }
 int main() {
-    print_egyptian(43, 48);
+    print_egyptian(fraction(43, 48));
-    print_egyptian(5, 121);
+    print_egyptian(fraction(5, 121));
-    print_egyptian(2014, 59);
+    print_egyptian(fraction(2014, 59));
     show_max_terms_and_max_denominator(100);
     show_max_terms_and_max_denominator(1000);
@@ Line 576: / Line 587: @@
 Largest denominator (150 digits): 8/97 = 1/13 + 1/181 + 1/38041 + 1/1736503177 + 1/3769304102927363485 + 1/1894353789...8154430149 + 1/5382864419...4225813153 + 1/5795045870...3909789665
 Proper fractions with most terms and largest denominator, limit = 1000:
@@ Line 582: / Line 592: @@
 Largest denominator (2847 digits): 36/457 = 1/13 + 1/541 + 1/321409 + 1/114781617793 + 1/1482167225...0844346913 + 1/2510651068...4290086881 + 1/7353930250...3326272641 + 1/6489634815...7391865217 + 1/5264420004...5476206145 + 1/3695215730...1238141889 + 1/2048192894...4706590593 + 1/8390188268...5525592705
 </pre>