Merge pull request #40 from rctcwyvrn/lily

Simplify fractran fib

1 files changed, 36 insertions, 0 deletions

diff --git a/entries/lilylin/fractran/fractran.py b/entries/lilylin/fractran/fractran.py
new file mode 100644
index 0000000..8363609
--- /dev/null
+++ b/entries/lilylin/fractran/fractran.py
@@ -0,0 +1,36 @@
+import math
+
+def fibonacci(n):
+	def is_power_of_two(counter):
+		bin = "{0:b}".format(counter)
+		return bin[0] == "1" and all([x == "0" for x in bin[1:]])
+
+	# http://lomont.org/posts/2017/fractran/
+	fractions = [
+                (17, 65),
+                (133, 34),
+                (17, 19),
+                (23, 17),
+                (2233, 69),
+                (23, 29),
+                (31, 23),
+                (74, 341),
+                (31, 37),
+                (41, 31),
+                (129, 287),
+                (41, 43),
+                (13, 41),
+                (1, 13),
+                (1, 3),
+            ]
+
+	counter = 78 * pow(5,n)
+
+	while True:
+		if is_power_of_two(counter):
+			return int(math.log2(counter))
+		for (numerator, denominator) in fractions:
+			if counter % denominator == 0:
+				counter //= denominator
+				counter *= numerator
+				break