-
Notifications
You must be signed in to change notification settings - Fork 0
/
026_reciprocal_cycles.py
49 lines (36 loc) · 994 Bytes
/
026_reciprocal_cycles.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
"""
Task:
http://www.mathblog.dk/project-euler-26-find-the-value-of-d-1000-for-which-1d-contains-the-longest-recurring-cycle/
"""
import time
def main():
cycle_len = 0
num = 0
for i in range(1000, 1, -1):
if cycle_len >= i:
break
remainders = [0 for _ in range(i)]
value = 1
pos = 0
while remainders[value] == 0 and value != 0:
remainders[value] = pos
value *= 10
value %= i
pos += 1
if pos - remainders[value] > cycle_len:
num = i
cycle_len = pos - remainders[value]
print("cycle len:", cycle_len)
print("num:", num)
def get_cycle_lenght(numerator, denominator):
x = numerator * 9
z = x
cycle_length = 1
while z % denominator:
z = z * 10 + x
cycle_length += 1
return cycle_length
if __name__ == '__main__':
start_time = time.time()
main()
print("time:", time.time() - start_time)