project euler problem 65 https projecteuler netproblem65 the square root of 2 can be written as an infinite continued fraction sqrt2 1 1 2 1 2 1 2 1 2 the infinite continued fraction can be written sqrt2 1 2 2 indicates that 2 repeats ad infinitum in a similar way sqrt23 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 sqrt2 1 1 2 32 1 1 2 1 2 75 1 1 2 1 2 1 2 1712 1 1 2 1 2 1 2 1 2 4129 hence the sequence of the first ten convergents for sqrt2 are 1 32 75 1712 4129 9970 239169 577408 1393985 33632378 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 83 114 197 8732 10639 19371 1264465 1457536 the sum of digits in the numerator of the 10th convergent is 1 4 5 7 17 find the sum of the digits in the numerator of the 100th convergent of the continued fraction for e the solution mostly comes down to finding an equation that will generate the numerator of the continued fraction for the ith numerator the pattern is ni mi ni1 ni2 for mi the ith index of the continued fraction representation of e n0 1 and n1 2 as the first 2 numbers of the representation for example n9 6 193 106 1264 1 2 6 4 13 n10 1 193 1264 1457 1 4 5 7 17 returns the sum of every digit in num sumdigits1 1 sumdigits12345 15 sumdigits999001 28 returns the sum of the digits in the numerator of the maxth convergent of the continued fraction for e solution9 13 solution10 17 solution50 91 returns the sum of every digit in num sum_digits 1 1 sum_digits 12345 15 sum_digits 999001 28 returns the sum of the digits in the numerator of the max th convergent of the continued fraction for e solution 9 13 solution 10 17 solution 50 91
def sum_digits(num: int) -> int:
    
    digit_sum = 0
    while num > 0:
        digit_sum += num % 10
        num //= 10
    return digit_sum


def solution(max_n: int = 100) -> int:
    
    pre_numerator = 1
    cur_numerator = 2

    for i in range(2, max_n + 1):
        temp = pre_numerator
        e_cont = 2 * i // 3 if i % 3 == 0 else 1
        pre_numerator = cur_numerator
        cur_numerator = e_cont * pre_numerator + temp

    return sum_digits(cur_numerator)


if __name__ == "__main__":
    print(f"{solution() = }")