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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
#!/usr/bin/env python
# we use two method to get the Eulercoins
# 1. iterate over the sequence
# 2. find the *n* such that for a given number *a*, mul*n=a (mod g)
mul = 1504170715041707
mod = 4503599627370517
# gcdrev(a,b)=(g,a',b')
# - g is gcd(a,b)
# - a'a+b'b=g
# gcdrev_ calculates one (a',b') answer, while gcdrev() makes a'>=0
def gcdrev_(a,b):
if a == 0 and b == 0:
raise ValueError
if a == 0:
return b,0,1
if b == 0:
return a,1,0
q = a // b
g,aa,bb = gcdrev_(b,a%b)
return g,bb,(aa-q*bb)
def gcdrev(a,b):
if b <= 0:
raise ValueError
g,x0,y0 = gcdrev_(a,b)
if x0 < 0:
t = (-x0 + b - 1) // b
x = x0 + t * b
y = y0 - t * a
return g,x,y
else:
t = x0 // b
x = x0 - t * b
y = y0 + t * a
return g,x,y
def main():
sum_of_coins = 0
g,r,_ = gcdrev(mul,mod) # actually g is 1
# we use the second method, until the smallest n is smaller than the coin
print("======== First run ========")
coin = g
n_min = mod
while coin < n_min:
n = coin * r % mod
if n < n_min:
n_min = n
sum_of_coins = sum_of_coins + coin
print("n = {}, coin = {}".format(n, coin))
coin = coin + g
# then use the first method, until n >= n_min
print("======== Second run ========")
mincoin = mod
n = 1
coin = mul % mod
while n < n_min:
if coin < mincoin:
sum_of_coins = sum_of_coins + coin
mincoin = coin
print("n = {}, coin = {}".format(n,coin))
n = n + 1
coin = (coin + mul) % mod
print(sum_of_coins)
if __name__ == "__main__":
main()
|
