Added an O(1) solution to problem 002 (TheAlgorithms#776)

melonbreadjin · poyea · commit 7b89d03dd7d8 · 2019-05-02T00:44:21.000+08:00
* Added an O(1) solution to problem 002

* Removed comments from sol3.py that were accidentally added to sol4.py
diff --git a/project_euler/problem_02/sol4.py b/project_euler/problem_02/sol4.py
@@ -0,0 +1,13 @@
+import math
+from decimal import *
+
+getcontext().prec = 100
+phi = (Decimal(5) ** Decimal(0.5) + 1) / Decimal(2)
+
+n = Decimal(int(input()) - 1)
+
+index = (math.floor(math.log(n * (phi + 2), phi) - 1)  // 3) * 3 + 2
+num = round(phi ** Decimal(index + 1)) / (phi + 2)
+sum = num // 2
+
+print(int(sum))
