From 7509f7f46d0511454dccce2d52545c045cb67e57 Mon Sep 17 00:00:00 2001
From: Lily Lin
Date: Tue, 25 Oct 2022 00:09:05 -0700
Subject: Much simpler fractran program

Why did I commit the complex one in the first place...
---
 entries/lilylin/fractran/fractran.py | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
 create mode 100644 entries/lilylin/fractran/fractran.py

(limited to 'entries/lilylin/fractran/fractran.py')

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
-- 
cgit v1.2.3-70-g09d2