70 lines
1.9 KiB
Python
70 lines
1.9 KiB
Python
import math
|
|
|
|
|
|
def get_floor_sqrt(n):
|
|
return math.floor(math.sqrt(n))
|
|
|
|
|
|
def next_expansion(current_a, current_nominator,
|
|
current_denominator, original_number):
|
|
# Less typing
|
|
cn = current_nominator
|
|
cd = current_denominator
|
|
|
|
# Step 1: Multiply the fraction so that we can use the third binomial
|
|
# formula. Make sure we can reduce the nominator.
|
|
assert((original_number - cd * cd) % cn == 0)
|
|
# The new nominator is the denominator since we multiply with (x + cd) and
|
|
# then reduce the previous nominator. The new denominator is calculated by
|
|
# applying the third binomial formula and then by divided by the previous
|
|
# nominator.
|
|
cn, cd = cd, (original_number - cd * cd) // cn
|
|
|
|
# Step 2: Calculate the next a by finding the next floor square root.
|
|
next_a = math.floor((math.sqrt(original_number) + cn) // cd)
|
|
|
|
# Step 3: Remove next a from the fraction by substracting it.
|
|
cn = cn - next_a * cd
|
|
cn *= -1
|
|
|
|
return next_a, cn, cd
|
|
|
|
|
|
def get_continued_fraction_sequence(n):
|
|
|
|
# If number is a square number we return it.
|
|
floor_sqrt = get_floor_sqrt(n)
|
|
if n == floor_sqrt * floor_sqrt:
|
|
return ((floor_sqrt), [])
|
|
|
|
# Otherwise, we calculate the next expansion till we
|
|
# encounter a step a second time.
|
|
a = floor_sqrt
|
|
cn = a
|
|
cd = 1
|
|
sequence = []
|
|
previous_steps = []
|
|
|
|
while not (a, cn, cd) in previous_steps:
|
|
# print("a: {} cn: {} cd: {}".format(a, cn, cd))
|
|
previous_steps.append((a, cn, cd))
|
|
a, cn, cd = next_expansion(a, cd, cn, n)
|
|
sequence.append(a)
|
|
sequence.pop()
|
|
return ((floor_sqrt), sequence)
|
|
|
|
|
|
def get_period(n):
|
|
_, sequence = get_continued_fraction_sequence(n)
|
|
return len(sequence)
|
|
|
|
|
|
def euler_064():
|
|
s = len([n for n in range(1, 10001) if get_period(n) % 2 != 0])
|
|
return s
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print("e064.py: " + str(euler_064()))
|
|
assert(euler_064() == 1322)
|