Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 09:43, 2 May 2021
, 3 years agoC++ code modified to use a fraction type
(Added Wren) |
m (C++ code modified to use a fraction type) |
||
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 ⟶ 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 ⟶ 484:
}
std::string
const int max_digits = 20;
std::ostringstream os;
Line 488 ⟶ 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);
}
result.clear();
integer x = f.numerator, y = f.denominator;
while (x > 0) {
integer z = (y + x - 1)/x;
result.
x = mod(-y, x);
y = y * z;
Line 498 ⟶ 510:
}
void print_egyptian(const std::vector<
if (result.empty())
return;
auto i = result.begin();
std::cout <<
for (; i != result.end(); ++i)
std::cout << " +
std::cout <<
}
void print_egyptian(
std::cout << "Egyptian fraction for " <<
integer x = f.numerator, y = f.denominator;
if (x > y) {
std::cout << "[" << x/y << "] ";
x = x % y;
}
std::vector<
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;
▲ std::vector<integer> max_terms_result;
integer max_denominator = 0;
std::vector<
std::vector<
for (integer b = 2; b < limit; ++b) {
for (integer a = 1; a < b; ++a) {
egyptian(f, result);
if (result.size() > max_terms) {
max_terms = result.size();
max_terms_result = result;
}
const integer&
if (
max_denominator =
max_denominator_result = result;
}
}
}
std::cout << "Proper fractions with most terms and largest denominator, limit = " << limit << ":\n\n";
std::cout << "Most terms (" << max_terms << "): " <<
print_egyptian(max_terms_result);
std::cout << "
<<
print_egyptian(max_denominator_result);
}
int main() {
print_egyptian(fraction(43, 48));
print_egyptian(fraction(5, 121));
print_egyptian(fraction(2014, 59));
show_max_terms_and_max_denominator(100);
show_max_terms_and_max_denominator(1000);
Line 576 ⟶ 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 ⟶ 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>
| |||