Project Euler 197

发表于 2022-05-17 更新于 2023-07-03 分类于 Project Euler 阅读次数： 85 本文字数： 407 阅读时长 ≈ 1 分钟

Project Euler 197

题目

Investigating the behaviour of a recursively defined sequence

Given is the function $f (x) = ⌊ 2^{30.403243784} - x^{2} ⌋ \times 10^{- 9}$ ( $⌊ ⌋$ is the floor-function), the sequence $u_{n}$ is defined by $u_{0} = - 1$ and $u_{n + 1} = f (u_{n})$ .

Find $u_{n} + u_{n + 1}$ for $n = 10^{12}$ .

Give your answer with $9$ digits after the decimal point.

解决方案

将序列打印出多项后发现，到了某一个下标（大约 $600$ 前后）之后，数列的值是两个数反复交替出现。因此枚举量为常数，直接模拟。

代码

N = 10 ** 12
M = min(N, 600)


def f(x: float):
    return int(2 ** (30.403243784 - x * x)) * 1e-9


a = [-1]
for i in range(M):
    a.append(f(a[-1]))
ans = a[M] + a[M - 1]
print(ans)