Generalization of the "counting" algorithm

Let's consider now the class of the (n, k, 1)-algorithms acting on the line segment AB (Fig.1).

The first step of the optimal (n, k, 1)-algorithm
Figure 1. The first step of the optimal (n, k, 1)-algorithm.

Let's recall that the restriction of S º 1 means that the "Indicator Elements" move along the line segment AB in the only possible direction from the point A to the point B. It means that if any "Indicator Element" at any step is found to the right of the measurable point X, the "Indicator Element" will "leave the field", i.e. cannot be used for further measuring. The above-considered "counting" algorithm is the clear example of the restriction of S º 1.

We wouldn't like to tire our readers by the keenness of the mathematical reasoning and would like to give the final result. It was proved that the "effectiveness" function F(n, k) is expressed by using the binomial coefficients, that is:

(1)

The values of the "effectiveness" function are given with the next table ("arithmetical square").

 012345...n
0111111...1
1123456...F(n, 1)
2136101521...F(n, 2)
31410203556...F(n, 3)
415153570126...F(n, 4)
5162156126252...F(n, 5)
...........................
k1F(1, k)F(2, k)F(3, k)F(4, k)F(5, k)...F(n, k)

The action of the optimal (n, k, 1)-algorithm may be demonstrated with the help of the "arithmetical square". In fact, for the given n and k the value of the function F(n, k) is at the intersection of the n-th column and k-th row of the "arithmetical square". The co-ordinates of the k IEs applying to the points C1, C2, ..., Cj, Cj+1, ... , Ck about the point A (Fig.1) are in the n-th column of the arithmetical square, i.e.

AC1 = 1, AC2 = F(n, 1), ..., ACj = F(n, j-1), ACj+1 = F(n, j), ... , ACk = F(n, k-1).(2)

If after the first step of the algorithm the j IEs are found to the left of the point X and the rest of the (k - j) IEs are found to the right of X, the "indeterminacy interval" about X is diminished up to the line segment CjCj+1. The length of the latter is equal to F(n - 1, j). This binomial coefficient is at the intersection of the (n - 1)-th column and the j-th row of the arithmetical square. To get the binomial coefficient F(n - 1, j) we have to move from the initial coefficient F(n, k) in one column to the left and in (k - j) rows up.

At the second step we begin to consider the point Cj as the new beginning of the co-ordinates. Here the second step is applying the j IEs to the points D1, D2, ... , Dj of the new "indeterminacy interval" CjCj+1. The co-ordinates of the points D1, D2, ... , Dj about the point Cj, the new beginning of co-ordinates, are in the (n - 1)-th column of the arithmetical square, i.e.

CjD1 = 1, CjD2 = F(n - 1, 1), CjD3 = F(n - 1, 2), ..., CjDj = F(n - 1, j-1).(3)

This process lasts up to the exhaustion either of all the measurement steps or of all the IEs.

By way of example let's consider the optimal (3, 3, 1)-algorithm (Fig. 2).

The optimal (3, 3, 1)-algorithm
Figure 2. The optimal (3, 3, 1)-algorithm.

The latter consists of 3 steps and uses 3 IEs. The value of the initial "indeterminacy interval" is the number F(3, 3) = 20 that is at the intersection of the 3th column and the 3th row of the "arithmetical square".

The first step of the algorithm on the line segment [0, 20] is the applying the 3 IEs to the points 1, 4, 10 (Fig. 2). In accordance with the IEs "indications" one may arise 4 situations after the first step.

The second step.

1-a. For this situation the process of measurement is over because all the IEs are found to the right of the point X.

1-b. For this situation we have 1 IE, which is applied to the point 2.

1-c. For this situation we have 2 IE's, which are applied to the points 5 and 7.

1-d. For this situation we have 3 IEs. In this case the point 10 is a new beginning of the co-ordinates and 3 IE's are applied to the points 1, 3, 6 about the new beginning of co-ordinates. By summing over these numbers with the number 10 we can get the co-ordinates of the IE's applying points at the second step (11, 13, 16).

After the second step one may arise the following situations: [1,2], [2,4], [4,5], [5,7], [7,10], [10,11], [11,13], [13,16], [16,20]. Note that for the situations [1,2], [4,5], [10,11] the measurement process is over at the second step.

The third step.

For the situation [2,4], [5,7] and [11,13] the third step is applying 1 IE to the points 3, 6, 12 respectively.

For the situations [7,10] and [13,16] the third step is applying 2 IE's to the points 8, 9 and 14, 15 respectively.

For the situation [16,20] the third step is applying 3 IE's to the points 17, 18, 19.

What importance could have the "optimal" (n, k, 1)-algorithm for development of mathematics? It is important to emphasize that the "optimal" (n, k, 1)-algorithms are the wide generalization of the "counting" algorithm, which underlies the basis of the Pythagorean number theory. And possibly we can use the measurement algorithms based on "arithmetical square" for development of number theory?