Project Euler 57: Square root convergents
2024-09-01 18:01:15
五十七、平方根收敛(Square root convergents)
二的平方根可以表示为以下这个无穷连分数:
\[\sqrt 2 =1+ \frac 1 {2+ \frac 1 {2 +\frac 1 {2+ \dots}}}
\]通过把前四项展开,我们得到:
\[\begin{aligned}1 + \frac 1 2 &= \frac 32 = 1.5\\1 + \frac 1 {2 + \frac 1 2} &= \frac 7 5 = 1.4\\1 + \frac 1 {2 + \frac 1 {2+\frac 1 2}} &= \frac {17}{12} = 1.41666 \dots\\1 + \frac 1 {2 + \frac 1 {2+\frac 1 {2+\frac 1 2}}} &= \frac {41}{29} = 1.41379 \dots\end{aligned}
\]接下来三项展开式为\(99/70,239/169\)和\(577/408\),但是第八项是\(1393/985\),是第一个分子的位数超过分母的位数的例子。
求在前一千项展开式中,有多少分数的分子位数超过分母的位数?
分析:首先我们可以推导出上面的展开式中分子和分母的递推式:设\(a_k=n_k/d_k\)表示第\(k\)项展开式,则易知:
\[a_{k+1}=1+\frac{1}{1+a_k}=1+\frac{1}{1+n_k/d_k}=1+\frac{d_k}{d_k+n_k}=\frac{2d_k+n_k}{d_k+n_k}
\]
\]
即对于第\(k+1\)项展开式,其分子为\(2d_k+n_k\),分母为\(d_k+n_k\)。因此我们可以根据这个递推关系计算每一项展开式的分子与分母,对其取以十为底的对数判断其位数,然后统计分子位数大于分母位数的项,即为题目所求。代码如下:
# time cost = 885 µs ± 9.93 µs
from math import log10
def main(N=1000):
c,n,d = 0,1,1
for i in range(N):
n,d = 2 * d + n,d + n
if int(log10(n)) > int(log10(d)):
c += 1
return c
最新文章
- jdbcTemplate批量插入(添加)
- ES5基础之正则表达式02:范围类、预定义类和边界字符
- 【转载】Chaotic Time-Series Prediction
- 64位系统里的IIS运行32位ODP.NET的方法
- Oracle Recommended Patches -- ";Oracle JavaVM Component Database PSU"; (OJVM PSU) Patches (文档 ID 1929745.1)
- EasyUI 我的第一个窗口
- LSTM网络(Long Short-Term Memory )
- URAL 1024 Permutations(LCM)
- 简单说pyglet.event
- Sass入门:第二章
- 【THUSC2017】【LOJ2982】宇宙广播 计算几何 高斯消元
- 三元运算和bytes数据类型笔记
- Docker学习笔记:基础
- PHP反序列化与Session
- 小程序动态添加class及调接口传递多个参数
- Netty4.0学习笔记系列之二:Handler的执行顺序
- EF 多对多循环引用序列化失败 解决办法
- 设置TableView section header的颜色
- Elementary Sorts
- Android开发之Navigationdrawer导航抽屉功能的实现(源码分享)