题目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

1. 完全正确
   
2. 153
   
3. [Finished in 0.1s]
   
4. 
   
5. fenmu, fenzi, count = [2], [3], 0
   
6. for i in range(1,1000):
   
7.         fenmu.append (fenzi[i-1]+fenmu[i-1])
   
8.         fenzi.append (fenmu[i]+fenmu[i-1])
   
9. for j in range(1000):
   
10.         if len(str(fenzi[j])) > len(str(fenmu[j])):
    
11.                 count += 1
    
12. print (count)

复制代码

愤怒的大头菇

1. from fractions import Fraction
   
2. count = 0
   
3. for i in range(1,1001):
   
4.     temp = 2+Fraction(1,2)
   
5.     while i:
   
6.         if i ==1:
   
7.             temp = 1+1/temp
   
8.         else:
   
9.             temp = 2+1/temp
   
10.         i -= 1
    
11.     (a,b) = str(temp).split('/')
    
12.     if len(a) > len(b):
    
13.         count += 1
    
14. print(count)

复制代码

结果：153.
很慢

芒果加黄桃

1. # encoding:utf-8
   
2. # 考察2的平方根展开
   
3. from time import time
   
4. def euler057(N=1000000):
   
5.     a, b = 1, 2
   
6.     count = 0
   
7.     for i in range(1, 1000):
   
8.         a, b = b, a + 2 * b
   
9.         if len(str(a + b)) > len(str(b)):
   
10.             # print(a+b,b,(a+b)/b)
    
11.             count += 1
    
12.     print(count)
    
13. if __name__ == '__main__':
    
14.     start = time()
    
15.     euler057()
    
16.     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)
......
以此类推

1. from time import time
   
2. ttt = time()
   
3. N, count, n, m = 1, 0, 1, 2
   
4. while N <= 1000:
   
5.     n, m = m, m*2 + n
   
6.     if len(str(n+m)) > len(str(m)):
   
7.         count += 1
   
8.     N += 1
   
9. print(count, time()-ttt)

复制代码

渡风

此代码使用matlab编程
Problem57所用时间为： 3.1446秒
Problem57的答案为： 153

1. %% Problem57.m
   
2. % 最后编辑时间：17-06-17 0:02
   
3. % 问题：考察2的平方根的展开
   
4. %事实上可以先求出小于等于100w的数，然后用总数减去之
   
5. % Problem57所用时间为： 3.1446秒
   
6. % Problem57的答案为： 153
   
7. 
   
8. function Output = Problem57()
   
9. tic
   
10. 
    
11. Total = 0;
    
12. Demo = 2; %分母
    
13. Elem = 3; %分子
    
14. 
    
15. for ii = 1:999
    
16.     NewEl = Vector_Plus(Vector_Plus(Demo,Demo), Elem);
    
17.     NewDe = Vector_Plus(Demo, Elem);
    
18.     if length(NewEl) >  length(NewDe)
    
19.         Total = Total + 1;
    
20.     end
    
21.     disp(Demo)
    
22.     Demo = NewDe;
    
23.     Elem = NewEl;
    
24. end
    
25.    
    
26. Output = Total;   
    
27.                      
    
28. toc
    
29. disp('此代码使用matlab编程')
    
30. disp(['Problem57所用时间为： ',num2str(toc),'秒'])
    
31. disp(['Problem57的答案为： ',num2str(Output)])
    
32. end
    
33. %此程序实现两个向量的加法
    
34. function Output=Vector_Plus(a,b)
    
35. if nargin==0
    
36.     a=[9 9 9 9 9 9 ];
    
37.     b=[2 0];
    
38. end
    
39. L1=length(a);
    
40. L2=length(b);
    
41. L=max(L1,L2);
    
42. if L1<L2
    
43.    Span=L2-L1;
    
44.    Newa=[zeros(1,Span),a];
    
45.    Newb=b;
    
46. elseif L1>L2
    
47.    Span=L1-L2;
    
48.    Newa=a;
    
49.    Newb=[zeros(1,Span),b];
    
50. else
    
51.     Newa=a;
    
52.     Newb=b;
    
53. end
    
54. Rank=Newa+Newb;
    
55. for ii=L:-1:2
    
56.     if Rank(ii)>=10
    
57.         Rank(ii)=Rank(ii)-10;
    
58.         Rank(ii-1)=Rank(ii-1)+1;
    
59.     end
    
60. end
    
61. Biggest=0;
    
62. while (Rank(1)>=10)
    
63.     if Rank(1)>=10
    
64.        Rank(1)=Rank(1)-10;
    
65.        Biggest=Biggest+1;
    
66.     end
    
67. end
    
68. if Biggest>0
    
69.     Output=[Biggest,Rank];
    
70. else
    
71.     Output=Rank;
    
72. end
    
73. end
    
74.         
    
75.    

复制代码

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 秒

1. import time
   
2. 
   
3. def Fib(N, a, b):
   
4.     n, a, b = 0, a, b
   
5.     while n < N:
   
6.         yield a
   
7.         a, b = b,  2*b + a
   
8.         n += 1
   
9. 
   
10. 
    
11. def cal_result():
    
12.     count = 0
    
13.     fenzi = [_ for _ in Fib(1000, 3, 7)]
    
14.     fenmu = [_ for _ in Fib(1000, 2, 5)]
    
15.     for i in range(1000):
    
16.         if len(str(fenzi[i])) > len(str(fenmu[i])):
    
17.             count += 1
    
18.     return count
    
19. print("计数：{} 次\n用时：{} 秒".format(cal_result(), time.process_time()))

复制代码

永恒的蓝色梦想

1. nume = 1
   
2. deno = 2
   
3. count = 0
   
4. 
   
5. for _ in range(1, 1000):
   
6.     nume, deno = deno, nume + 2 * deno
   
7.     count += len(str(nume + deno)) > len(str(deno))
   
8. 
   
9. print(count)

复制代码

debuggerzh

153

Process returned 0 (0x0)   execution time : 0.061 s
Press any key to continue.
重载了+运算的高精度

1. #include<iostream>
   
2. #include<vector>
   
3. using namespace std;
   
4. 
   
5. typedef struct BigInt{
   
6.   vector<int> v;
   
7. 
   
8.   BigInt(vector<int> v):v(v){}
   
9. }BI;
   
10. 
    
11. BI operator + (const BI & a,const BI & x){
    
12.   vector<int> t1 = a.v;
    
13.   vector<int> t2 = x.v;
    
14.   if (a.v.size() < x.v.size())  swap(t1,t2);
    
15. 
    
16.   for (int i = 0;i < max(t1.size(),t2.size() );i++){
    
17.       if (i < t2.size())  t1[i] += t2[i];
    
18.       if (i > 0 && t1[i-1] > 9)  {t1[i]++;  t1[i-1] -= 10;}
    
19.   }
    
20. 
    
21.   if (t1[t2.size()-1] > 9)
    
22.     if (t1.size() == t2.size() )  {t1.push_back(1);  t1[t1.size()-2] -= 10;}
    
23. 
    
24.     else {
    
25.       t1[t2.size()]++;
    
26.       for (int i = t2.size();i < t1.size()-1;i++){
    
27.         if (t1[i] > 9) {t1[i] -= 10;  t1[i+1]++;}
    
28.         else break;
    
29.       }
    
30.       t1[t2.size()-1] -= 10;
    
31.     }
    
32.   return BI(t1);
    
33. }
    
34. 
    
35. int main(){
    
36.   int cnt = 0;
    
37.   vector<int> a(1,1),b(2,1);
    
38.   BI n(a),d(b);
    
39. 
    
40.   for (int i = 0;i < 1000;i++){
    
41.     BI t = n;
    
42.     n = d;
    
43.     d = t + d + d;
    
44. 
    
45.     BI u = n + d;
    
46.     if (u.v.size() > d.v.size())  cnt++;
    
47.   }
    
48.   cout << cnt << endl;
    
49.   return 0;
    
50. }
    

复制代码

4444567

用时

1. from time import time
   
2. 
   
3. t = time()
   
4. a = 3  #a是分子
   
5. b = 2  #b是分母
   
6. l1 = []
   
7. count = 1000
   
8. while count:
   
9.     c = b #上一个数的分母
   
10.     b = a+b
    
11.     a = b+c
    
12.     if len(str(a))>len(str(b)):
    
13.         l1.append((a,b))
    
14.     count -= 1
    
15.    
    
16. print(l1,'\n')
    
17. 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库，本题就非常简单了。

1. /*
   
2. 答案：153
   
3. */
   
4. #include <iostream>
   
5. #include <string>
   
6. #include <mpirxx.h>
   
7. using namespace std;
   
8. 
   
9. int main(void)
   
10. {
    
11.   mpz_class p0 = 1, p1 = 3, p2;
    
12.   mpz_class q0 = 1, q1 = 2, q2;
    
13.   int nCount = 0;
    
14.   for (int i = 2; i <= 1000; ++i)
    
15.   {
    
16.     p2 = 2 * p1 + p0;
    
17.     q2 = 2 * q1 + q0;
    
18.     string sp = p2.get_str();
    
19.     string sq = q2.get_str();
    
20.     if (sp.length() > sq.length())
    
21.       ++nCount;
    
22.     p0 = p1;
    
23.     p1 = p2;
    
24.     q0 = q1;
    
25.     q1 = q2;
    
26.   }
    
27.   cout << nCount << endl;
    
28.   return 0;
    
29. }
    

复制代码

Asss-whom

1. use std::time::Instant;
   
2. 
   
3. fn main() {
   
4.     let now = Instant::now();
   
5.     // Copy from "[飘飞的白杨](https://fishc.com.cn/space-uid-359393.html)"
   
6.     let (mut num, mut n, mut m) = (0, 1, 2);
   
7.     for _ in 0..1001 {
   
8.         (n, m) = (m, m * 2 + n);
   
9.         if (n + m).to_string().len() > m.to_string().len() {
   
10.             num += 1;
    
11.         }
    
12.     }
    
13.     println!("{}", num);
    
14.     println!("[Finished in {}s]", now.elapsed().as_secs_f32())
    
15. }
    

复制代码

319
[Finished in 0.0004963s]