About one task that is no longer offered at the interview

In one company, the following task was proposed to candidates for a programmer’s vacancy. Find fraction value:

$$

$$\ frac {1} {1+ \ frac {1} {1+ \ frac {1} {1+ \ frac {1} {1 + ...}}}}$$

To solve this problem, knowledge of the nature of such fractions and the area in which these fractions are applied is not required. It is only necessary to note that the proposed expression is self-similar and can be represented as:

$$

$$x = \ frac {1} {1 + x}$$

And this, in turn, leads to the usual quadratic equation:

$$

$$x ^ 2 + x-1 = 0 \\ x = \ frac {sqrt (5) -1} {2} \\ x = 0.618033988 ...$$

Now let's say that these fractions have a special name, these are continued fractions, and they are used as one of the forms for recording real numbers. In this example, the infinite continued fraction has the simplest representation. In her record only units are used, and the length of her period is also equal to one. It is curious that the number it expresses is very widely represented, and not only in the mathematical world, and even has its own name — the reciprocal of the “golden section”. We obtain several approximations for a given number using its representation via a continued fraction. In the first step, we discard the second term in the denominator. Will get $$$\ frac {1} {1}$ , we now write the following approximation, using the result obtained, as the second term in the sum under the fraction sign $$$\ frac {1} {1+ \ frac {1} {1}} = \ frac {1} {2}$ Repeat this operation again. $$$\ frac {1} {1+ \ frac {1} {2}} = \ frac {2} {3}$ As a result, we get the following row:

$$

$$\ frac {1} {1}, \ frac {1} {2}, \ frac {2} {3}, \ frac {3} {5}, \ frac {5} {8}, \ frac {8 } {13} ...$$

We now turn to such a concept as the Fibonacci sequence. So called members of the number series, compiled according to the following rule. The first and second members of the series are equal to one, and each succeeding is equal to the sum of the two previous ones.

$$

$$1,1,2,3,5,8,13,21 ...$$

Compose a series formed by the relations of two adjacent members of the Fibonacci sequence

$$

$$\ frac {1} {1}, \ frac {1} {2}, \ frac {2} {3}, \ frac {3} {5}, \ frac {5} {8}, \ frac {8 } {13} ...$$

Isn't it a familiar record? Indeed, the limit of the ratio of two Fibonacci numbers is expressed by the reciprocal of the “golden section”. We get this result.
From the definition it follows that

$$

$$F_ {i + 1} = F_i + F_ {i-1}$$

$$

$$\ frac {F_ {i + 1}} {F_i} = 1 + \ frac {F_ {i-1}} {F_i}$$

We introduce the following notation

$$

$$s_ {i-j} = \ frac {F_i} {F_j}$$

Then the previous equality is written as

$$

$$s_1 = 1 + s _ {- 1}$$

In the limit

$$

$$s_1 = \ frac {1} {s _ {- 1}}$$

We introduce the notation $$$x = s _ {- 1}$ . Then we get the equation that was already given at the beginning of the article.

$$

$$x = \ frac {1} {1 + x}$$

Now consider the sequence in which the first three terms are equal to one, and each succeeding is the sum of the three previous ones.

$$

$$1,1,1,3,5,9,17,31,57,105, ...$$

Let us find the limit to which the ratio of two neighboring terms of the sequence tends. By definition

$$

$$F_ {i + 3} = F_i + F_ {i + 1} + F_ {i + 2}$$

Divide the left and right side into $$$F_ {i + 1}$ . Then, in the notation used earlier, we can write:

$$

$$s_2 = s _ {- 1} + s_1 + 1$$

Now divide the left and right side $$$F_ {i + 2}$ . We get the following relation:

$$

$$s_1 = s _ {- 2} + s _ {- 1} + 1$$

Denote

$$

$$s_1 = x \\ s_2 = y$$

In the new notation, the system of equations will look like this:

$$

$$y = \ frac {1} {x} + x + 1 \\ x = \ frac {1} {x} + \ frac {1} {y} + 1$$

This system is given to the following equation:

$$

$$y ^ 3-3y ^ 2-y-1 = 0$$

It has one real solution.

$$

$$y = 3.382976 ...$$

If we consider a series for a sequence in which each member is equal to the sum of the previous four,

$$

$$1,1,1,1,4,7,13,25,49,94,181,349, ...$$

then we come to a system of three equations:

$$

$$z = x + y + \ frac {1} {x} +1 \\ y = x + \ frac {1} {x} + \ frac {1} {y} +1 \\ x = \ frac {1} { z} + \ frac {1} {y} + \ frac {1} {x} +1$$

And this system is reduced to the following nonlinear equation:

$$

$$y ^ 4-3y ^ 3-3y ^ 2 + y + 1 = 0$$

This equation has two real roots. The solution to our problem will be:

$$

$$y = 3,715,495 ...$$

These are the observations that occurred thanks to one task at the interview.