Read Time: 3 Minutes
After playing with tetration, I started to wonder how we can solve equations of the form:
To approach this problem we can look to the properties of infinite recursion. Generally, we can represent a function being applied with itself as so:
We can take both sides as input to . Notice how the left side stays the same, since one added to infinity is still infinity. Since both and can be represented using infinite recursion and must be equal.
This means we can solve any equation of the form by computing the value of for some large .
Note the choice of is important in some cases. Trivially, if then the identity always applies. Most of the time the choice of is arbitrary and infinite recursion eventually reaches a limit. In cases where a solution doesn't exist the function cannot ever approach a value for any choice of . Lastly, some functions have unstable solutions, where only a specific set of starting values result in the recursion reaching a limit. We can demonstate this with these two simple functions:
We can see that starting at any value for would always lead to approaching 0.5, but for has to be between -1 and 1 to approach one of the solutions 0.38196, to find the second solution must be equal to exactly for it to approach it. The second function is more unstable and the second solution is the most unstable.
We can apply this technique to more interesting functions like . Finding for some arbitrary starting point leads us to the solution .
Going back to the original question consider the function:
Doing some rearranging we can turn this into our original problem:
This means that the limit gives us the reciprocal of the solution to for the in the function. In practice we need to take the absolute value of to ensure that remains in the functions domain, this is when we only care about real solutions. This is a much better way to find the solution compared to Newton's method as only one logarithm function is needed. Furthermore, I've found that the values converge to the solution faster when starting at the same values.
Using this knowledge, we can write some code that solves equations like this for us:
def solve(b, time=500, accuracy=100): #Solves x^x=b from math import log import decimal decimal.getcontext().prec = accuracy x = decimal.Decimal(2) #this value is arbitrary for _ in range(time): x = decimal.Decimal(log(abs(x), 1/b)) return 1/x
As a result of this we can now not only solve some tetration equations faster but also we have a new tool to calculate numerical solutions to equations and a new way of thinking of functions. Nice!