论坛 › 欧拉计划（Project Euler） › 题目57：考察2的平方根的展开

欧拉计划 发表于 2015-6-18 23:37:22

题目57：考察2的平方根的展开

Square root convergents

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

By expanding this for the first four iterations, we get:

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

题目：

2 的平方根可以被表示为无限延伸的分数：

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

将其前四次迭代展开，我们得到：

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

接下来三次迭代的展开是 99/70, 239/169, 和 577/408, 但是第八次迭代的展开, 1393/985, 是第一个分子的位数超过分母的位数的例子。

在前 1000 次迭代的展开中，有多少个的分子位数超过分母位数？

迷雾少年 发表于 2016-8-31 20:02:20

153..

jerryxjr1220 发表于 2016-9-29 03:52:59

完全正确
153


fenmu, fenzi, count = , , 0
for i in range(1,1000):
        fenmu.append (fenzi+fenmu)
        fenzi.append (fenmu+fenmu)
for j in range(1000):
        if len(str(fenzi)) > len(str(fenmu)):
                count += 1
print (count)

愤怒的大头菇 发表于 2016-11-22 10:38:51

from fractions import Fraction
count = 0
for i in range(1,1001):
    temp = 2+Fraction(1,2)
    while i:
      if i ==1:
            temp = 1+1/temp
      else:
            temp = 2+1/temp
      i -= 1
    (a,b) = str(temp).split('/')
    if len(a) > len(b):
      count += 1
print(count)
结果：153.
很慢

芒果加黄桃 发表于 2017-1-17 16:11:07

# encoding:utf-8
# 考察2的平方根展开
from time import time
def euler057(N=1000000):
    a, b = 1, 2
    count = 0
    for i in range(1, 1000):
      a, b = b, a + 2 * b
      if len(str(a + b)) > len(str(b)):
            # print(a+b,b,(a+b)/b)
            count += 1
    print(count)
if __name__ == '__main__':
    start = time()
    euler057()
    print('cost %.6f sec' % (time() - start))
153
cost 0.006001 sec

飘飞的白杨 发表于 2017-1-21 20:38:04

1,    1+1/2
2,    1+2/5      1+2/(2*2+1)
3,    1+5/12    1+5/(2*5+2)
4,    1+12/291+12/(2*12+5)
......
以此类推
from time import time
ttt = time()
N, count, n, m = 1, 0, 1, 2
while N <= 1000:
    n, m = m, m*2 + n
    if len(str(n+m)) > len(str(m)):
      count += 1
    N += 1
print(count, time()-ttt)

渡风 发表于 2017-6-17 00:16:30

本帖最后由 渡风 于 2017-6-17 00:19 编辑

此代码使用matlab编程
Problem57所用时间为： 3.1446秒
Problem57的答案为： 153
%% Problem57.m
% 最后编辑时间：17-06-17 0:02
% 问题：考察2的平方根的展开
%事实上可以先求出小于等于100w的数，然后用总数减去之
% Problem57所用时间为： 3.1446秒
% Problem57的答案为： 153

function Output = Problem57()
tic

Total = 0;
Demo = 2; %分母
Elem = 3; %分子

for ii = 1:999
    NewEl = Vector_Plus(Vector_Plus(Demo,Demo), Elem);
    NewDe = Vector_Plus(Demo, Elem);
    if length(NewEl) >length(NewDe)
      Total = Total + 1;
    end
    disp(Demo)
    Demo = NewDe;
    Elem = NewEl;
end
   
Output = Total;   
                     
toc
disp('此代码使用matlab编程')
disp(['Problem57所用时间为： ',num2str(toc),'秒'])
disp(['Problem57的答案为： ',num2str(Output)])
end
%此程序实现两个向量的加法
function Output=Vector_Plus(a,b)
if nargin==0
    a=;
    b=;
end
L1=length(a);
L2=length(b);
L=max(L1,L2);
if L1<L2
   Span=L2-L1;
   Newa=;
   Newb=b;
elseif L1>L2
   Span=L1-L2;
   Newa=a;
   Newb=;
else
    Newa=a;
    Newb=b;
end
Rank=Newa+Newb;
for ii=L:-1:2
    if Rank(ii)>=10
      Rank(ii)=Rank(ii)-10;
      Rank(ii-1)=Rank(ii-1)+1;
    end
end
Biggest=0;
while (Rank(1)>=10)
    if Rank(1)>=10
       Rank(1)=Rank(1)-10;
       Biggest=Biggest+1;
    end
end
if Biggest>0
    Output=;
else
    Output=Rank;
end
end
      
   

najin 发表于 2017-10-1 18:19:23

用的matlab
结果是：
   153

时间已过 0.016199 秒。
>>

hk1057 发表于 2018-8-1 20:47:27

import time
from fractions import Fraction


def time_it():
        start=time.time()
        fun()
        end=time.time()
        print('cost %.6f Secs'%(end-start))


def get_root(time):
        n=1
        m=2
        for i in range(time):
                f=Fraction(n,m)
                n,m=m,2*m+n
        return 1+f


def fun():
        sum_f=1
        count=0
        list_num=[]
        for i in range(1,1001):
                f= get_root(i)
                numerator=f.numerator
                denominator=f.denominator
                if len(str(numerator)) > len(str(denominator)):#分子位数超过分母位数
                        count+=1
                        list_num.append(f)
        print('前1000次迭代中,有%d次迭代中分子位数超过分母位数'%count)


if __name__=='__main__':
        time_it()

'''
前1000次迭代中,有153次迭代中分子位数超过分母位数
cost 4.505202 Secs
'''

王小召 发表于 2019-6-26 09:37:50

Fib 数列问题

计数：153 次
用时：0.156001 秒

import time

def Fib(N, a, b):
    n, a, b = 0, a, b
    while n < N:
      yield a
      a, b = b,2*b + a
      n += 1


def cal_result():
    count = 0
    fenzi =
    fenmu =
    for i in range(1000):
      if len(str(fenzi)) > len(str(fenmu)):
            count += 1
    return count
print("计数：{} 次\n用时：{} 秒".format(cal_result(), time.process_time()))

永恒的蓝色梦想 发表于 2019-7-23 18:55:26

本帖最后由 永恒的蓝色梦想 于 2021-1-13 12:33 编辑

nume = 1
deno = 2
count = 0

for _ in range(1, 1000):
    nume, deno = deno, nume + 2 * deno
    count += len(str(nume + deno)) > len(str(deno))

print(count)

debuggerzh 发表于 2020-8-21 19:31:45

153

Process returned 0 (0x0)   execution time : 0.061 s
Press any key to continue.
重载了+运算的高精度
#include<iostream>
#include<vector>
using namespace std;

typedef struct BigInt{
vector<int> v;

BigInt(vector<int> v):v(v){}
}BI;

BI operator + (const BI & a,const BI & x){
vector<int> t1 = a.v;
vector<int> t2 = x.v;
if (a.v.size() < x.v.size())swap(t1,t2);

for (int i = 0;i < max(t1.size(),t2.size() );i++){
      if (i < t2.size())t1 += t2;
      if (i > 0 && t1 > 9){t1++;t1 -= 10;}
}

if (t1 > 9)
    if (t1.size() == t2.size() ){t1.push_back(1);t1 -= 10;}

    else {
      t1++;
      for (int i = t2.size();i < t1.size()-1;i++){
      if (t1 > 9) {t1 -= 10;t1++;}
      else break;
      }
      t1 -= 10;
    }
return BI(t1);
}

int main(){
int cnt = 0;
vector<int> a(1,1),b(2,1);
BI n(a),d(b);

for (int i = 0;i < 1000;i++){
    BI t = n;
    n = d;
    d = t + d + d;

    BI u = n + d;
    if (u.v.size() > d.v.size())cnt++;
}
cout << cnt << endl;
return 0;
}

4444567 发表于 2020-10-28 21:27:07

用时from time import time

t = time()
a = 3#a是分子
b = 2#b是分母
l1 = []
count = 1000
while count:
    c = b #上一个数的分母
    b = a+b
    a = b+c
    if len(str(a))>len(str(b)):
      l1.append((a,b))
    count -= 1
   
print(l1,'\n')
print('用时%.6f sec,满足的数字有%d 个.' % (time()-t,len(l1)))0.373784 sec,满足的数字有153 个.应该是电脑问题，不然肯定要快一点。

guosl 发表于 2022-1-9 10:49:17

本帖最后由 guosl 于 2022-1-9 11:05 编辑

从这题开始，有一些列的题目都牵涉到了连分数，连分数的内容可以参考《初等数论》（闵嗣鹤 严士健编）一书。
对于一个连分数，若假设p(k)/q(k)为其的第k个渐进分数，则有：
p(1)=a1,p(2)=a2*a1+1,...,p(k)=ak*p(k-1)+p(k-2),...
q(1)=1,q(2)=a2,...,q(k)=ak*q(k-1)+q(k-2),...
对于本题则连分数为：是一个无限循环的连分数。套用前面给出的公式再结合mpir库，本题就非常简单了。{:10_257:}
/*
答案：153
*/
#include <iostream>
#include <string>
#include <mpirxx.h>
using namespace std;

int main(void)
{
mpz_class p0 = 1, p1 = 3, p2;
mpz_class q0 = 1, q1 = 2, q2;
int nCount = 0;
for (int i = 2; i <= 1000; ++i)
{
    p2 = 2 * p1 + p0;
    q2 = 2 * q1 + q0;
    string sp = p2.get_str();
    string sq = q2.get_str();
    if (sp.length() > sq.length())
      ++nCount;
    p0 = p1;
    p1 = p2;
    q0 = q1;
    q1 = q2;
}
cout << nCount << endl;
return 0;
}

Asss-whom 发表于 2022-8-8 17:20:32

use std::time::Instant;

fn main() {
    let now = Instant::now();
    // Copy from "[飘飞的白杨](https://fishc.com.cn/space-uid-359393.html)"
    let (mut num, mut n, mut m) = (0, 1, 2);
    for _ in 0..1001 {
      (n, m) = (m, m * 2 + n);
      if (n + m).to_string().len() > m.to_string().len() {
            num += 1;
      }
    }
    println!("{}", num);
    println!("", now.elapsed().as_secs_f32())
}

319

查看完整版本: 题目57：考察2的平方根的展开