684,686,700HEADmaster

3 files changed, 139 insertions, 0 deletions

diff --git a/euler_684.py b/euler_684.py
new file mode 100644
index 0000000..f5bbec7
--- /dev/null
+++ b/euler_684.py
@@ -0,0 +1,36 @@
+#!/usr/bin/env python
+
+_mod = 1000000007
+
+def expmod(a,n,m):
+    if n == 0:
+        return 1
+
+    if n % 2 == 0:
+        t = expmod(a,n>>1,m)
+        return (t*t)%m
+    else:
+        return (a*expmod(a,n-1,m))%m
+
+def S(k):
+    n = k // 9
+    m = k % 9
+    pwr = expmod(10,n,_mod)
+    return 5*(pwr-1)-9*n+pwr*(m+2)*(m+1)//2-(m+1)
+
+def main():
+    fib = [0]*91
+    fib[0] = 0
+    fib[1] = 1
+    for i in range(2,91):
+        fib[i] = fib[i-2]+fib[i-1]
+
+    ans = 0
+    for i in range(2,91):
+        print(i)
+        ans = (ans + S(fib[i])) % _mod
+
+    print(ans)
+
+if __name__ == "__main__":
+    main()
diff --git a/euler_686.py b/euler_686.py
new file mode 100644
index 0000000..01af7b2
--- /dev/null
+++ b/euler_686.py
@@ -0,0 +1,24 @@
+#!/usr/bin/pypy
+
+import math
+
+# calculate the length-l prefix of 2^n
+def prefix_power2(n,l):
+    log = math.log10(2)*n
+    declog = log - math.floor(log)
+    return math.floor(pow(10,declog+l-1))
+
+def main():
+    i = 0
+    count = 0
+    while count < 678910:
+        i = i + 1
+        if prefix_power2(i, 3) == 123:
+            count = count + 1
+            if count % 1000 == 0:
+                print("p({},{})={}".format(123,count,i))
+
+    print("p({},{})={}".format(123,count,i))
+
+if __name__ == "__main__":
+    main()
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()