A Complicated Numbers Problem in New Logic/Math Puzzles Posted April 2, 2015 · Report reply Okay here's my attempt So calculating (3 + sqrt5)^n When I saw sqrt5 I immediately thought of its connection to the golden ratio & fibonacci numbers The golden ratio "phi" = (1 + sqrt5)/2, one of two numbers holding the property phi^2 - phi - 1 = 0 the other being (1 - sqrt5)/2 Anyway phi^n has curious properties that let the exponential be reduced to multiples of itself added together with coefficients being Fibonacci numbers. 3 + sqrt5 = 2 * phi + 2 or 2*(1 + phi) = 2*phi^2 because phi^2 = phi + 1 so (3 + sqrt5)^n = 2^n * phi^(2n) At this point I think you could use a lot of different properties of the golden ratio to get this number. Notably phi^k = F(k) * phi + F(k-1) where F(k) is the kth Fibonacci number so=> 2^n * (F(2n) * phi + F(2n-1)) This should way be easier to calculate assuming you don't make any coding mistakes aka have a fast fibonacci calculator (non recursive - the recursive algorithm is complexity O(2^n) but the iterative method is much faster like O(n) I think) and so the whole latter term can be calculated pretty quickly, and if not because n is soooo huge well I'm pretty sure there are algorithms for calculating just the final digits of large fibonacci numbers. Don't quote me on that but let's roll with it! So now we have this number N(n) = (F(2n) * phi + F(2n-1)) = ((1+sqrt5)/2)^(2n) and (3 + sqrt5)^n === 2^n * N(n) This doesn't seem too expensive now because 2^n in binary is just a one bit followed by n-1 zero bits.