Egyptian fraction
   HOME

TheInfoList



OR:

An Egyptian fraction is a finite sum of distinct
unit fraction A unit fraction is a rational number written as a fraction where the numerator is one and the denominator is a positive integer. A unit fraction is therefore the reciprocal of a positive integer, 1/''n''. Examples are 1/1, 1/2, 1/3, 1/4, 1/5, et ...
s, such as \frac+\frac+\frac. That is, each
fraction A fraction (from la, fractus, "broken") represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, a fraction describes how many parts of a certain size there are, for example, one-half, eight ...
in the expression has a
numerator A fraction (from la, fractus, "broken") represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, a fraction describes how many parts of a certain size there are, for example, one-half, eight ...
equal to 1 and a
denominator A fraction (from la, fractus, "broken") represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, a fraction describes how many parts of a certain size there are, for example, one-half, eight ...
that is a positive
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
, and all the denominators differ from each other. The value of an expression of this type is a
positive Positive is a property of positivity and may refer to: Mathematics and science * Positive formula, a logical formula not containing negation * Positive number, a number that is greater than 0 * Plus sign, the sign "+" used to indicate a posi ...
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
\tfrac; for instance the Egyptian fraction above sums to \tfrac. Every positive rational number can be represented by an Egyptian fraction. Sums of this type, and similar sums also including \tfrac and \tfrac as
summand Addition (usually signified by the plus symbol ) is one of the four basic operations of arithmetic, the other three being subtraction, multiplication and division. The addition of two whole numbers results in the total amount or '' sum'' of ...
s, were used as a serious notation for rational numbers by the ancient Egyptians, and continued to be used by other civilizations into medieval times. In modern mathematical notation, Egyptian fractions have been superseded by
vulgar fraction A fraction (from la, fractus, "broken") represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, a fraction describes how many parts of a certain size there are, for example, one-half, eight ...
s and
decimal The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral ...
notation. However, Egyptian fractions continue to be an object of study in modern
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777 ...
and
recreational mathematics Recreational mathematics is mathematics carried out for recreation (entertainment) rather than as a strictly research and application-based professional activity or as a part of a student's formal education. Although it is not necessarily limited ...
, as well as in modern historical studies of ancient mathematics.


Applications

Beyond their historical use, Egyptian fractions have some practical advantages over other representations of fractional numbers. For instance, Egyptian fractions can help in dividing food or other objects into equal shares. For example, if one wants to divide 5 pizzas equally among 8 diners, the Egyptian fraction \frac=\frac+\frac means that each diner gets half a pizza plus another eighth of a pizza, for example by splitting 4 pizzas into 8 halves, and the remaining pizza into 8 eighths. Similarly, although one could divide 13 pizzas among 12 diners by giving each diner one pizza and splitting the remaining pizza into 12 parts (perhaps destroying it), one could note that \frac=\frac+\frac+\frac and split 6 pizzas into halves, 4 into thirds and the remaining 3 into quarters, and then give each diner one half, one third and one quarter. Egyptian fractions can provide a solution to rope-burning puzzles, in which a given duration is to be measured by igniting non-uniform ropes which burn out after a unit time. Any rational fraction of a unit of time can be measured by expanding the fraction into a sum of unit fractions and then, for each unit fraction 1/x, burning a rope so that it always has x simultaneously lit points where it is burning. For this application, it is not necessary for the unit fractions to be distinct from each other. However, this solution may need an infinite number of re-lighting steps.


Early history

Egyptian fraction notation was developed in the
Middle Kingdom of Egypt The Middle Kingdom of Egypt (also known as The Period of Reunification) is the period in the history of ancient Egypt following a period of political division known as the First Intermediate Period. The Middle Kingdom lasted from approximatel ...
. Five early texts in which Egyptian fractions appear were the
Egyptian Mathematical Leather Roll The Egyptian Mathematical Leather Roll (EMLR) is a 10 × 17 in (25 × 43 cm) leather roll purchased by Alexander Henry Rhind in 1858. It was sent to the British Museum in 1864, along with the Rhind Mathemati ...
, the
Moscow Mathematical Papyrus The Moscow Mathematical Papyrus, also named the Golenishchev Mathematical Papyrus after its first non-Egyptian owner, Egyptologist Vladimir Golenishchev, is an ancient Egyptian mathematical papyrus containing several problems in arithmetic, geom ...
, the
Reisner Papyrus The Reisner Papyri date to the reign of Senusret I, who was king of ancient Egypt in the 19th century BCE. The documents were discovered by G.A. Reisner during excavations in 1901–04 in Naga ed-Deir in southern Egypt. A total of four papyrus rol ...
, the
Kahun Papyrus The Kahun Papyri (KP; also Petrie Papyri or Lahun Papyri) are a collection of ancient Egyptian texts discussing administrative, mathematical and medical topics. Its many fragments were discovered by Flinders Petrie in 1889 and are kept at the U ...
and the
Akhmim Wooden Tablet The Akhmim wooden tablets, also known as the Cairo wooden tablets (Cairo Cat. 25367 and 25368), are two wooden writing tablets from ancient Egypt, solving arithmetical problems. They each measure around and are covered with plaster. The tablets ar ...
. A later text, the Rhind Mathematical Papyrus, introduced improved ways of writing Egyptian fractions. The Rhind papyrus was written by
Ahmes Ahmes ( egy, jꜥḥ-ms “, a common Egyptian name also transliterated Ahmose) was an ancient Egyptian scribe who lived towards the end of the Fifteenth Dynasty (and of the Second Intermediate Period) and the beginning of the Eighteenth Dyna ...
and dates from the
Second Intermediate Period The Second Intermediate Period marks a period when ancient Egypt fell into disarray for a second time, between the end of the Middle Kingdom and the start of the New Kingdom. The concept of a "Second Intermediate Period" was coined in 1942 by ...
; it includes a table of Egyptian fraction expansions for rational numbers \tfrac, as well as 84 word problems. Solutions to each problem were written out in scribal shorthand, with the final answers of all 84 problems being expressed in Egyptian fraction notation. Tables of expansions for \tfrac similar to the one on the Rhind papyrus also appear on some of the other texts. However, as the
Kahun Papyrus The Kahun Papyri (KP; also Petrie Papyri or Lahun Papyri) are a collection of ancient Egyptian texts discussing administrative, mathematical and medical topics. Its many fragments were discovered by Flinders Petrie in 1889 and are kept at the U ...
shows,
vulgar fraction A fraction (from la, fractus, "broken") represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, a fraction describes how many parts of a certain size there are, for example, one-half, eight ...
s were also used by scribes within their calculations.


Notation

To write the unit fractions used in their Egyptian fraction notation, in hieroglyph script, the Egyptians placed the
hieroglyph A hieroglyph ( Greek for "sacred carvings") was a character of the ancient Egyptian writing system. Logographic scripts that are pictographic in form in a way reminiscent of ancient Egyptian are also sometimes called "hieroglyphs". In Neoplatoni ...
(''er'', " ne/nowiki> among" or possibly ''re'', mouth) above a number to represent the
reciprocal Reciprocal may refer to: In mathematics * Multiplicative inverse, in mathematics, the number 1/''x'', which multiplied by ''x'' gives the product 1, also known as a ''reciprocal'' * Reciprocal polynomial, a polynomial obtained from another pol ...
of that number. Similarly in hieratic script they drew a line over the letter representing the number. For example: The Egyptians had special symbols for \tfrac, \tfrac, and \tfrac that were used to reduce the size of numbers greater than \tfrac when such numbers were converted to an Egyptian fraction series. The remaining number after subtracting one of these special fractions was written as a sum of distinct unit fractions according to the usual Egyptian fraction notation. The Egyptians also used an alternative notation modified from the Old Kingdom to denote a special set of fractions of the form 1/2^k (for k=1,2,\dots,6) and sums of these numbers, which are necessarily
dyadic rational In mathematics, a dyadic rational or binary rational is a number that can be expressed as a fraction whose denominator is a power of two. For example, 1/2, 3/2, and 3/8 are dyadic rationals, but 1/3 is not. These numbers are important in compute ...
numbers. These have been called "Horus-Eye fractions" after a theory (now discredited) that they were based on the parts of the
Eye of Horus The Eye of Horus, ''wedjat'' eye or ''udjat'' eye is a concept and symbol in ancient Egyptian religion that represents well-being, healing, and protection. It derives from the mythical conflict between the god Horus with his rival Set, in wh ...
symbol. They were used in the Middle Kingdom in conjunction with the later notation for Egyptian fractions to subdivide a
hekat The hekat or heqat (transcribed ''HqA.t'') was an ancient Egyptian volume unit used to measure grain, bread, and beer. It equals 4.8 litres, or about 1.056 imperial gallons, in today's measurements. retrieved March 22, 2020 at about 7:00 ...
, the primary ancient Egyptian volume measure for grain, bread, and other small quantities of volume, as described in the
Akhmim Wooden Tablet The Akhmim wooden tablets, also known as the Cairo wooden tablets (Cairo Cat. 25367 and 25368), are two wooden writing tablets from ancient Egypt, solving arithmetical problems. They each measure around and are covered with plaster. The tablets ar ...
. If any remainder was left after expressing a quantity in Eye of Horus fractions of a hekat, the remainder was written using the usual Egyptian fraction notation as multiples of a ''ro'', a unit equal to \tfrac of a hekat.


Calculation methods

Modern historians of mathematics have studied the Rhind papyrus and other ancient sources in an attempt to discover the methods the Egyptians used in calculating with Egyptian fractions. In particular, study in this area has concentrated on understanding the tables of expansions for numbers of the form \tfrac in the Rhind papyrus. Although these expansions can generally be described as algebraic identities, the methods used by the Egyptians may not correspond directly to these identities. Additionally, the expansions in the table do not match any single identity; rather, different identities match the expansions for
prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
and for
composite Composite or compositing may refer to: Materials * Composite material, a material that is made from several different substances ** Metal matrix composite, composed of metal and other parts ** Cermet, a composite of ceramic and metallic materials ...
denominators, and more than one identity fits the numbers of each type: * For small odd prime denominators p, the expansion \frac = \frac + \frac was used. * For larger prime denominators, an expansion of the form \frac = \frac + \frac was used, where A is a number with many divisors (such as a
practical number In number theory, a practical number or panarithmic number is a positive integer n such that all smaller positive integers can be represented as sums of distinct divisors of n. For example, 12 is a practical number because all the numbers from 1 ...
) between \tfrac and p. The remaining term (2A-p)/Ap was expanded by representing the number 2A-p as a sum of divisors of A and forming a fraction \tfrac for each such divisor d in this sum. As an example, Ahmes' expansion \tfrac=\tfrac+\tfrac+\frac fits this pattern with A=24 and 2A-p=11=8+3, as \tfrac=\tfrac and \tfrac=\tfrac. There may be many different expansions of this type for a given p; however, as K. S. Brown observed, the expansion chosen by the Egyptians was often the one that caused the largest denominator to be as small as possible, among all expansions fitting this pattern. * For some composite denominators, factored as p\cdot q, the expansion for \tfrac has the form of an expansion for \tfrac with each denominator multiplied by q. This method appears to have been used for many of the composite numbers in the Rhind papyrus, but there are exceptions, notably \tfrac, \tfrac, and \tfrac. * One can also expand \frac=\frac+\frac. For instance, Ahmes expands \tfrac=\tfrac=\tfrac+\tfrac. Later scribes used a more general form of this expansion, \frac=\frac+\frac, which works when p+q is a multiple of n. * The final (prime) expansion in the Rhind papyrus, \tfrac, does not fit any of these forms, but instead uses an expansion \frac = \frac + \frac + \frac + \frac that may be applied regardless of the value of p. That is, \tfrac = \tfrac + \tfrac + \tfrac + \tfrac. A related expansion was also used in the Egyptian Mathematical Leather Roll for several cases.


Later usage

Egyptian fraction notation continued to be used in Greek times and into the Middle Ages, despite complaints as early as
Ptolemy Claudius Ptolemy (; grc-gre, Πτολεμαῖος, ; la, Claudius Ptolemaeus; AD) was a mathematician, astronomer, astrologer, geographer, and music theorist, who wrote about a dozen scientific treatises, three of which were of importanc ...
's
Almagest The ''Almagest'' is a 2nd-century Greek-language mathematical and astronomical treatise on the apparent motions of the stars and planetary paths, written by Claudius Ptolemy ( ). One of the most influential scientific texts in history, it canoni ...
about the clumsiness of the notation compared to alternatives such as the Babylonian base-60 notation. Related problems of decomposition into unit fractions were also studied in 9th-century India by Jain mathematician
Mahāvīra Mahavira (Sanskrit: महावीर) also known as Vardhaman, was the 24th ''tirthankara'' (supreme preacher) of Jainism. He was the spiritual successor of the 23rd ''tirthankara'' Parshvanatha. Mahavira was born in the early part of the 6 ...
. An important text of medieval European mathematics, the ''
Liber Abaci ''Liber Abaci'' (also spelled as ''Liber Abbaci''; "The Book of Calculation") is a historic 1202 Latin manuscript on arithmetic by Leonardo of Pisa, posthumously known as Fibonacci. ''Liber Abaci'' was among the first Western books to describe ...
'' (1202) of
Leonardo of Pisa Fibonacci (; also , ; – ), also known as Leonardo Bonacci, Leonardo of Pisa, or Leonardo Bigollo Pisano ('Leonardo the Traveller from Pisa'), was an Italian mathematician from the Republic of Pisa, considered to be "the most talented Western ...
(more commonly known as Fibonacci), provides some insight into the uses of Egyptian fractions in the Middle Ages, and introduces topics that continue to be important in modern mathematical study of these series. The primary subject of the ''Liber Abaci'' is calculations involving decimal and vulgar fraction notation, which eventually replaced Egyptian fractions. Fibonacci himself used a complex notation for fractions involving a combination of a
mixed radix Mixed radix numeral systems are non-standard positional numeral systems in which the numerical radix, base varies from position to position. Such numerical representation applies when a quantity is expressed using a sequence of units that are eac ...
notation with sums of fractions. Many of the calculations throughout Fibonacci's book involve numbers represented as Egyptian fractions, and one section of this book provides a list of methods for conversion of vulgar fractions to Egyptian fractions. If the number is not already a unit fraction, the first method in this list is to attempt to split the numerator into a sum of divisors of the denominator; this is possible whenever the denominator is a
practical number In number theory, a practical number or panarithmic number is a positive integer n such that all smaller positive integers can be represented as sums of distinct divisors of n. For example, 12 is a practical number because all the numbers from 1 ...
, and ''Liber Abaci'' includes tables of expansions of this type for the practical numbers 6, 8, 12, 20, 24, 60, and 100. The next several methods involve algebraic identities such as \frac=\frac+\frac. For instance, Fibonacci represents the fraction by splitting the numerator into a sum of two numbers, each of which divides one plus the denominator: . Fibonacci applies the algebraic identity above to each these two parts, producing the expansion . Fibonacci describes similar methods for denominators that are two or three less than a number with many factors. In the rare case that these other methods all fail, Fibonacci suggests a "greedy" algorithm for computing Egyptian fractions, in which one repeatedly chooses the unit fraction with the smallest denominator that is no larger than the remaining fraction to be expanded: that is, in more modern notation, we replace a fraction by the expansion \frac=\frac+\frac, where represents the
ceiling function In mathematics and computer science, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least inte ...
; since , this method yields a finite expansion. Fibonacci suggests switching to another method after the first such expansion, but he also gives examples in which this greedy expansion was iterated until a complete Egyptian fraction expansion was constructed: and . Compared to ancient Egyptian expansions or to more modern methods, this method may produce expansions that are quite long, with large denominators, and Fibonacci himself noted the awkwardness of the expansions produced by this method. For instance, the greedy method expands \frac=\frac+\frac+\frac+\frac+\frac, while other methods lead to the shorter expansion \frac=\frac+\frac+\frac.
Sylvester's sequence In number theory, Sylvester's sequence is an integer sequence in which each term of the sequence is the product of the previous terms, plus one. The first few terms of the sequence are :2, 3, 7, 43, 1807, 3263443, 10650056950807, 11342371305542184 ...
2, 3, 7, 43, 1807, ... can be viewed as generated by an infinite greedy expansion of this type for the number 1, where at each step we choose the denominator instead of , and sometimes Fibonacci's greedy algorithm is attributed to
James Joseph Sylvester James Joseph Sylvester (3 September 1814 – 15 March 1897) was an English mathematician. He made fundamental contributions to matrix theory, invariant theory, number theory, partition theory, and combinatorics. He played a leadership ro ...
. After his description of the greedy algorithm, Fibonacci suggests yet another method, expanding a fraction by searching for a number ''c'' having many divisors, with , replacing by , and expanding ''ac'' as a sum of divisors of ''bc'', similar to the method proposed by Hultsch and Bruins to explain some of the expansions in the Rhind papyrus.


Modern number theory

Although Egyptian fractions are no longer used in most practical applications of mathematics, modern number theorists have continued to study many different problems related to them. These include problems of bounding the length or maximum denominator in Egyptian fraction representations, finding expansions of certain special forms or in which the denominators are all of some special type, the termination of various methods for Egyptian fraction expansion, and showing that expansions exist for any sufficiently dense set of sufficiently
smooth number In number theory, an ''n''-smooth (or ''n''-friable) number is an integer whose prime factors are all less than or equal to ''n''. For example, a 7-smooth number is a number whose every prime factor is at most 7, so 49 = 72 and 15750 = 2 × 32 × ...
s. *One of the earliest publications of
Paul Erdős Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
proved that it is not possible for a harmonic progression to form an Egyptian fraction representation of an
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
. The reason is that, necessarily, at least one denominator of the progression will be divisible by a
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
that does not divide any other denominator. The latest publication of Erdős, nearly 20 years after his death, proves that every integer has a representation in which all denominators are products of three primes. *The Erdős–Graham conjecture in
combinatorial number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Math ...
states that, if the integers greater than 1 are partitioned into finitely many subsets, then one of the subsets has a finite subset of itself whose reciprocals sum to one. That is, for every , and every ''r''-coloring of the integers greater than one, there is a finite monochromatic subset ''S'' of these integers such that \sum_\frac = 1. The conjecture was proven in 2003 by Ernest S. Croot III. *
Znám's problem In number theory, Znám's problem asks which sets of integers have the property that each integer in the set is a proper divisor of the product of the other integers in the set, plus 1. Znám's problem is named after the Slovak mathematician Šte ...
and
primary pseudoperfect number In mathematics, and particularly in number theory, ''N'' is a primary pseudoperfect number if it satisfies the Egyptian fraction equation :\frac + \sum_\frac = 1, where the sum is over only the prime divisors of ''N''. Properties Equivalently, ...
s are closely related to the existence of Egyptian fractions of the form \sum\frac1 + \prod\frac1=1. For instance, the primary pseudoperfect number 1806 is the product of the prime numbers 2, 3, 7, and 43, and gives rise to the Egyptian fraction . *Egyptian fractions are normally defined as requiring all denominators to be distinct, but this requirement can be relaxed to allow repeated denominators. However, this relaxed form of Egyptian fractions does not allow for any number to be represented using fewer fractions, as any expansion with repeated fractions can be converted to an Egyptian fraction of equal or smaller length by repeated application of the replacement \frac1k+\frac1k=\frac2+\frac2 if ''k'' is odd, or simply by replacing by if ''k'' is even. This result was first proven by . *Graham and Jewett proved that it is similarly possible to convert expansions with repeated denominators to (longer) Egyptian fractions, via the replacement \frac1k+\frac1k=\frac1k+\frac1+\frac1. This method can lead to long expansions with large denominators, such as \frac45=\frac15+\frac16+\frac17+\frac18+\frac1+\frac1+\frac1+\frac1+\frac1+\frac1+ \frac1+\frac1+\frac1+\frac1+\frac1. had originally used this replacement technique to show that any rational number has Egyptian fraction representations with arbitrarily large minimum denominators. *Any fraction has an Egyptian fraction representation in which the maximum denominator is bounded by O\left(y \log y \left(\log\log y\right)^4 \left(\log\log\log y\right)^2\right), and a representation with at most O\left(\sqrt\right) terms. The number of terms must sometimes be at least proportional to ; for instance this is true for the fractions in the sequence , , , , , ... whose denominators form
Sylvester's sequence In number theory, Sylvester's sequence is an integer sequence in which each term of the sequence is the product of the previous terms, plus one. The first few terms of the sequence are :2, 3, 7, 43, 1807, 3263443, 10650056950807, 11342371305542184 ...
. It has been conjectured that terms are always enough. It is also possible to find representations in which both the maximum denominator and the number of terms are small. * characterized the numbers that can be represented by Egyptian fractions in which all denominators are ''n''th powers. In particular, a rational number ''q'' can be represented as an Egyptian fraction with square denominators if and only if ''q'' lies in one of the two half-open intervals \left[0,\frac-1\right)\cup\left[1,\frac\right). * showed that any rational number has very dense expansions, using a constant fraction of the denominators up to ''N'' for any sufficiently large ''N''. *Engel expansion, sometimes called an ''Egyptian product'', is a form of Egyptian fraction expansion in which each denominator is a multiple of the previous one: x=\frac+\frac+\frac+\cdots. In addition, the sequence of multipliers ''ai'' is required to be nondecreasing. Every rational number has a finite Engel expansion, while
irrational number In mathematics, the irrational numbers (from in- prefix assimilated to ir- (negative prefix, privative) + rational) are all the real numbers that are not rational numbers. That is, irrational numbers cannot be expressed as the ratio of two integ ...
s have an infinite Engel expansion. * study numbers that have multiple distinct Egyptian fraction representations with the same number of terms and the same product of denominators; for instance, one of the examples they supply is \frac=\frac+\frac+\frac=\frac+\frac+\frac. Unlike the ancient Egyptians, they allow denominators to be repeated in these expansions. They apply their results for this problem to the characterization of
free product In mathematics, specifically group theory, the free product is an operation that takes two groups ''G'' and ''H'' and constructs a new The result contains both ''G'' and ''H'' as subgroups, is generated by the elements of these subgroups, and i ...
s of
Abelian group In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commut ...
s by a small number of numerical parameters: the rank of the
commutator subgroup In mathematics, more specifically in abstract algebra, the commutator subgroup or derived subgroup of a group is the subgroup generated by all the commutators of the group. The commutator subgroup is important because it is the smallest normal s ...
, the number of terms in the free product, and the product of the orders of the factors. *The number of different ''n''-term Egyptian fraction representations of the number one is bounded above and below by
double exponential function A double exponential function is a constant raised to the power of an exponential function. The general formula is f(x) = a^=a^ (where ''a''>1 and ''b''>1), which grows much more quickly than an exponential function. For example, if ''a'' = ''b ...
s of ''n''.


Open problems

Some notable problems remain unsolved with regard to Egyptian fractions, despite considerable effort by mathematicians. * The
Erdős–Straus conjecture The Erdős–Straus conjecture is an unproven statement in number theory. The conjecture is that, for every integer n that is 2 or more, there exist positive integers x, y, and z for which \frac=\frac+\frac+\frac. In other words, the number 4/n ...
concerns the length of the shortest expansion for a fraction of the form . Does an expansion \frac4n=\frac1x+\frac1y+\frac1z exist for every ''n''? It is known to be true for all , and for all but a vanishingly small fraction of possible values of ''n'', but the general truth of the conjecture remains unknown. * It is unknown whether an
odd greedy expansion In number theory, the odd greedy expansion problem asks whether a greedy algorithm for finding Egyptian fractions with odd denominators always succeeds. , it remains unsolved. Description An Egyptian fraction represents a given rational number as ...
exists for every fraction with an odd denominator. If Fibonacci's greedy method is modified so that it always chooses the smallest possible ''odd'' denominator, under what conditions does this modified algorithm produce a finite expansion? An obvious necessary condition is that the starting fraction have an odd denominator ''y'', and it is conjectured but not known that this is also a sufficient condition. It is known; that every with odd ''y'' has an expansion into distinct odd unit fractions, constructed using a different method than the greedy algorithm. * It is possible to use
brute-force search In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the soluti ...
algorithms to find the Egyptian fraction representation of a given number with the fewest possible terms or minimizing the largest denominator; however, such algorithms can be quite inefficient. The existence of
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
algorithms for these problems, or more generally the
computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
of such problems, remains unknown. describes these problems in more detail and lists numerous additional open problems.


See also

*
List of sums of reciprocals In mathematics and especially number theory, the sum of reciprocals generally is computed for the reciprocals of some or all of the positive integers (counting numbers)—that is, it is generally the sum of unit fractions. If infinitely many n ...


Notes


References

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *


External links

*. *. *. * * and ,
The Wolfram Demonstrations Project The Wolfram Demonstrations Project is an organized, open-source collection of small (or medium-size) interactive programs called Demonstrations, which are meant to visually and interactively represent ideas from a range of fields. It is hos ...
, based on programs by
David Eppstein David Arthur Eppstein (born 1963) is an American computer scientist and mathematician. He is a Distinguished Professor of computer science at the University of California, Irvine. He is known for his work in computational geometry, graph algorit ...
. {{Authority control Recreational mathematics Number theory