Detailed mathematical approach

Problem Summary

For a real number \(\theta > 1\), define \(b_1=\theta\) and then iterate

$a_n=\lfloor b_n\rfloor,\qquad b_{n+1}=a_n\bigl(b_n-a_n+1\bigr).$

The integer part \(a_1\) becomes the integer part of a decimal number, and every later value \(a_2,a_3,a_4,\ldots\) is written after the decimal point by direct concatenation. If one of these values has several digits, all of those digits are appended.

The goal is to find the fixed point for which this concatenated decimal equals the original \(\theta\), and then report that value rounded to 24 decimal places.

Mathematical Approach

The recurrence generates a deterministic sequence of integers from any starting value \(\theta\). Writing \(d_k\) for the number of decimal digits of \(a_k\) when \(k\ge 2\), the concatenation map can be written as

$\tau(\theta)=a_1+\sum_{k=2}^{\infty} a_k\,10^{-(d_2+d_3+\cdots+d_k)}.$

So the problem becomes a fixed-point equation

$\tau(\theta)=\theta.$

Step 1: Understand the recurrence locally

Write

$b_n=a_n+\delta_n,\qquad 0\le \delta_n<1.$

Then the update rule becomes

$b_{n+1}=a_n(1+\delta_n).$

Because \(0\le \delta_n<1\), we immediately get the useful bound

$a_n\le b_{n+1}<2a_n.$

Taking floors shows that every next block is constrained by

$a_{n+1}\in\{a_n,a_n+1,\ldots,2a_n-1\}.$

This explains why the generated blocks grow in a controlled way rather than exploding unpredictably.

Step 2: Convert the sequence into a decimal operator

The decimal is not formed by ordinary place values of single digits, because the blocks \(a_n\) may have several digits. The exponent in the formula for \(\tau(\theta)\) therefore depends on cumulative digit lengths.

If, for example, the generated blocks begin

$a_1=2,\quad a_2=3,\quad a_3=5,\quad a_4=8,\quad a_5=13,$

then the concatenated value begins

$2.35813\ldots$

rather than \(2.3+0.05+0.008+\cdots\). The explicit digit-length formula above is the correct way to encode this concatenation mathematically.

Step 3: Turn the problem into fixed-point iteration

Once \(\tau\) is defined, the natural numerical strategy is to iterate

$\theta_{t+1}=\tau(\theta_t).$

The implementations start from the practical seed \(2.2\). Repeated application of the concatenation map quickly stabilizes a long leading decimal prefix, and once many guard digits agree, the final 24-digit rounding is determined.

This is the central idea of the solution: instead of solving the fixed-point equation symbolically, it is solved numerically by repeatedly rebuilding the decimal number produced by the recurrence.

Step 4: Evaluate only a finite prefix and bound the error

In practice we do not need the full infinite decimal expansion of \(\tau(\theta)\). If we stop after collecting \(D\) digits after the decimal point, we obtain a truncated value \(\tau_D(\theta)\).

Because truncating any positive decimal after \(D\) fractional digits changes its value by less than one unit in the next place, we have

$0\le \tau(\theta)-\tau_D(\theta)<10^{-D}.$

The implementations use \(D=80\), leaving a margin of 56 extra digits beyond the required 24. That makes the final rounding step numerically safe once the fixed-point iteration has stabilized.

Worked Example: A sample that produces Fibonacci numbers

A useful checkpoint is the sample starting value

$\theta=2.956938891377988.$

Then

$b_1=2.956938891377988,\qquad a_1=\lfloor b_1\rfloor=2.$

The next updates are

$b_2=2(2.956938891377988-2+1)=3.913877782755976,\qquad a_2=3,$

$b_3=3(3.913877782755976-3+1)=5.741633348267928,\qquad a_3=5,$

$b_4=5(5.741633348267928-5+1)=8.70816674133964,\qquad a_4=8.$

Continuing the same recurrence yields

$a_5=13,\quad a_6=21,\quad a_7=34,\quad a_8=55,\quad a_9=89,\quad a_{10}=144.$

So the concatenated decimal begins

$\tau(\theta)=2.3581321345589144\ldots$

This example is valuable because it shows exactly how multi-digit blocks such as \(13\), \(21\), and \(144\) are appended.

How the Code Works

The C++, Python, and Java implementations all follow the same numerical plan. They work with high-precision decimal arithmetic, start from \(2.2\), generate the recurrence, and rebuild the concatenated decimal until 80 fractional digits have been collected. That truncated decimal becomes the next iterate.

The C++ and Java implementations perform this fixed-point iteration directly for 30 rounds and then round the final value to 24 decimal places. The Python entry point delegates to the same C++ computation, so its mathematical behavior is identical to the C++ version rather than being a separate algorithm.

Complexity Analysis

Let \(P\) be the working number of fractional digits, \(K\) the number of generated blocks needed to reach that precision in one evaluation of \(\tau\), and \(I\) the number of fixed-point iterations. One evaluation performs \(K\) recurrence updates with \(P\)-digit decimal arithmetic and appends about \(P\) output characters overall, so a reasonable asymptotic description is \(O(IKP)\) time and \(O(P)\) memory. In the concrete implementations here, \(P=80\) and \(I=30\), so the computation is effectively constant-time for this single Project Euler instance.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=751
2. Fixed-point iteration: Wikipedia - Fixed-point iteration
3. Floor and ceiling functions: Wikipedia - Floor and ceiling functions
4. Arbitrary-precision arithmetic: Wikipedia - Arbitrary-precision arithmetic
5. Decimal representation: Wikipedia - Decimal representation