Egyptian Fracs: Algorithm for Minimizing Terms/Denominator

  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    Fractions
Click For Summary

Homework Help Overview

The discussion revolves around the problem of converting rational numbers into sums of distinct unit fractions, specifically focusing on algorithms that minimize the number of terms or the size of the largest denominator. The subject area includes number theory and algorithms related to Egyptian fractions.

Discussion Character

  • Exploratory, Conceptual clarification, Mathematical reasoning

Approaches and Questions Raised

  • The original poster inquires about algorithms for minimizing terms in Egyptian fraction representations. Some participants suggest the greedy algorithm as a potential method, while others question its effectiveness in achieving the desired minimization. There is also a discussion about the uniqueness of such decompositions.

Discussion Status

The discussion is active, with participants exploring different algorithms and their properties. Some guidance has been offered regarding the limitations of the greedy algorithm, and references to additional resources have been shared. Multiple interpretations of the problem are being considered.

Contextual Notes

Participants are discussing the uniqueness of Egyptian fraction decompositions and the implications of minimizing terms or denominators, which may involve assumptions about the nature of these fractions.

Dragonfall
Messages
1,023
Reaction score
5
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
My hunch would be the "greedy" algorithm. 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:
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:
Thanks, shmoe, I was wondering about that.

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

Similar threads

  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 8 ·
Replies
8
Views
2K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 11 ·
Replies
11
Views
2K
  • · Replies 5 ·
Replies
5
Views
1K
  • · Replies 9 ·
Replies
9
Views
3K
  • · Replies 9 ·
Replies
9
Views
3K
  • · Replies 12 ·
Replies
12
Views
2K
  • · Replies 6 ·
Replies
6
Views
2K