project euler problem 64 https projecteuler netproblem64 all square roots are periodic when written as continued fractions for example let us consider sqrt23 it can be seen that the sequence is repeating for conciseness we use the notation sqrt234 1 3 1 8 to indicate that the block 1 3 1 8 repeats indefinitely exactly four continued fractions for n13 have an odd period how many continued fractions for n10000 have an odd period references https en wikipedia orgwikicontinuedfraction returns the continued fraction period of a number n continuousfractionperiod2 1 continuousfractionperiod5 1 continuousfractionperiod7 4 continuousfractionperiod11 2 continuousfractionperiod13 5 returns the count of numbers 10000 with odd periods this function calls continuousfractionperiod for numbers which are not perfect squares this is checked in if sr floorsr 0 statement if an odd period is returned by continuousfractionperiod countoddperiods is increased by 1 solution2 1 solution5 2 solution7 2 solution11 3 solution13 4 returns the continued fraction period of a number n continuous_fraction_period 2 1 continuous_fraction_period 5 1 continuous_fraction_period 7 4 continuous_fraction_period 11 2 continuous_fraction_period 13 5 returns the count of numbers 10000 with odd periods this function calls continuous_fraction_period for numbers which are not perfect squares this is checked in if sr floor sr 0 statement if an odd period is returned by continuous_fraction_period count_odd_periods is increased by 1 solution 2 1 solution 5 2 solution 7 2 solution 11 3 solution 13 4
from math import floor, sqrt


def continuous_fraction_period(n: int) -> int:
    
    numerator = 0.0
    denominator = 1.0
    root = int(sqrt(n))
    integer_part = root
    period = 0
    while integer_part != 2 * root:
        numerator = denominator * integer_part - numerator
        denominator = (n - numerator**2) / denominator
        integer_part = int((root + numerator) / denominator)
        period += 1
    return period


def solution(n: int = 10000) -> int:
    
    count_odd_periods = 0
    for i in range(2, n + 1):
        sr = sqrt(i)
        if sr - floor(sr) != 0 and continuous_fraction_period(i) % 2 == 1:
            count_odd_periods += 1
    return count_odd_periods


if __name__ == "__main__":
    print(f"{solution(int(input().strip()))}")