Problem 684

1 files changed, 36 insertions, 0 deletions

diff --git a/problem684.ijs b/problem684.ijs
new file mode 100644
index 0000000..5ebca10
--- /dev/null
+++ b/problem684.ijs
@@ -0,0 +1,36 @@
+modn =: 1000000007
+
+bigmodpower =: {{
+	NB. perform the calculation b^e mod m
+	NB. Based on this https://en.wikipedia.org/wiki/Modular_exponentiation
+	'base exp mod' =. y
+
+	result =. 1
+	base =. mod|base
+	while. exp > 0 do.
+		if. 2|exp do.
+			result =. mod|result*base
+		end.
+		base =. mod|*:base
+		exp =. <.exp%2
+	end.
+	result
+}}
+
+S =: {{
+	t =. <.y%9
+	k =. 9|y
+	pow =. bigmodpower 10;t;modn
+	r =. (pow*6+k++/>:i.k)-k+6+9*t
+	modn|r
+}}
+
+fib =: {{
+	if. y < 2 do.
+		y
+	else.
+		(fib y-2)+(fib y-1)
+	end.
+}} M.
+
+problem684 =: modn|+/S@fib"0 x:2+i.89