[C/C++] Project Euler #64 - Odd period square roots
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.
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;
}