题目65：找出e的连分数中第100个收敛项的分子各位之和。

欧拉计划

Convergents of e

The square root of 2 can be written as an infinite continued fraction.



The infinite continued fraction can be written, = [1;(2)], (2) indicates that 2 repeats ad infinitum. In a similar way, = [4;(1,3,1,8)].

It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations. Let us consider the convergents for .



Hence the sequence of the first ten convergents for are:

1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...
What is most surprising is that the important mathematical constant,
e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].

The first ten terms in the sequence of convergents for e are:

2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...
The sum of digits in the numerator of the convergent is 1+4+5+7=17.

Find the sum of digits in the numerator of the convergent of the continued fraction for e.

题目：

2的平方根可以写作无限连分数：



这个无限连分数可以写作， = [1;(2)], (2) 表示2无限循环出现。类似的， = [4;(1,3,1,8)]。

事实证明平方根的连分数序列提供了最好的有理数近似值。让我们考虑 的收敛项：



因此 的收敛项中的前十项是：

1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...

更令人惊奇的是一个重要的数学常数：

e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].

e 的收敛项序列中的前十项是：

2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...

其中第十项的分子各位数之和是 1+4+5+7=17。

找出 e 的收敛项序列中第 100 项的分子上各位之和。

jerryxjr1220

272
[Finished in 0.1s]

本来写了递归的算法，结果run了半天出不来，果然递归的效率太低，用列表就快多了

k = []
for i in range(34):
        k.append (1)
        k.append (2*i+2)
        k.append (1)

En = [2,3]
for j in range(2,101):
        En.append (En[j-1] * k[j-1] + En[j-2])

E100 = str(En[99])
total = 0
for each in E100:
        total += int(each)
print (total)

99592938

def con_e(num):#将连分数e的前num项组成list
    e=[2]
    for i in range(1,num):
        if i%3==2:
            e.append(2*i//3+1)
        else:
            e.append(1)
    return e

def deno(num):#将c+1/(b/a)转为b/a的格式,迭代c，最后一项不倒置，所以a即num项的分子
    e=con_e(num)
    a=e.pop()
    b=1
    while len(e):
        c=e.pop()
        temp=a*c+b
        b=a
        a=temp
    return a

num=100
print(sum(int(i) for i in str(deno(num))))

272
>>>

najin

用matlab算这个题目就是艹蛋，放弃

fc1735

from fractions import Fraction

def fun(n):
  if n == 0:
    return 2
  elif n % 3 == 2:
    return (n + 1) * 2 // 3
  else:
    return 1

ans = Fraction(0)
for i in map(lambda x: fun(x), reversed(range(100))):
  ans += i
  ans = 1 / ans

print(sum(map(lambda x: int(x), str(ans.denominator))))

https://github.com/devinizz/project_euler/blob/master/page02/65.py

j.p.-hwang

n=99;
k=ones(1,n);
k(2:3:end)=2*(1:round(n/3));
k=flip(k);
fenzi=sym('1');
fenmu=sym(k(1));
for i=2:n
    temp=sym(fenmu);
    fenmu=sym(fenzi+k(i)*temp);
    fenzi=temp;
end
total=[fenzi+2*fenmu fenmu];
t1=char(total(1));
wei=length(t1);
s=0;
for j=1:wei
    s=s+str2num(t1(j));
end

永恒的蓝色梦想

j.p.-hwang 发表于 2020-6-28 15:18
n=99;
k=ones(1,n);
k(2:3:end)=2*(1:round(n/3));

这……是什么语言

debuggerzh

272

Process returned 0 (0x0)   execution time : 0.032 s
Press any key to continue.
使用栈储存数据，递推计算，大数

#include<iostream>
#include<vector>
#include<stack>
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);
}

BI operator * (const int c,const BI & x){
  BI res = x;

  for (int i = 0;i < res.v.size();i++)
    res.v[i] *= c;

  for (int i = 0;i < res.v.size()-1;i++)
    if (res.v[i] > 9) {
      res.v[i+1] += res.v[i] / 10;
      res.v[i] %= 10;
  }
  int sz = res.v.size();
  if (res.v[sz-1] > 9)  {res.v.push_back(res.v[sz-1] / 10); res.v[sz-1] %= 10;}

  return res;
}

void print_ans(const BI & x){
  int ans = 0;

  for (int i = 0;i < x.v.size();i++)
    ans += x.v[i];

  cout << ans <<endl;
}

int main()
{
  vector<int> a(1,1),b(1,1);
  BI n(a),d(b);
  stack<int> s;

  for (int i = 1;i < 99;i++){
    int k = i/3 + 1;

    if (i % 3 == 2) s.push(2*k);
    else  s.push(1);
  }
  while(s.size() ){//先算e-2，再补回去
    //cout << s.top() << endl;
    BI t = d;
    d = n + s.top() * d;
    n = t;

    s.pop();
  }
  n = n + 2*d;

  print_ans(n);
  return 0;
}

guosl

/*
答案：272
*/
#include <iostream>
#include <string>
#include <gmpxx.h>
using namespace std;

int main(void)
{
  mpz_class p1 = 2, p2 = 3, p3, q1 = 1, q2 = 1, q3;
  for (int i = 3; i <= 100; ++i)
  {
    if (i % 3 == 0)
    {
      p3 = p2 * 2 * (i / 3) + p1;
      q3 = q2 * 2 * (i / 3) + q1;
    }
    else
    {
      p3 = p2 + p1;
      q3 = q2 + q1;
    }
    p1 = p2;
    q1 = q2;
    p2 = p3;
    q2 = q3;
  }
  string str = p2.get_str(10);
  int nSum = 0;
  for(int i = 0; i < int(str.length()); ++i)
    nSum += int(str[i] - 48);
  cout << nSum << endl;
  return 0;
}

永恒的蓝色梦想

def generator():
    yield 2
    k = 2

    while True:
        yield 1
        yield k
        yield 1
        k += 2

it = [i for i, _ in zip(generator(), range(100))]
it.reverse()
it = iter(it)

nume = next(it)
deno = 1

for i in it:
    nume, deno = i * nume + deno, nume

print(sum(int(i) for i in str(nume)))

guosl

本题可以应用连分数的递推公式和大数库mpir（或gmp）来解。

/*
答案：272
*/
#include <iostream>
#include <string>
#include <mpirxx.h>
using namespace std;

int main(void)
{
  mpz_class p1=2, p2=3, p3;
  mpz_class q1=1, q2=1, q3;
  for (int i = 3; i <= 100; ++i)
  {
    int a = 1;
    if (i % 3 == 0)
      a = (i / 3) * 2;
    p3 = a*p2 + p1;
    q3 = a*q2 + q1;
    p1 = p2;
    p2 = p3;
    q1 = q2;
    q2 = q3;
  }
  string str = p3.get_str();
  int nSum = 0;
  for (int i = 0; i < (int)str.length(); ++i)
    nSum += int(str[i] - '0');
  cout << nSum << endl;
  return 0;
}

B1tetheDust

import time as t

start = t.perf_counter()
decimal_list = []
for n in range(2, 101):
    if not n % 3:
        decimal_list.append(n // 3 * 2)
    else:
        decimal_list.append(1)

numerator = 1
denominator = decimal_list[-1]
for n in range(98, 0, -1):
    numerator, denominator = denominator, numerator + denominator * decimal_list[n - 1]
numerator += denominator * 2
print(sum([int(i) for i in str(numerator)]))
print("It costs %f s" % (t.perf_counter() - start))

272
It costs 0.000073 s

TLM

永恒的蓝色梦想 发表于 2020-6-28 16:17
这……是什么语言

matlab，虽然已经三年了