Two Egyptian Unit Fractions
National Olympiad — Regional round (2014 season)
Submission name: egypt.cpp
Problem summary
Find every integer solution of 1/x+1/y=1/z with 1<x<y, in increasing x order.
Input
One positive integer z.
Output
One x y pair per line, in increasing x order.
Constraints
1 < z < 1000.
Worked example
Input and output for the worked example discussed below.
Input
15
Output
16 240 18 90 20 60 24 40
Solution analysis
- Both fractions are positive, so x>z. Since x<y, 1/x+1/y<2/x, implying x<2z. There are therefore only z−1 candidate x values to inspect.
- Rearrange the equation to y=zx/(x−z). For each integer x in z+1…2z−1, compute the numerator and denominator and accept it exactly when the division has no remainder. No floating-point equality is needed.
- For z=15, x=16 gives y=240, x=18 gives 90, x=20 gives 60, and x=24 gives 40. Other candidates fail divisibility. The ascending loop already produces the required output order.
Why it works
The inequalities prove every legal solution has x in the enumerated range. Algebra gives a unique y for each such x. Divisibility is equivalent to y being an integer, and the range guarantees y>x. Thus every printed pair is valid and every valid pair is printed once.
Watch out. Exclude x=z, which causes division by zero, and x=2z, which gives x=y. Use remainder tests instead of approximate floating-point comparisons.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int main(){
int z;
cin>>z;
for(int x=z+1;x<2*z;x++){
int numerator=z*x;
int denominator=x-z;
// An exact remainder test preserves rational equality.
if(numerator%denominator==0){
cout<<x<<' '<<numerator/denominator<<'\n';
}
}
}