An   Egyptian fraction   is the sum of distinct unit fractions such as:

  






1
2



+



1
3



+



1
16




(
=



43
48



)


{\displaystyle {\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{16}}\,(={\tfrac {43}{48}})}

 
Each fraction in the expression has a numerator equal to   1   (unity)   and a denominator that is a positive integer,   and all the denominators are distinct   (i.e., no repetitions).

Fibonacci's   Greedy algorithm for Egyptian fractions   expands the fraction    






x
y





{\displaystyle {\tfrac {x}{y}}}

    to be represented by repeatedly performing the replacement

  





x
y


=


1

⌈
y

/

x
⌉



+



(
−
y
)





mod


x


y
⌈
y

/

x
⌉





{\displaystyle {\frac {x}{y}}={\frac {1}{\lceil y/x\rceil }}+{\frac {(-y)\!\!\!\!\mod x}{y\lceil y/x\rceil }}}

 


(simplifying the 2nd term in this replacement as necessary, and where    



⌈
x
⌉


{\displaystyle \lceil x\rceil }

    is the   ceiling   function).



For this task,   Proper and improper fractions   must be able to be expressed.



Proper  fractions   are of the form    






a
b





{\displaystyle {\tfrac {a}{b}}}

    where    



a


{\displaystyle a}

    and    



b


{\displaystyle b}

    are positive integers, such that    



a
<
b


{\displaystyle a<b}

,     and

improper fractions are of the form    






a
b





{\displaystyle {\tfrac {a}{b}}}

    where    



a


{\displaystyle a}

    and    



b


{\displaystyle b}

    are positive integers, such that    a ≥ b.



(See the REXX programming example to view one method of expressing the whole number part of an improper fraction.)

For improper fractions, the integer part of any improper fraction should be first isolated and shown preceding the Egyptian unit fractions, and be surrounded by square brackets [n].



Task requirements

   show the Egyptian fractions for: 






43
48





{\displaystyle {\tfrac {43}{48}}}

 and 






5
121





{\displaystyle {\tfrac {5}{121}}}

 and 






2014
59





{\displaystyle {\tfrac {2014}{59}}}


   for all proper fractions,    






a
b





{\displaystyle {\tfrac {a}{b}}}

    where    



a


{\displaystyle a}

    and    



b


{\displaystyle b}

    are positive one-or two-digit (decimal) integers, find and show an Egyptian fraction that has:
   the largest number of terms,
   the largest denominator.
   for all one-, two-, and three-digit integers,   find and show (as above).     {extra credit}


Also see

   Wolfram MathWorld™ entry: Egyptian fraction


 
use num_bigint::BigInt;
use num_integer::Integer;
use num_traits::{One, Zero};
use std::fmt;
 
#[derive(Debug, Clone, PartialEq, PartialOrd)]
struct Rational {
    nominator: BigInt,
    denominator: BigInt,
}
 
impl Rational {
    fn new(n: &BigInt, d: &BigInt) -> Rational {
        assert!(!d.is_zero(), "denominator cannot be 0");
        // simplify if possible
        let c = n.gcd(d);
        Rational {
            nominator: n / &c,
            denominator: d / &c,
        }
    }
 
    fn is_proper(&self) -> bool {
        self.nominator < self.denominator
    }
    fn to_egyptian(&self) -> Vec<Rational> {
        let mut frac: Vec<Rational> = Vec::new();
 
        let mut current: Rational;
        if !self.is_proper() {
            // input is grater than 1
            // store the integer part
            frac.push(Rational::new(
                &self.nominator.div_floor(&self.denominator),
                &One::one(),
            ));
 
            // calculate the remainder
            current = Rational::new(
                &self.nominator.mod_floor(&self.denominator),
                &self.denominator,
            );
        } else {
            current = self.clone();
        }
 
        while !current.nominator.is_one() {
            let div = current.denominator.div_ceil(&current.nominator);
 
            // store the term
            frac.push(Rational::new(&One::one(), &div));
 
            current = Rational::new(
                &(-&current.denominator).mod_floor(&current.nominator),
                match current.denominator.checked_mul(&div).as_ref() {
                    Some(r) => r,
                    _ => break,
                },
            );
        }
 
        frac.push(current);
        frac
    }
}
 
impl fmt::Display for Rational {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        if self.denominator.is_one() {
            // for integers only display the integer part
            write!(f, "{}", self.nominator)
        } else {
            write!(f, "{}/{}", self.nominator, self.denominator)
        }
    }
}
 
fn rational_vec_to_string(vec: Vec<Rational>) -> String {
    let mut p = vec
        .iter()
        .fold(String::new(), |acc, num| (acc + &num.to_string() + ", "));
 
    if p.len() > 1 {
        p.truncate(p.len() - 2);
    }
    format!("[{}]", p)
}
 
fn run_max_searches(x: usize) {
    // generate all proper fractions with 2 digits
    let pairs = (1..x).flat_map(move |i| (i + 1..x).map(move |j| (i, j)));
 
    let mut max_length = (0, Rational::new(&BigInt::from(1), &BigInt::from(1)));
    let mut max_denom = (
        Zero::zero(),
        Rational::new(&BigInt::from(1), &BigInt::from(1)),
    );
 
    for (i, j) in pairs {
        let e = Rational::new(&BigInt::from(i), &BigInt::from(j)).to_egyptian();
        if e.len() > max_length.0 {
            max_length = (e.len(), Rational::new(&BigInt::from(i), &BigInt::from(j)));
        }
 
        if e.last().unwrap().denominator > max_denom.0 {
            max_denom = (
                e.last().unwrap().denominator.clone(),
                Rational::new(&BigInt::from(i), &BigInt::from(j)),
            );
        }
    }
 
    println!(
        "Maximum length of terms is for {} with {} terms",
        max_length.1, max_length.0
    );
    println!("{}", rational_vec_to_string(max_length.1.to_egyptian()));
 
    println!(
        "Maximum denominator is for {} with {} terms",
        max_denom.1, max_denom.0
    );
    println!("{}", rational_vec_to_string(max_denom.1.to_egyptian()));
}
fn main() {
    let tests = [
        Rational::new(&BigInt::from(43), &BigInt::from(48)),
        Rational::new(&BigInt::from(5), &BigInt::from(121)),
        Rational::new(&BigInt::from(2014), &BigInt::from(59)),
    ];
 
    for test in tests.iter() {
        println!("{} -> {}", test, rational_vec_to_string(test.to_egyptian()));
    }
 
    run_max_searches(100);
    run_max_searches(1000);
}
 
 