77 lines
2.1 KiB
Python
77 lines
2.1 KiB
Python
#!/usr/bin/python
|
||
|
||
# All square roots are periodic when written as continued fractions and can be written in the form:
|
||
#
|
||
# √N=a0+1/(a1+1/(a2+1/(a3+…
|
||
#
|
||
# For example, let us consider √23:
|
||
#
|
||
# √23=4+√23−4=4+1/(1/(√23−4))=4+1/(1+(√23−3)/7)
|
||
#
|
||
# If we continue we would get the following expansion:
|
||
#
|
||
# √23=4+1/(1+1/(3+1/(1+1/(8+…
|
||
#
|
||
# The process can be summarised as follows:
|
||
# a0=4,1/(√23−4)=(√23+4)/7=1+(√23−3)/7
|
||
# a1=1,7/(√23−3)=7(√23+3)/14=3+(√23−3)/2
|
||
# a2=3,2/(√23−3)=2(√23+3)/14=1+(√23−4)/7
|
||
# a3=1,7/(√23−4)=7(√23+4)/7=8+√23−4
|
||
# a4=8,1/(√23−4)=(√23+4)/7=1+(√23−3)/7
|
||
# a5=1,7/(√23−3)=7(√23+3)/14=3+(√23−3)/2
|
||
# a6=3,2/(√23−3)=2(√23+3)/14=1+(√23−4)/7
|
||
# a7=1,7/(√23−4)=7(√23+4)/7=8+√23−4
|
||
#
|
||
# It can be seen that the sequence is repeating. For conciseness, we use the notation √23=[4;(1,3,1,8)], to indicate that the block (1,3,1,8)
|
||
# repeats indefinitely.
|
||
#
|
||
# The first ten continued fraction representations of (irrational) square roots are:
|
||
#
|
||
# √2=[1;(2)], period=1
|
||
# √3=[1;(1,2)], period=2
|
||
# √5=[2;(4)], period=1
|
||
# √6=[2;(2,4)], period=2
|
||
# √7=[2;(1,1,1,4)], period=4
|
||
# √8=[2;(1,4)], period=2
|
||
# √10=[3;(6)], period=1
|
||
# √11=[3;(3,6)], period=2
|
||
# √12=[3;(2,6)], period=2
|
||
# √13=[3;(1,1,1,1,6)], period=5
|
||
#
|
||
# Exactly four continued fractions, for N≤13, have an odd period.
|
||
#
|
||
# How many continued fractions for N≤10000 have an odd period?
|
||
|
||
from math import sqrt
|
||
|
||
from projecteuler import build_sqrt_cont_fraction, timing
|
||
|
||
|
||
def is_square(n):
|
||
p = sqrt(n)
|
||
m = int(p)
|
||
|
||
return bool(p == m)
|
||
|
||
|
||
@timing
|
||
def p064():
|
||
count = 0
|
||
|
||
for i in range(2, 10000):
|
||
# Perfect squares are obviously not represented as continued fractions.
|
||
# For all other numbers, calculate their period and check if it's odd.
|
||
if not is_square(i):
|
||
# period_cf(i) % 2 != 0:
|
||
_, period = build_sqrt_cont_fraction(i, 300)
|
||
|
||
if period % 2 != 0:
|
||
count = count + 1
|
||
|
||
print('Project Euler, Problem 64')
|
||
print(f'Answer: {count}')
|
||
|
||
|
||
if __name__ == '__main__':
|
||
p064()
|