Project Euler 751

题目

Concatenation Coincidence

A non-decreasing sequence of integers $a_n$ can be generated from any positive real value $\theta$ by the following procedure:

$$\begin{aligned} \begin{split} b_1 &= \theta \\ b_n &= \left\lfloor b_{n-1} \right\rfloor \left(b_{n-1} - \left\lfloor b_{n-1} \right\rfloor + 1\right)~~~\forall ~ n \geq 2 \\ a_n &= \left\lfloor b_{n} \right\rfloor \end{split} \end{aligned}$$

Where $\left\lfloor . \right\rfloor$ is the floor function.

For example, $\theta=2.956938891377988\dots$ generates the Fibonacci sequence: $2, 3, 5, 8, 13, 21, 34, 55, 89, \dots$

The concatenation of a sequence of positive integers $a_n$ is a real value denoted $\tau$ constructed by concatenating the elements of the sequence after the decimal point, starting at $a_1$: $a_1.a_2a_3a_4\dots$

For example, the Fibonacci sequence constructed from $\theta=2.956938891377988\dots$ yields the concatenation $\tau=2.3581321345589\dots$ Clearly, $\tau \neq \theta$ for this value of $\theta$.

Find the only value of $\theta$ for which the generated sequence starts at $a_1=2$ and the concatenation of the generated sequence equals the original value: $\tau = \theta$. Give your answer rounded to $24$ places after the decimal point.

解决方案

当$a_1=2$时，也就是说$\theta$的整数部分只能是$2$，也就是说$2\le\theta<3$。在这个范围内，在浮点数上二分算法逼近所求$\theta$的值。虽然这个二分算法并非正确，但是它仍然输出了正确的答案。整体上$\tau$的增长速度比$\theta$快。

代码

N = 2
M = 24
l, r = N, N + 1
for _ in range(100):
    theta = 0.5 * (l + r)
    b = [theta]
    a = [int(theta)]
    for i in range(M):
        b.append(int(b[-1]) * (b[-1] - int(b[-1]) + 1))
        a.append(int(b[-1]))
    tau = str(a[0]) + "."
    for i in range(1, M):
        tau += str(a[i])
    tau = float(tau)
    if tau < theta:
        r = theta
    else:
        l = theta
ans = "{}.".format(a[0]) + "".join(str(x) for x in a[1:])[:M]
print(ans)