This site is supported by donations to The OEIS Foundation.

Greedy Egyptian representation

From OeisWiki
(Redirected from Sylvester's sequence)
Jump to: navigation, search


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



This article needs more work.

Please help by expanding it!


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

Greedy Egyptian representation of 1 in distinct unit fractions less than 1

1 =
1
2
 +
1
3
 +
1
7
 +
1
43
 +
1
1807
 +
1
3263443
 +
1
10650056950807
 +
1
113423713055421844361000443
 + ⋯

The denominators are given by the quadratic recurrence

a (1) = 2; a (n) = a (n − 1) [a (n − 1) − 1] + 1 = a (n − 1) 2 − a (n − 1) + 1, n ≥ 2.

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

a (n) = 1 +
 
n  − 1
∏
 
i   = 1
  
a (i), n ≥ 1,
where for
n = 1
 we get 1 + (empty product, i.e. 1) = 2.
A000058 Sylvester’s sequence:
a (n + 1) = a (n) 2  −  a (n) + 1
, with
a (0) = 2
. (Greedy Egyptian representation of 1.)
{2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443, 12864938683278671740537145998360961546653259485195807, ...}
Sylvester’s sequence, except for the first term (i.e. 2), is a subsequence of the central polygonal numbers (quasi-oblong numbers), where we start with the second (since
a (1) = 2
) term (i.e. 3), then use the value of the second term as the index (3) of the third term (i.e. 7), then use the value of the third term as the index (7) of the fourth term (i.e. 43), then use the value of the fourth term as the index (43) of the fourth term (i.e. 1807), and so on...
A002061 Central polygonal numbers:
n 2  −  n + 1, n   ≥   1
. (Quasi-oblong numbers:
(n  −  1) n + 1, n   ≥   1
.)
{1, 3, 7, 13, 21, 31, 43, 57, 73, 91, 111, 133, 157, 183, 211, 241, 273, 307, 343, 381, 421, 463, 507, 553, 601, 651, 703, 757, 813, 871, 931, 993, 1057, 1123, 1191, 1261, 1333, 1407, 1483, 1561, 1641, 1723, 1807, ...}

Greedy Egyptian representation of positive rational numbers less than 1

Greedy Egyptian representation
m
n
 		Denominators of distinct unit fractions of the greedy Egyptian representation
of positive rational numbers less than 1
1
2
 		{2}
1
3
 		{3}
2
3
 		{2, 6}
1
4
 		{4}
3
4
 		{2, 4}
1
5
 		{5}
2
5
 		{3, 15}
3
5
 		{2, 10}
4
5
 		{2, 4, 20}
1
6
 		{6}
5
6
 		{2, 3}
1
7
 		{7}
2
7
 		{4, ...}
3
7
 		{3, ...}
4
7
 		{2, ...}
5
7
 		{2, ...}
6
7
 		{2, ...}
1
8
 		{8}
3
8
 		{3, ...}
5
8
 		{2, ...}
7
8
 		{2, ...}
1
9
 		{9}
2
9
 		{5, ...}
4
9
 		{3, ...}
5
9
 		{2, ...}
7
9
 		{2, ...}
8
9
 		{2, ...}
1
10
 		{10}
3
10
 		{4, ...}
7
10
 		{2, ...}
9
10
 		{2, ...}

Greedy algorithm for Egyptian representation

Fibonacci’s algorithm for the greedy Egyptian representation

of a rational number
r =
m
n
 < 1
 is
r0 = r ; ri = ri  − 1 − Ei , i ≥ 1,

where

Ei =
1
ei
, ei =
1
ri  − 1
, i ≥ 1,
where
⌈ ·⌉
 is the ceiling function.

Greedy signed Egyptian representation

A signed Egyptian representation of a real number
r
 is a sum of negative or positive (usually) distinct unit fractions equal to
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
m
n
 		Signed denominators of distinct signed unit fractions of the greedy signed Egyptian representation
of positive rational numbers less than 1
1
2
 		{2}
1
3
 		{3}
2
3
 		{2, 6}
1
4
 		{4}
3
4
 		{2, 4}
1
5
 		{5}
2
5
 		{2, −10}
3
5
 		{2, 10}
4
5
 		{2, ...}
1
6
 		{6}
5
6
 		{2, 3}
1
7
 		{7}
2
7
 		{4, 28}
3
7
 		{2, −14}
4
7
 		{2, 14}
5
7
 		{2, ...}
6
7
 		{2, ...}
1
8
 		{8}
3
8
 		{2, −8}
5
8
 		{2, 8}
7
8
 		{2, ...}
1
9
 		{9}
2
9
 		{4, −36}
4
9
 		{2, −18}
5
9
 		{2, 18}
7
9
 		{2, ...}
8
9
 		{2, ...}
1
10
 		{10}
3
10
 		{3, −30}
7
10
 		{2, 5}
9
10
 		{2, ...}

Greedy algorithm for signed Egyptian representation

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

The greedy algorithm for the signed Egyptian representation

where
H (x)
 is the Heaviside step function, of a rational number
r =
m
n
 < 1
 is
r0  =  r ; ri  =  ri − 1 − Si , i ≥ 1,
Si  = 
1
si
, si  = 
1
ri  − 1
 , i ≥ 1,
where
[x] =
⌊   x +
1
2
⌋
 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 the following sequence.

A??????

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

See also

Retrieved from "https://oeis.org/w/index.php?title=Greedy_Egyptian_representation&oldid=1636765#Greedy_Egyptian_representation_of_1_in_unit_fractions_less_than_1"