From 5024901379d4a6bc0d2ecc9338701395f85199ba Mon Sep 17 00:00:00 2001
From: Iru Cai <mytbk920423@gmail.com>
Date: Thu, 13 May 2021 20:05:58 +0800
Subject: 684,686,700

---
 euler_700.py | 79 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 79 insertions(+)
 create mode 100644 euler_700.py

(limited to 'euler_700.py')

diff --git a/euler_700.py b/euler_700.py
new file mode 100644
index 0000000..876b35d
--- /dev/null
+++ b/euler_700.py
@@ -0,0 +1,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()
-- 
cgit v1.2.3