Programming/Project Euler

[C/C++] Project Euler #64 - Odd period square roots

NoxLuna 2025. 6. 26. 00:43

Project Euler Problem #64 is about expressing square roots as continued fractions. The difficulty of this problem is around 20%. I think the challenge lies more in the mathematical concept rather than algorithmic complexity.

A similar problem of expressing square roots as continued fractions appeared previously in Problem #57: https://odev.tistory.com/entry/CPython-Project-Euler-57-Square-Root-Convergents

 

Here is the link to Problem #64:
https://projecteuler.net/problem=64



Key Mathematical Point

When expressing a square root as a continued fraction, it is important that the numerator is always 1.

For example, the square root of 7, \(\sqrt{7}\), can be expressed as:

\[\sqrt{7} = 2 + \sqrt{7} - 2\]

This is quite obvious mathematically, but we use this form to construct a continued fraction.

We first split the irrational number into its integer part and fractional part as shown above. For \(\sqrt{7}\), the integer part is 2, and the fractional part is \(\sqrt{7} - 2\). Next, we take the reciprocal of the fractional part to ensure the numerator is 1:

\[\sqrt{7} = 2 + \frac{1}{ \frac{1}{\sqrt{7} - 2} }\]

After this, we rationalize the denominator:

\[\sqrt{7} = 2 + \frac{1}{ 1 + \frac{ \sqrt{7} - 1 }{3} }\]

By repeating this process, we can express the square root as a continued fraction with periodic terms.



The Goal of the Problem

The continued fraction representation eventually exhibits a repeating period. The objective of this problem is to count how many square roots, within a given range, have an odd-length period in their continued fraction representation.



My Approach

I implemented the process of building the continued fraction step by step. Once I detected a repeating integer sequence, I recorded the period length and simply counted the cases with odd periods.

There may be better or more optimized solutions, but for me, it took around 10ms to compute, so I didn’t bother optimizing further for performance.


solving fractions

My Code(C/C++)

Below, I included my code for reference purposes only.

//------------------------------------------------
//    Project Euler #64 - Odd period square roots
//        - by Aubrey Choi
//        - created at 2015-04-02
//------------------------------------------------
#include <stdio.h>
#include <math.h>

int GetPeriod(int n);
int main()
{
    int count = 0;
    for( int i = 2 ; i <= 10000 ; i++ )
    {
        int p = GetPeriod(i);
        if( p%2 ) count++;
    }
    printf("ans = %d\n", count);
}

int GetPeriod(int n)
{
    double r = sqrt(n);
    int s = r;
    if( s*s == n ) return 0;
    int q = 1;
    int count = 0;
    do
    {
        q = (n-s*s)/q;
        int t = (r+s)/q;
        s = t*q - s;
        count++;
    } while( q != 1 );
    return count;
}
반응형