summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorIru Cai <mytbk920423@gmail.com>2021-05-13 20:05:58 +0800
committerIru Cai <mytbk920423@gmail.com>2021-05-13 20:05:58 +0800
commit5024901379d4a6bc0d2ecc9338701395f85199ba (patch)
tree760641de175f008bc782d564738d69d99c40fcfa
parente4f94bdaa436533b9f379b2846a64856f5d818b4 (diff)
downloadproject_euler-master.tar.xz
684,686,700HEADmaster
-rw-r--r--euler_684.py36
-rw-r--r--euler_686.py24
-rw-r--r--euler_700.py79
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()