Engel expansion
Engel expansion is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
The Engel expansion of a positive real number x is the unique non-decreasing sequence of positive integers { a1, a2, a3 ... } such that
x = 1 / a1 + 1 / a1a2 + 1 / a1a2a3 ...
In other words, each term is the reciprocal of the cumulative product of the expansion and x is the sum of those terms.
Rational numbers have a finite Engel expansion, while irrational numbers have an infinite Engel expansion.
Tiny amount of imprecision can cause wild variation from actual values as the (reciprocal) terms grow smaller. It can be quite challenging to maintain precision.
- Task
- Write routines (functions, procedures, whatever it may be called in your language) to convert a rational number to an Engel expansion representation and from an Engle expansion to a rational number.
- Demonstrate converting some rational numbers to an Engel expansion and back.
Test it with at least the following rational approximations of:
- π - 3.14159265358979
- π - 2.71828182845904
- β2 - 1.414213562373095
- Stretch
- If your language supports high precision rational numbers, do the same with at least:
- π - 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211
- π - 2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642743
- β2 - 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927558
There almost definitely will be some imprecision in the later terms. Feel free to limit the display of the expansion to the first 30 terms.
- See also
Raku
<lang perl6>sub to-engel ( $rat ) {
my $u = $rat;
do while $u { my $a = ceiling 1 / $u; $u = $u Γ $a - 1; $a }
}
sub from-engel (@expanded) { sum [\Γ] @expanded.map: { FatRat.new: 1, $_ } }
for flat
# low precision π, π, β2 and 1.5 to a power 3.14159265358979, 2.71828182845904, 1.414213562373095, 1.5 ** 5,
# high precision π, π, and β2 and 1.5 to a power 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211.FatRat,
2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642743.FatRat,
1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927558.FatRat,
1.5 ** 8
-> $rat {
say "Rational number: $rat";
my @expanded = $rat.&to-engel;
put "Engel expansion: " ~ @expanded.head(30);
say "Converted back to rational: " ~ @expanded.&from-engel;
put ;
}</lang>
- Output:
Rational number: 3.14159265358979 Engel expansion: 1 1 1 8 8 17 19 300 1991 2768 4442 4830 10560 37132 107315 244141 651042 1953125 Converted back to rational: 3.14159265358979 Rational number: 2.71828182845904 Engel expansion: 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 82 144 321 2289 9041 21083 474060 887785 976563 1953125 Converted back to rational: 2.71828182845904 Rational number: 1.414213562373095 Engel expansion: 1 3 5 5 16 18 78 102 120 144 260 968 18531 46065 63005 65105 78125 Converted back to rational: 1.414213562373095 Rational number: 7.59375 Engel expansion: 1 1 1 1 1 1 1 2 6 8 Converted back to rational: 7.59375 Rational number: 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211 Engel expansion: 1 1 1 8 8 17 19 300 1991 2492 7236 10586 34588 63403 70637 1236467 5417668 5515697 5633167 7458122 9637848 9805775 41840855 58408380 213130873 424342175 2366457522 4109464489 21846713216 27803071890 Converted back to rational: 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211 Rational number: 2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642743 Engel expansion: 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 Converted back to rational: 2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642743 Rational number: 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927558 Engel expansion: 1 3 5 5 16 18 78 102 120 144 251 363 1402 31169 88630 184655 259252 298770 4196070 38538874 616984563 1975413035 5345718057 27843871197 54516286513 334398528974 445879679626 495957494386 2450869042061 2629541150527 Converted back to rational: 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927558 Rational number: 25.628906 Engel expansion: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 32 Converted back to rational: 25.628906