Problem 57

题目发布于 2003-11-21 翻译更新于 2025-03-16

Problem 57

Square Root Convergents

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

$\sqrt{2} = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \dots}}}$

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

$1 + \frac{1}{2} = \frac{3}{2} = 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$

The next three expansions are $\frac{99}{70}$ , $\frac{239}{169}$ , and $\frac{577}{408}$ , but the eighth expansion, $\frac{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$ 的平方根可以表示为如下无限连分数：

$\sqrt{2} = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \dots}}}$

将这个连分数进行四次迭代展开，分别可以得到：

接下来的三次迭代展开得到的分别是 $\frac{99}{70}$ 、 $\frac{239}{169}$ 和 $\frac{577}{408}$ ，直到第八次迭代展开 $\frac{1393}{985}$ ，分子的位数第一次超过分母的位数。

在前一千次迭代展开中，有多少个分数满足分子的位数多于分母的位数？

4 comments

Anonymous

Markdown is supported

p-gpcommentedabout 3 years ago

/*e57.c--Square root convergents*/
#include <stdio.h>

int n1[400], n2[400], n3[400], n4[400], n5[400], n6[400];

void prt(int *x);
void rd(int x, int *y);
void pls(int *x, int *y);
void sub(int *x, int *y);
int cmp(int *x, int *y);
void gcd(int *x, int *y);
void cpy(int *x, int *y);
void rep(int *x, int *y);
void sqr(void);
int div(int *x, int *y);
_Bool test(void);

int main()
{
    int cnt = 0;
    rd(1, n1);
    rd(2, n2);
    for (int i = 1; i < 1000; ++i) {
        sqr();
        if (test()) {
            ++cnt;
            //printf("%d ", i + 1);
        }
    }
    printf("\n%d\n", cnt);

    return 0;
}


_Bool test(void)
{
    gcd(n3, n4); //gcd@n4
    int x , y;
    x = div(n5, n4);
    y = div(n6, n4);
    if (x > y)
        return 1;
    return 0;
}

int div(int *x, int *y)
{
    for (int i = n3[0]; i >= 0; --i)
        n3[i] = 0;
    for (int i = 1; i <= y[0]; ++i)
        n3[i] = x[x[0] - y[0] + i];
    n3[0] = y[0];
    if (cmp(n3,y) >= 0)
        return x[0] - y[0] + 1;
    else
        return x[0] - y[0];
}

void sqr(void)
{
    int max = n2[0] + 4;
    int temp[max];
    temp[0] = max;
    cpy(temp, n2);
    int carry = 0;
    for (int i = 1; i <= n2[0]; ++i) {
        int z = n2[i] * 2 + carry;
        n2[i] = z % 10;
        carry = z / 10;
    }
    if (carry) {
        n2[n2[0] + 1] = carry;
        ++n2[0];
    }
    pls(n2, n1);
    cpy(n1, temp);
    cpy(n3, n1);
    cpy(n4, n2);
    pls(n3, n4);
    cpy(n5, n3);
    cpy(n6, n4);  
}

void rd(int x, int *y)
{
    for (int i = y[0]; i >= 0; -- i)
        y[0] = 0;        
    do {
        y[++y[0]] = x % 10;
    } while (x /= 10);
}

void prt(int *x)
{
    printf("%d: ", x[0]);
    for (int i = x[0]; i > 0; --i)
        printf("%d", x[i]);
    printf("\n", x[0]);
}

void pls(int *x, int *y)
{
    int carry = 0;
    int max = x[0] > y[0] ? x[0] : y[0];

    for (int i = 1; i <= max + 1; ++i) {
        int z = x[i] + y[i] + carry;
        x[i] = z % 10;
        carry = z / 10;
    }
    if (x[max + 1])
        x[0] = max + 1;
    else
        x[0] = max;
}

void sub(int *x, int *y)
{
    int n = y[0];
    for (int i = 1; i <= n ; ++i) {
        int z = x[i] - y[i];
        if (z >= 0)
            x[i] = z;
        else {
            x[i] = z + 10;
            --x[i + 1];
        }
    }
    for (int i = n + 1; i <= x[0]; ++i) {
        if (x[i] < 0) {
            x[i] += 10;
            --x[i + 1];
        }
    }
    for (int i = x[0]; i > 0; -- i)
        if (x[i] > 0) {
            x[0] = i;
            break;
        }
}

int cmp(int *x, int *y)
{
    if (x[0] > y[0])
        return 1;
    else if (x[0] < y[0])
        return -1;
    else {
        for (int i = x[0]; i > 0; --i) {
            if (x[i] > y[i])
                return 1;
            else if (x[i] < y[i])
                return -1;
        }
        return 0;
    }
}

void gcd(int *x, int *y)
{
    if (cmp(x, y) == 0)
        return ;
    else if (cmp(x, y) < 0)
        rep(x, y);
    sub(x, y);
    if (cmp(x, y) == 0)
        return ;
    else
        gcd(x, y);        
}

void cpy(int *x, int *y)
{
    for (int i = x[0]; i >= 0; --i)
        x[i] = 0;
    
    for (int i = 0; i <= y[0]; ++i)
        x[i] = y[i];
}

void rep(int *x, int *y)
{
    int max = x[0] > y[0] ? x[0] : y[0];

    int temp[max + 1];
    for (int i = 0; i <= max; ++i)
        temp[i] = 0;
    for (int i = 0; i <= x[0]; ++i)
        temp[i] = x[i];
    for (int i = 0; i <= x[0]; ++i)
        x[i] = 0;
    for (int i = 0; i <= y[0]; ++i)
        x[i] = y[i];
    for (int i = 0; i <= temp[0]; ++i)
        y[i] = temp[i];
}

..............................................................................................

153

SunMoonTraincommentedalmost 3 years ago

Length@Select[Rest@Convergents[Sqrt[2], 1001], 
  IntegerLength@Numerator@# > IntegerLength@Denominator@# &]

HZyundanfengqingcommentedalmost 3 years ago

以1，1为初值，把1000对分母、分子从小到大排成一列，一对一对比较。

from math import log10

def PEuler57(N=1000):
    count, frac = 0, [1, 1]
    for i in range(N):
        frac.append(frac[-1] + frac[-2])
        frac.append(frac[-1] + frac[-3])
        if int(log10(frac[-1])) > int(log10(frac[-2])):
            count += 1
    return count

yuandi42commented10 months ago

diglen(n)={length(Str(n))};
{my(S=2, c=0, sqrt2=S-1); for(i=1, 1000, S=2+1/S; sqrt2=S-1; if(diglen(numerator(sqrt2))>diglen(denominator(sqrt2)), c++)); c}

\\yet another solution, slightly faster:
{my(N=1, D=1, temp_D=1, c=0); for(i=1, 1000, temp_D=D; D+=N; N+=2*temp_D; if(diglen(N)>diglen(D), c++)); c}