This site is supported by donations to The OEIS Foundation.

Greedy Egyptian representation

From OeisWiki

Jump to: navigation, search

This article page is a stub, please help by expanding it.


An Egyptian representation of a real number \scriptstyle r \, is a sum of positive (usually) distinct unit fractions equal to \scriptstyle r \,. The (unique) greedy Egyptian representation uses the greedy algorithm for Egyptian representation.

Contents

Greedy Egyptian representation of 1 in unit fractions less than 1

1 = \frac{1}{2} + \frac{1}{3} + \frac{1}{7} + \frac{1}{43} + \frac{1}{1807} + \frac{1}{3263443} + \frac{1}{10650056950807} + \frac{1}{113423713055421844361000443} + \ldots \,

The denominators are given by the quadratic recurrence

a(1) = 2,\, a(n) = a(n-1) (a(n-1) - 1) + 1 = a(n)^2 - a(n) + 1,\quad n \ge 2. \,

and by the formula (which shows that it is an infinite coprime sequence)

a(n) = 1 + \prod_{i=1}^{n-1} a(i), \,

where for \scriptstyle n \,=\, 1 \, we get 1 + (empty product, i.e. 1) = 2.

Greedy Egyptian representation of 1 (Sylvester's sequence): a(n+1) = a(n)^2 - a(n) + 1, with a(0) = 2. (Cf. A000058)

{2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443, 12864938683278671740537145998360961546653259485195807, ...}

Greedy Egyptian representation of positive rational numbers less than 1

Greedy Egyptian representation
\scriptstyle \frac{m}{n} \, Denominators of distinct unit fractions of the greedy Egyptian representation

of positive rational numbers less than 1

\tfrac{1}{2} \, {2}
\tfrac{1}{3} \, {3}
\tfrac{2}{3} \, {2, 6}
\tfrac{1}{4} \, {4}
\tfrac{3}{4} \, {2, 4}
\tfrac{1}{5} \, {5}
\tfrac{2}{5} \, {3, 15}
\tfrac{3}{5} \, {2, 10}
\tfrac{4}{5} \, {2, 4, 20}
\tfrac{1}{6} \, {6}
\tfrac{5}{6} \, {2, 3}
\tfrac{1}{7} \, {7}
\tfrac{2}{7} \, {4, ...}
\tfrac{3}{7} \, {3, ...}
\tfrac{4}{7} \, {2, ...}
\tfrac{5}{7} \, {2, ...}
\tfrac{6}{7} \, {2, ...}
\tfrac{1}{8} \, {8}
\tfrac{3}{8} \, {3, ...}
\tfrac{5}{8} \, {2, ...}
\tfrac{7}{8} \, {2, ...}
\tfrac{1}{9} \, {9}
\tfrac{2}{9} \, {5, ...}
\tfrac{4}{9} \, {3, ...}
\tfrac{5}{9} \, {2, ...}
\tfrac{7}{9} \, {2, ...}
\tfrac{8}{9} \, {2, ...}
\tfrac{1}{10} \, {10}
\tfrac{3}{10} \, {4, ...}
\tfrac{7}{10} \, {2, ...}
\tfrac{9}{10} \, {2, ...}


Greedy algorithm for Egyptian representation

Fibonacci's algorithm for the greedy Egyptian representation

E = \sum_{\stackrel {i \ge 1}{E_i > 0}} E_i \,

of a rational number \scriptstyle r \,=\, \frac{m}{n} \,<\, 1 \, is

r_0 = r, r_i = r_{i-1} - E_{i},\quad i \ge 1, \,
E_i = \frac{1}{e_i},\, e_i = \Bigg\lceil \frac{1}{r_{i-1}} \Bigg\rceil,\quad i \ge 1, \,

where \scriptstyle \lceil\cdot\rceil \, is the ceiling function.

Greedy signed Egyptian representation

A signed Egyptian representation of a real number \scriptstyle r \, is a sum of negative or positive (usually) distinct unit fractions equal to \scriptstyle r \,. The (unique) greedy signed Egyptian representation uses the greedy algorithm for signed Egyptian representation.

Greedy signed Egyptian representation of positive rational numbers less than 1

Greedy signed Egyptian representation
\scriptstyle \frac{m}{n} \, Signed denominators of distinct signed unit fractions of the greedy signed Egyptian representation

of positive rational numbers less than 1

\tfrac{1}{2} \, {2}
\tfrac{1}{3} \, {3}
\tfrac{2}{3} \, {2, 3}
\tfrac{1}{4} \, {4}
\tfrac{3}{4} \, {1, -4}
\tfrac{1}{5} \, {5}
\tfrac{2}{5} \, {3, 15}
\tfrac{3}{5} \, {1, ...}
\tfrac{4}{5} \, {1, ...}
\tfrac{1}{6} \, {6}
\tfrac{5}{6} \, {1, ...}
\tfrac{1}{7} \, {7}
\tfrac{2}{7} \, {4, ...}
\tfrac{3}{7} \, {2, }
\tfrac{4}{7} \, {2, ...}
\tfrac{5}{7} \, {1, ...}
\tfrac{6}{7} \, {1, ...}
\tfrac{1}{8} \, {8}
\tfrac{3}{8} \, {3, ...}
\tfrac{5}{8} \, {2, ...}
\tfrac{7}{8} \, {1, ...}
\tfrac{1}{9} \, {9}
\tfrac{2}{9} \, {5, ...}
\tfrac{4}{9} \, {2, ...}
\tfrac{5}{9} \, {2, ...}
\tfrac{7}{9} \, {1, ...}
\tfrac{8}{9} \, {1, ...}
\tfrac{1}{10} \, {10}
\tfrac{3}{10} \, {3, ...}
\tfrac{7}{10} \, {1, ...}
\tfrac{9}{10} \, {1, ...}


Greedy algorithm for signed Egyptian representation

***** NEEDS DOUBLECHECKING *****

The greedy algorithm for the signed Egyptian representation

S = \sum_{\stackrel {i \ge 1}{S_i > 0}} (-1)^{H(r_{i-1})} ~ |S_i|, \,

where \scriptstyle H(x) \, is the Heaviside step function, of a rational number \scriptstyle r \,=\, \frac{m}{n} \,<\, 1 \, is

r_0 = r, r_i = r_{i-1} - S_{i},\quad i \ge 1, \,
S_i = \frac{1}{s_i},\, s_i = \Bigg[ \frac{1}{r_{i-1}} \Bigg],\quad i \ge 1, \,

where \scriptstyle [x] = \lfloor x + \frac{1}{2} \rfloor \, is the nearest integer function.

Sequences

Denominators of distinct unit fractions (less than 1) of the greedy Egyptian representation of rational numbers (less than 1) ordered by increasing denominators, then by increasing coprime numerators of those rational numbers

{{2}, {3}, {2, 6}, {4}, {2, 4}, {5}, {3, 15}, {2, 10}, {2, 4, 20}, {6}, {2, 3}, {7}, ...}

whose concatenation gives (Cf. A??????)

{2, 3, 2, 6, 2, 4, 5, 3, 15, 2, 10, 2, 4, 20, 6, 2, 3, 7, ...}

See also

Retrieved from "http://oeis.org/wiki/Greedy_Egyptian_representation"
Personal tools