Egyptian Fracs: Algorithm for Minimizing Terms/Denominator

  • Thread starter Dragonfall
  • Start date
  • Tags
    Fractions
In summary, the conversation discusses the use of an algorithm to convert any rational number to a sum of distinct unit fractions. The "greedy" algorithm is suggested, where the smallest integer is repeatedly subtracted from the rational number until a unit fraction is reached. However, this algorithm may not always result in the representation with the least number of terms and smallest denominators. There is a calculator available to find the shortest representation on the website provided.
  • #1
Dragonfall
1,030
4
Is there an algorithm which can convert any rational number to a sum of distinct unit fractions which minimizes the number of terms or the largest denominator?
 
Physics news on Phys.org
  • #2
My hunch would be the "greedy" algoritm. Given rational x1, let n be the smallest integer such that 1/n< x1. Now repeat the process with x2= x1- 1/n.

For example to find the unit fractions for 13/17:
It is clear that 1/2< 13/17 so our first unit fraction is 1/2. 13/17- 1/2= 26/34- 17/34= 9/34. 1/3> 9/34 but 1/4< 9/34 so our second unit fraction is 1/4. 9/34- 1/4= 18/68- 17/68= 1/68 which is itself a unit fraction.
13/17= 1/2+ 1/4+ 1/68.

Is it necessary to include "which minimizes the number of terms or the largest denominator"? Isn't decomposition into unit fractions unique?
 
Last edited by a moderator:
  • #3
The decomposition is not at all unique. 1/2=1/3+1/6 for example. See the algorithm described in

https://www.physicsforums.com/showthread.php?t=119708&highlight=egyptian


The greedy algorithm can fail to give the representation with the least number of terms and smallest denominators. See

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fractions/egyptian.html#Fibgreedy

I'm not sure of the algorithm that finds the shortest, but they have a calculator on that page that claims to, so that page is probably a good place to start.
 
Last edited by a moderator:
  • #4
Thanks, shmoe, I was wondering about that.

I have edited my post so it makes sense now!
 
  • #5
Thanks for the help.
 

1. What is the purpose of the Egyptian Fracs algorithm?

The Egyptian Fracs algorithm is designed to minimize the number of terms in a fraction's denominator, making it easier to work with and manipulate mathematically.

2. How does the Egyptian Fracs algorithm work?

The algorithm works by repeatedly dividing the numerator by the largest possible unit fraction (a fraction with a numerator of 1) that is less than the remaining fraction. This process is repeated until the remaining fraction becomes equal to 1, at which point the unit fractions used in the division are the terms in the Egyptian fraction.

3. What are the benefits of using the Egyptian Fracs algorithm?

The main benefit of using the algorithm is that it simplifies fractions and makes them easier to work with. This can be especially useful in complex mathematical calculations or when comparing fractions.

4. Are there any limitations to the Egyptian Fracs algorithm?

While the algorithm is effective in minimizing terms in a fraction's denominator, it may not always produce the most efficient or smallest possible Egyptian fraction. Additionally, the algorithm does not work for all fractions, particularly those with large prime denominators.

5. How is the Egyptian Fracs algorithm used in modern times?

The algorithm is still used in some areas of mathematics, particularly in number theory and algorithms research. However, with the advent of computers and calculators, it is not as commonly used in everyday calculations as it once was.

Similar threads

  • Calculus and Beyond Homework Help
Replies
8
Views
887
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
11
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
127
  • Calculus and Beyond Homework Help
Replies
3
Views
3K
  • Calculus and Beyond Homework Help
Replies
12
Views
2K
  • Special and General Relativity
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
11
Views
1K
Back
Top