Why Searches Are Difficult

Lochs' theorem [2] states that to represent a decimal number with digits, we need about simple continued fraction terms. This means that when adding digits to our lists, the continued fraction digits and the radix digits get slowly out of sync. To ensure that the digits agree with each other, we need a pool size that becomes progressively larger.

Lochs' theorem holds in its classic form only for simple continued fractions. But experience shows that nonsimple continued fractions behave similarly. Let us analyze the best Trott constant found with more than 400 coinciding digits.

On average we obtain about 0.7 decimal digits per continued fraction digit.

The following graphics show the digit gain and the difference of the digit gain and its linear part.

The absolute difference shows similar behavior, though different in detail.