题目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 次迭代的展开中，有多少个的分子位数超过分母位数？

迷雾少年

153..

jerryxjr1220

完全正确
153
[Finished in 0.1s]

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

愤怒的大头菇

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.
很慢

芒果加黄桃

# 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

飘飞的白杨

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/29  1+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)

渡风

此代码使用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=[9 9 9 9 9 9 ];
    b=[2 0];
end
L1=length(a);
L2=length(b);
L=max(L1,L2);
if L1<L2
   Span=L2-L1;
   Newa=[zeros(1,Span),a];
   Newb=b;
elseif L1>L2
   Span=L1-L2;
   Newa=a; 
   Newb=[zeros(1,Span),b];
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=[Biggest,Rank];
else
    Output=Rank;
end
end
        
   

najin

用的matlab
结果是：
   153

时间已过 0.016199 秒。
>>

hk1057

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
'''

王小召

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 = [_ for _ in Fib(1000, 3, 7)]
    fenmu = [_ for _ in Fib(1000, 2, 5)]
    for i in range(1000):
        if len(str(fenzi[i])) > len(str(fenmu[i])):
            count += 1
    return count
print("计数：{} 次\n用时：{} 秒".format(cal_result(), time.process_time()))

永恒的蓝色梦想

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

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[i] += t2[i];
      if (i > 0 && t1[i-1] > 9)  {t1[i]++;  t1[i-1] -= 10;}
  }

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

    else {
      t1[t2.size()]++;
      for (int i = t2.size();i < t1.size()-1;i++){
        if (t1[i] > 9) {t1[i] -= 10;  t1[i+1]++;}
        else break;
      }
      t1[t2.size()-1] -= 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

用时

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

从这题开始，有一些列的题目都牵涉到了连分数，连分数的内容可以参考《初等数论》（闵嗣鹤 严士健编）一书。
对于一个连分数[a1,a2,...ak...]，若假设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),...
对于本题则连分数为：[1,2,...,2,...]是一个无限循环的连分数。套用前面给出的公式再结合mpir库，本题就非常简单了。

/*
答案：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

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!("[Finished in {}s]", now.elapsed().as_secs_f32())
}

319
[Finished in 0.0004963s]