• Welcome to the new Internet Infidels Discussion Board, formerly Talk Freethought.

Egyptian fractions

lpetrich

lpetrich

Contributor
Joined
Jul 27, 2000
Messages
25,057
Location
Eugene, OR
Gender
Male
Basic Beliefs
Atheist
Ancient Egyptians liked to represent fractions as sums of reciprocals, though they sometimes used fractions like 2/3 and 3/4.
That 2/n table:
  • 2/3  = 1/2 + 1/6
  • 2/5   = 1/3 + 1/15
  • 2/7  = 1/4 + 1/28
  • 2/9  = 1/6 + 1/18
  • 2/11  = 1/6 + 1/66
  • 2/13 = 1/8 + 1/52 + 1/104
  • 2/15 = 1/10 + 1/30
  • 2/17  = 1/12 + 1/51 + 1/68
  • 2/19 = 1/12 + 1/76 + 1/114
  • Etc. to 2/101
The Rhind papyrus's multiples of 1/10:
  • 1/10 = 1/10
  • 2/10 = 1/5
  • 3/10 = 1/5 + 1/10
  • 4/10 = 1/3 - 1/15
  • 5/10 = 1/2
  • 6/10 = 1/2 + 1/10
  • 7/10 = 2/3 + 1/30
  • 8/10 = 2/3 + 1/10 + 1/30
  • 9/10 = 2/3 + 1/5 + 1/30
From some of these examples, it is possible to guess at what algorithms were used.

Like:
2/n = 1/m + (2m-n)/(m*n)
n/(p*q) = 1/(p*r) + 1/(q*r) where r = (p+q)/n
 
There is an algorithm called the greedy algorithm. It starts with a fraction x and finds the largest reciprocal not greater than it. 1/r. If x != 1/r, then it repeats the calculation with x - 1/r.

I'll apply it to approximations for pi.
  • 256/81 = 3 13/81 = 3 + 1/7 + 1/57 + 1/10773
  • 22/7 = 3 1/7 = 3 + 1/7
  • 223/71 = 3 10/71 = 3 + 1/8 + 1/64 + 1/4544
  • 355/113 = 3 16/113 = 3 + 1/8 + 1/61 + 1/5014 + 1/27649202 + 1/1911195900442808
256/81 is from an approximation of the area of a circle: ((8*diameter)/9)^2
 
 Egyptian fraction gives several reduction algorithms. Here are some of those that fit the Rhind papyrus's numbers:

A simple one for odd x is 2/x = 2/(x+1) + 2/x*(x+1))

A fancier one is 2/x = 1/a + (2*a-x)/(a*x) where a is some number with lots of divisors.

A fraction a/b where b has lots of divisors can be resolved by looking for some sum of divisors that adds up to a. For power-of-2 divisors, that is always possible, from a binary representation. For numbers with powers of higher primes, that is more difficult, but it is sometimes possible.

The number 6 = 2*3 and its proper divisors are 1, 2, and 3. One can form 1, 2, 3, 4 = 1+3, 5 = 2+3.

But prime numbers have only one proper divisor, so that is only possible for 2. That is also true of odd numbers more generally. One cannot represent 2 with the proper divisors of an odd number greater than 1.

There are also even numbers where that is not possible, like 10 = 2*5, with proper divisors 1, 2, 5. One can form 1, 2, 5, 6 = 1+5, 7=2+5, but not 3, 4, 8, 9.

2/(x*y) = 1/(a*x) + 1/(a*x*y) where a = (x+1)/2

n/(x*y) = 1/(a*x) + 1/(a*y) where a = (x+y)/n

2/x = 1/x + 1/(2x) + 1/(3x) + 1/(6x)

Fibonacci used algebraic identities like

a/(a*b-1) = 1/b + 1/(b*(a*b-1))

He also described a greedy method, though he conceded that it sometimes produces very large denominators.

Yes, the Fibonacci of the Fibonacci sequence.
 
Algorithms for Egyptian Fractions - Introduction
Greedy method: for x, the next fraction is 1/ceiling(1/x)

Odd greedy method: like the greedy method, but it looks for the next odd-denominator fraction. It resolves repeats by looking for the next odd denominator. If the input fraction has an even denominator, it needs to make one even-denominator output.

Harmonic method: tries to make a harmonic series: 1/n, 1/n+1, ..., then continues with the greedy method.

If one has multiple copies of some fraction, one may combine them: 1/x + 1/x = 2/x. If x is even, then one simplifies. But if x is odd, then one composes fractions 2/(x+1) and 2/(x*(x+1))


For the binary-number system, one uses a general theorem about place-system representations of rational numbers

(integer part).(nonrepeating fractional part)(infinitely repeating fractional part)

For instance, 1/3 in decimal is 0.333333333... and in binary is 0.0101010101...

 Euler's theorem provides a way of finding the repeating part. It uses  Euler's totient function, the number of numbers relatively prime to positive integer n: phi(n). It can be calculated as n * (product over distinct prime factors p of (1 - 1/p)).

That theorem: for all positive-integer a and n, a^(phi(n)) = 1 mod n.

The algorithm: find the lowest power of the base that contains all its prime factors in the denominator. Multiply the fraction by that value. The integer part is the nonrepeating part. To get the repeating part, finds its denominator (den) and find all the divisors d of phi(den). Then find the smallest d that makes (base)^d - 1 divisible by den. One then multiplies by (base)^d - 1 to get the repeating part.

Applied to Egyptian fractions, one can use this algorithm to get the nonrepeating part of a fraction with respect to some base, though only for base 2 does one get proper Egyptian fractions. One can get the repeating part with the help of that part's denominator, as (denominator) * (powers of 2).
 
 Paul Erdős has an interesting conjecture about Egyptian fractions:
UNPROVEN: Every fraction 4/n can be written as the sum of three Egyptian fractions.
. . . . 4/n = 1/a + 1/b + 1/c​

I've spent some time playing with this, though to no avail! :)
 
I first started playing with the  Erdős–Straus conjecture before Google and Wikipedia were so knowledgeable. Now I see that this problem has been well-studied, with even the famous Terence Tao involved.

Since 4/pq = 1/aq + 1/bq + 1/cq will be a solution if 4/p = 1/a + 1/b + 1/c is, we need only worry about p prime. And p = 4x-1 will cause no trouble; in fact two fractions will be enough: 4/(4x-1) = 1/(4x-1)x + 1/x.

When p = (4r-1)x - 1, then 4/p = 1/rx + 1/rp + 1/rxp does the trick. Since r and x can be any integers, many p will fit this pattern. And there are seemingly an infinite number of other successful patterns.

I stopped when I'd found patterns to deal with all p < 1000. The last holdout was p = 577 which succumbed to the following pattern:

When a = (2p + b + 1) / 8b is a positive integer for some b, then
4/p = 1/ab + 1/2ap + 1/2abp = (2p + b + 1)/2abp = 8ab/2abp = 4/p
For p = 577, b = 5 works. a = 29, and 4/577 = 1/5·29 + 1/2·29·577 + 1/2·5·29·577.

I guess it's been proven that no finite set of such patterns will suffice. Satisfactory patterns have been found for all p < 1017, but there seems to be no easy way to generate the required infinity of such patterns.
 
[1812.05684] Solutions to Diophantine Equation of Erdos-Straus Conjecture
In number theory, the Erdos-Straus conjecture states that for all n >=2, the rational number 4/n can be expressed as the sum of three unit fractions. Paul Erdos and Ernst G. Straus formulated the conjecture in 1948. The restriction that the three unit fractions be positive is essential to the difficulty of the problem, for if negative values were allowed the problem could always be solved. This paper presents an explicit solutions to this conjecture for all n >=2 excepting some n such that n=1(mod8).
Click to expand...

The greedy algorithm works for all n but n = 1 or 17 mod 24, and the second one is a special case of 2 mod 3.

The article mentions this solution: n = 3m-1: 4/n = 1/n + 1/m + 1/(n*m)

Also mentions solutions existing for 2 mod 3, 3 mod 4, 2 3 mod 5, 3 5 6 mod 7, 2 3 5 6 7 mod 8 -- Mordell's identities. These identities cover all positive integers > 2 other than 1, 121, 169, 289, 361, or 529 mod 840.
 
If a fraction's numerator is equal to the sum of divisors of its denominator, then that fraction can be decomposed into a sum of Egyptian fractions with the help of that sum. That is one of the algorithms that Fibonacci mentioned.

Thus, 5/6 = (2+3)/6 = 1/3 + 1/2

A number where that is always possible for numbers less than it is called a  Practical number - A005153 - OEIS - sometimes called a panarithmic number.

OEIS: 1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 48, 54, 56, 60, 64, 66, 72, 78, 80, 84, 88, 90, 96, 100, 104, 108, 112, 120, 126, 128, 132, 140, 144, 150, 156, 160, 162, 168, 176, 180, 192, 196, 198, 200, 204, 208, 210, 216, 220, 224, 228, 234, 240, 252

Using σ(n) for the sum of all divisors of n including itself, there is a necessary and sufficient condition for being a practical number -- the implication works both ways. It is that for every prime pi,

\( p(i) \le 1 + \sigma\left( \prod_{p_j < p_i} p_j^{m_j} \right) ;\ n = \prod_i p_i^{m_i} ;\ \sigma(n) = \prod_i \frac{p_i^{m_i+1} - 1}{p_i - 1} \)

The arg of the σ function is the contribution of all primes less than pi to n.

It is easy to show that no odd number greater than 1 is practical. Its smallest prime p is greater than 1 + σ(1) = 2. That is why all practical numbers greater than 1 are even, though only some even numbers are practical. The smallest one not practical is 10, because 5 > 1 + σ(2) = 3.

Related to that is A030057 - OEIS - the smallest number not the sum of distinct divisors of some number.

2, 4, 2, 8, 2, 13, 2, 16, 2, 4, 2, 29, 2, 4, 2, 32, 2, 40, 2, 43, 2, 4, 2, 61, 2, 4, 2, 57, 2, 73, 2, 64, 2, 4, 2, 92, 2, 4, 2, 91, 2, 97, 2, 8, 2, 4, 2, 125, 2, 4, 2, 8, 2, 121, 2, 121, 2, 4, 2, 169, 2, 4, 2, 128, 2, 145, 2, 8, 2, 4, 2, 196, 2, 4, 2, 8, 2, 169, 2, 187, 2, 4, 2, 225, 2, 4, 2, 181
 
Practical numbers satisfy some interrelationships.
  • The product of practical numbers is also a practical number
  • The least common multiple of practical numbers is also a practical number
  • For practical number n with divisor d, n*d is also a practical number
A practical number that cannot be composed from other practical numbers greater than 1 is called a "primitive" practical number, much like a prime number with multiplication.

When divided by any of its prime factors with factorization number greater than 1, the result will not be practical. A factorization number is the power where a prime contributes to a number as a prime factor.

A267124 - OEIS - primitive practical numbers
1, 2, 6, 20, 28, 30, 42, 66, 78, 88, 104, 140, 204, 210, 220, 228, 260, 272, 276, 304, 306, 308, 330, 340, 342, 348, 364, 368, 380, 390, 414, 460, 462, 464, 476, 496, 510, 522, 532, 546, 558, 570, 580, 620, 644, 666, 690, 714, 740, 744, 798, 812, 820, 858, 860, 868, 870, 888, 930, 966, 984
 
You must log in or register to reply here.
Back
Top Bottom