Greedy algorithm for Egyptian fractions: Difference between revisions

Content added Content deleted

Inline

@@ Line 2,941: / Line 2,941: @@
 Denominator max is 8/97 with 150 digits
 579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665
+</pre>
+=={{header|Rust}}==
+<lang rust>
+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);
+}
+</lang>
+{{out}}
+<pre>
+/48 -> [1/2, 1/3, 1/16]
+/121 -> [1/25, 1/757, 1/763309, 1/873960180913, 1/1527612795642093418846225]
+/59 -> [34, 1/8, 1/95, 1/14947, 1/670223480]
+Maximum length of terms is for 8/97 with 8 terms
+[1/13, 1/181, 1/38041, 1/1736503177, 1/3769304102927363485, 1/18943537893793408504192074528154430149, 1/538286441900380211365817285104907086347439746130226973253778132494225813153, 1/579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665]
+Maximum denominator is for 8/97 with 5795045870675428017131...3909789665 terms (150 digits)
+[1/13, 1/181, 1/38041, 1/1736503177, 1/3769304102927363485, 1/18943537893793408504192074528154430149, 1/538286441900380211365817285104907086347439746130226973253778132494225813153, 1/5795045870675428017131...3909789665]
+Maximum length of terms is for 529/914 with 13 terms:
+[1/2, 1/13, 1/541, 1/321409, 1/114781617793, 1/14821672255960844346913, 1/251065106814993628596500876449600804290086881, 1/73539302503361520198362339236500915390885795679264404865887253300925727812630083326272641, 1/6489634815217096741...91865217, 1/52644200043...5476206145, 1/36952157309...38141889, 1/204819289476534...06590593, 1/83901882683...25592705]
+Maximum denominator is for 36/457 with 83901882683...25592705 (2847 digits)
 </pre>