Find a continued fraction that approximates Euler’s number

This notebook is an example of finding an arithmetic expression that evaluates to a given number. In this case the arithmetic expression is chosen to be of the form of a continued fraction and the target number is Euler’s number e.

References

[1]:

from math import e

import alogos as al

Search space

A recursive grammar that describes an infinite language for continued fractions that can be evaluated in Python.

[2]:

ebnf_text = """
S = CONST "+1/(" S ")" | CONST
CONST = DIGIT | DIGIT DIGIT
DIGIT = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
"""

grammar = al.Grammar(ebnf_text=ebnf_text)

Search goal

An objective function that evaluates the string, which represents a continued fraction, in order to get a number and returns the deviation from the target number e.

[3]:

def objective_function(string):
    number = eval(string)
    return abs(number-e)

Search an optimal string

[4]:

ea = al.EvolutionaryAlgorithm(
    grammar, objective_function, 'min', verbose=True,
    max_generations=200, population_size=200, offspring_size=200)
best_ind = ea.run()

Progress         Generations      Evaluations      Runtime (sec)    Best fitness
..... .....      10               1990             1.4              0.2917181715409547
..... .....      20               3871             1.7              0.13886102868381212
..... .....      30               5179             1.9              0.13886102868381212
..... .....      40               6668             2.0              0.004345236760967985
..... .....      50               8513             2.2              0.0003331105103270282
..... .....      60               10378            2.3              7.716783918088055e-06
..... .....      70               12318            2.6              8.319676370049933e-08
..... .....      80               14285            2.9              3.6071940989756968e-09
..... .....      90               16263            3.2              8.222178493610954e-11
..... .....      100              18251            3.6              1.4412027127264082e-11
..... .....      110              20234            3.9              1.3921752639589613e-11
..... .....      120              22216            4.5              1.3919532193540363e-11
..... .....      130              24172            4.8              1.3916867658281262e-11
..... .....      140              26160            5.2              1.3916867658281262e-11
..... .....      150              28142            5.7              1.3916867658281262e-11
..... .....      160              30130            6.4              1.1538769939534177e-11
..... .....      170              32102            7.0              1.1538769939534177e-11
..... .....      180              34000            7.3              1.1538769939534177e-11
..... .....      190              35876            7.5              1.1538769939534177e-11
..... .....      200              37727            7.8              1.1538769939534177e-11


Finished         200              37727            7.8              1.1538769939534177e-11

[5]:

best_str = best_ind.phenotype
print(best_str)

2+1/(1+1/(2+1/(1+1/(1+1/(4+1/(1+1/(1+1/(6+1/(1+1/(1+1/(8+1/(1+1/(1+1/(11))))))))))))))

[6]:

print('Target:', e)
print('Found: ', eval(best_str))

Target: 2.718281828459045
Found:  2.718281828470584