Greedy algorithm for Egyptian fractions: Difference between revisions

Content added Content deleted
m (C++ solution writes out numerator and denominator for Egyptian fractions with most terms/largest denominator)
Line 202: Line 202:
=={{header|C++}}==
=={{header|C++}}==
The C++ standard library does not have a "big integer" type, so this solution uses the Boost library.
The C++ standard library does not have a "big integer" type, so this solution uses the Boost library.
<lang cpp>#include <iostream>
<lang cpp><lang cpp>#include <iostream>
#include <vector>
#include <vector>
#include <algorithm>
#include <string>
#include <string>
#include <sstream>
#include <sstream>
#include <set>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_int.hpp>


typedef boost::multiprecision::cpp_int integer;
typedef boost::multiprecision::cpp_int integer;

struct rational
{
integer numerator_;
integer denominator_;
rational(const integer& n, const integer& d) : numerator_(n), denominator_(d)
{
}
⚫
};

std::ostream& operator<<(std::ostream& os, const rational& r)
{
os << r.numerator_ << '/' << r.denominator_;
return os;
}

bool operator<(const rational& a, const rational& b)
{
return a.numerator_ * b.denominator_ < b.numerator_ * a.denominator_;
}


integer mod(const integer& x, const integer& y)
integer mod(const integer& x, const integer& y)
Line 235: Line 257:
}
}


void egyptian(integer x, integer y, std::vector<integer>& result)
std::vector<integer> egyptian(integer x, integer y)
{
{
result.clear();
std::vector<integer> result;
while (x > 0)
while (x > 0)
{
{
Line 245: Line 267:
y = y * z;
y = y * z;
}
}
⚫
return result;
}
}


Line 266: Line 289:
x = x % y;
x = x % y;
}
}
std::vector<integer> result;
std::vector<integer> result(egyptian(x ,y));
⚫
egyptian(x ,y, result);
print_egyptian(result);
print_egyptian(result);
}
}
Line 274: Line 296:
{
{
size_t max_terms = 0;
size_t max_terms = 0;
integer max_terms_numerator, max_terms_denominator;
integer max_denominator_numerator, max_denominator_denominator;
std::vector<integer> max_terms_result;
std::vector<integer> max_terms_result;
integer max_denominator = 0;
integer max_denominator = 0;
std::vector<integer> max_denominator_result;
std::vector<integer> max_denominator_result;
std::vector<integer> result;
std::set<rational> fractions;
for (integer b = 2; b < limit; ++b)
for (integer b = 2; b < limit; ++b)
{
{
for (integer a = 1; a < b; ++a)
for (integer a = 1; a < b; ++a)
{
{
egyptian(a, b, result);
rational r(a, b);
if (fractions.find(r) != fractions.end())
continue;
fractions.insert(r);
std::vector<integer> result = egyptian(a, b);
if (result.size() > max_terms)
if (result.size() > max_terms)
{
{
max_terms = result.size();
max_terms = result.size();
max_terms_result = result;
max_terms_result = result;
max_terms_numerator = a;
max_terms_denominator = b;
}
}
integer largest_denominator = result.back();
integer largest_denominator = result.back();
Line 293: Line 323:
max_denominator = largest_denominator;
max_denominator = largest_denominator;
max_denominator_result = result;
max_denominator_result = result;
max_denominator_numerator = a;
max_denominator_denominator = b;
}
}
}
}
}
}
std::cout << "Proper fractions with most terms and largest denominator, limit = " << limit << ":\n\n";
std::cout << "Proper fractions with most terms and largest denominator, limit = " << limit << ":\n\n";
std::cout << "Most terms (" << max_terms << "): ";
std::cout << "Most terms (" << max_terms << "): " << max_terms_numerator
<< '/' << max_terms_denominator << " = ";
print_egyptian(max_terms_result);
print_egyptian(max_terms_result);
std::cout << "Largest denominator (" << count_digits(max_denominator) << " digits): ";
std::cout << "Largest denominator (" << count_digits(max_denominator_result.back()) << " digits): "
<< max_denominator_numerator << '/' << max_denominator_denominator << " = ";
print_egyptian(max_denominator_result);
print_egyptian(max_denominator_result);
}
}
Line 311: Line 345:
show_max_terms_and_max_denominator(1000);
show_max_terms_and_max_denominator(1000);
return 0;
return 0;
⚫
}</lang>
⚫
}

⚫
</lang>
{{out}}
{{out}}
<pre>
<pre>Egyptian fraction for 43/48: 1/2 + 1/3 + 1/16
Egyptian fraction for 43/48: 1/2 + 1/3 + 1/16


Egyptian fraction for 5/121: 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795...3418846225
Egyptian fraction for 5/121: 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795...3418846225
Line 322: Line 357:
Proper fractions with most terms and largest denominator, limit = 100:
Proper fractions with most terms and largest denominator, limit = 100:


Most terms (8): 1/2 + 1/4 + 1/13 + 1/307 + 1/120871 + 1/20453597227 + 1/6972493991...6783218655 + 1/1458470173...7836808420
Most terms (8): 44/53 = 1/2 + 1/4 + 1/13 + 1/307 + 1/120871 + 1/20453597227 + 1/6972493991...6783218655 + 1/1458470173...7836808420


Largest denominator (150 digits): 1/13 + 1/181 + 1/38041 + 1/1736503177 + 1/3769304102927363485 + 1/1894353789...8154430149 + 1/5382864419...4225813153 + 1/5795045870...3909789665
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:
Proper fractions with most terms and largest denominator, limit = 1000:


Most terms (13): 1/2 + 1/4 + 1/19 + 1/379 + 1/159223 + 1/28520799973 + 1/9296411783...1338400861 + 1/1008271507...4174730681 + 1/1219933718...8484537833 + 1/1860297848...1025882029 + 1/4614277444...8874327093 + 1/3193733450...1456418881 + 1/2039986670...2410165441
Most terms (13): 641/796 = 1/2 + 1/4 + 1/19 + 1/379 + 1/159223 + 1/28520799973 + 1/9296411783...1338400861 + 1/1008271507...4174730681 + 1/1219933718...8484537833 + 1/1860297848...1025882029 + 1/4614277444...8874327093 + 1/3193733450...1456418881 + 1/2039986670...2410165441

⚫
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


⚫
Largest denominator (2847 digits): 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>
</pre>


Retrieved from "https://rosettacode.org/wiki/Greedy_algorithm_for_Egyptian_fractions"