Analyzing Patterns within an Original Egyptian Fraction Decomposition Algorithm

Overview

The exploration of Egyptian Fractions is part of the field of pure mathematics, Number Theory. First used by the Egyptians to express fractions with 2 in the numerator or 10 in the denominator, they can be defined as proper fractions expressed through the sum of distinct unit fractions. Rather than having a defined method for decomposing fractions, they used a chart. Later, the greedy algorithm was applied to Egyptian fractions as a method for decomposition. While it is the conventional algorithm for decomposition, it is not always most suitable. During the course of this project, a different algorithm was developed that deals with the binary expansion of the numerator. Testing proved it more efficient in some cases - especially those involving perfect numbers in the denominator. Due to the way the algorithm functions though, it has yet to be proven whether or not the algorithm will terminate in every case. No cases contradicting termination have been found yet. To take steps towards proving the functionality and termination of the algorithm, perfect numbers, Mersenne numbers, and the sum lengths of each decomposition were analyzed in order to find patterns that would help predict a sum length for any fraction. Based on these studies, as a general rule, the prime factorization of the denominator correlated numerically to the lengths of these sums. Through analysis, significant steps toward achieving a proof of the derived and improved algorithm were taken and, in the process, more patterns within the fundamentals of the algorithm were discovered.

Competition history

• ISEF 2018 Mathematics · Entry MATH028

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.