Soumava's Algorithm

This algorithm was conceived by Soumava Pal. This is his original note.

Abstract:
Soumava develops a numerical method to compute pairs of \((x, y)\) such that \(x^y = y^x = k,\) where \(k > 1.\)

Given the parameters \(x_0\), a seed, and \(h\), the tolerance limit, Soumava's algorithm is as follows:

1. [Initialize] \(x \leftarrow x_0\)
2. [Compute] \(y \leftarrow k^{\frac{1}{x}}\)
3. [Iterate] While \( (x^y \sim k) > h \): \[(x,y) \leftarrow \left(k^{k^{\frac{-1}{x}}}, k^{k^{\frac{-1}{y}}}\right) \]
4. [Output] Return \((x,y)\)

The proof is cluttered, we could clean it up.

Let \(<a>\) be a sequence defined as follows: \[a_0 = x_0, \quad a_{i+1} = k^{\frac{1}{a_i}}. \] Furthermore, let \(<x>\) be the subsequence formed by the even terms of \(<a>\): \[x_i = a_{2i}.\] Similarly, let \(<y>\) be the subsequence formed by the odd terms of \(<a>\): \[y_i = a_{2i+1}.\] We claim that \[\lim_{i\to \infty} x_i^{y_i} = y_i^{x_i} = k.\ _\square\]

We split the proof into two parts. First we prove that the sequences converge, and then we show that the limits satisfy the equation.

Convergence

\(P\) = \(a_{1}\) = \(k^{1/m}\), \(b_{j+1}\) = \(k^{1/b_{j-1}}\) for all \(j \in N,\) where \(N\) is the set of all positive integers, and \(m\) is any positive real number (domain of \(m\) is \((0, \infty)\)).

Let us take the two sub-sequences \(\{ a_{1}, a_{3}, a_{5}, \ldots \}\) and \(\{a_{2}, a_{4}, a_{6}, \ldots\}\) that are the sub-sequences formed by the odd numbered terms and by the even numbered terms, respectively.

Let the sequence formed by the odd numbered terms be \(M\) and the sequence formed by the even numbered terms be \(T.\)

Now we express \(a_{n+2}\) in terms of \(a_{n}\). By definition,

\[a_{n+2} = k^{1/a_{n+1}} =k^{1/{k^{1/a_{n}}}}. \qquad (1)\]

Our first observation is that the two sub-sequences that I have considered are both bounded below by \(0\) and above by \(k\) itself.

The lower bound is easy to observe because we know that the exponential function \(a^x\) is positive for all real \(x\) and positive \(a\). And our sequence is of the exponential form only. So \(0\) is indeed a lower bound.

Now we can establish the validity of \(k\) as an upper bound by the method of contradiction.

Let us assume that the sequence \(P\) contains a number which is greater than \(k\) itself, i.e. \(a_{h} = v>k\) for some \(h\) in \(N\).

But \(a_{h}= k^{1/{a_{h-1}}}= v\) necessarily implies that \(a_{h-1}\) is less than \(1\) and greater than \(0,\) i.e. \(1/{a_{h-1}}\) is greater than \(1\), and \(k^{1/{a_{h-1}}}\) is greater than \(k\). All this holds if \(a_{h-1}\) is less than \(1\). But again \(a_{h-1}\) = \(k^{1/{a_{h-2}}}\).

Now if we take logarithm to the base \(k\) on both sides, then on LHS we get something negative as \(a_{h-1}\) belongs to \((0,1)\) by assumption and \(k\) is greater than \(1\) (domain of \(k\) is \((1,\infty)\)). But on RHS we have \(1/{a_{h-2}}\) which is positive because \(a_{h-2}\) is positive as the lower bound of the sequence \(\{a_{1}, a_{2}, a_{3}, \ldots\}\) is 0. Thus a negative number on the LHS is equal to a positive number on the RHS by assumption that \(a_{h}>k\) for some positive integer \(h\).

So we have a direct contradiction if \(a_{h}>k\) for some positive integer \(h\), and therefore this assumption must be false. So the negation of this statement must be true. That is ‘\(a_{h}<k\) for all positive integers \(h'\). So we have established that \(k\) itself is an upper bound.

Our second aim is to prove that these two sub-sequences are monotonic.

Let us consider the sub-sequence \(M=\{a_{1}, a_{3}, a_{5}, \ldots \}\) and we take \(M_{1} = a_{1}, M_{2} = a_{3}, M_{3} = a_{5}\), and in general \(M_{k} = a_{2k-1}\) for all \(k\in N\).

We know by order property (law of trichotomy) that given two reals \(a\) and \(b\), either \(a=b\), or \(a>b\), or \(a<b\). Here we observe that \(M_{n}\) is not equal to \(M_{n+1}\) for any positive integer \(n\), because of the relation between two consecutive terms of the sequence \(\{a_{1}, a_{3}, a_{5}, \ldots\}\) derived in \((1)\) above.

So \(M_{1}>M_{2}\) or \(M_{2}>M_{1}\).

Case I:
\(M_{1}>M_{2}\), i.e. \(a_{1}>a_{3}\)

Next we proceed by the principle of mathematical induction to show that \(M_{n}>M_{n+1}\) for all positive integers \(n\). In fact we have already checked the first step for \(n=1\).

Next we assume the validity of the statement to hold true for some \(n=k\), i.e. \(M_{k}>M_{k+1}\) or \(a_{m}>a_{m+2}\) (where obviously \(m={2k-1}\)).

Now,

\[\begin{align} M_{k}&>M_{k+1}\\ a_{m}&>a_{m+2}\\ 1/{a_{m}} &< 1/{a_{m+2}} \qquad (\text{reciprocating the positive numbers reverses the sign of inequality})\\ k^{1/{a_{m}}} &< k^{1/{a_{m+2}}}\\ 1/{k^{1/{a_{m}}}} &> 1/{k^{1/{a_{m+2}}}} \qquad (\text{reciprocating the positive numbers reverses the sign of inequality})\\ k^{1/{k^{1/{a_{m}}}}} &> k^{1/{k^{1/{a_{m}}}}}\\ a_{m+2} &> a_{m+4}, \qquad (\text{by the relation derived in (1)}) \end{align}\]

i.e.

\[M_{k+1} > M_{k+2}.\]

So we have \(M_{1}\) > \(M_{2}\) and \(M_{k}\) > \(M_{k+1}\), which implies \(M_{k+1}\) > \(M_{k+2}\) for all positive integers \(k\).

So \(M\) is a strictly decreasing monotone sequence.

Having established that, we also see that \(M_{1}\) > \(M_{2}\) i.e. \(a_{1}\) > \(a_{3}\) implies that

\[\begin{align} 1/{a_{1}} &< 1/{a_{3}}\\ k^{1/{a_{1}}} &< k^{1/{a_{3}}}\\ a_{2} &< a_{4}. \end{align}\]

Therefore \(a_{1}\)>\(a_{3}\) implies that \(a_{2}\) < \(a_{4}\). If we consider the sub-sequence \(T\) consisting of \(\{a_{2}, a_{4}, a_{6}, \ldots \},\) then we have \(a_{2} < a_{4}\), i.e. \(T_{1} < T_{2}\). By a similar inductive argument as above, we can see that

\(T\) is a strictly increasing monotone sequence.

It is to be noted that the conclusions drawn above are under the heading of Case I.

Case II:
\(M_{1} < M_{2}\)

Under this consideration, we proceed exactly as in Case I and prove that \(M\) is a strictly increasing monotone sequence.

And on the same lines as in Case I, we have that \(T\) is a strictly decreasing monotone sequence.

1. In both the cases which are mutually exhaustive, we see that \(M\) and \(T\) are monotone sequences of the opposite nature, i.e. if one is increasing the other is decreasing.
2. Also \(M\) and \(T\) are sub-sequences of a sequence \(P\) which is bounded as a whole with \(0\) as a lower bound and \(k\) as an upper bound.
3. So \(M\) and \(T\) themselves are also bounded with \(0\) as a lower bound for both and \(k\) as an upper bound for both.

So from 1, 2 and 3 we see that M and T are both monotonic and bounded.

By the Bolzano-Weierstrauss theorem, any monotonic bounded sequence has a finite limit.

Since the sequences \(M\) and \(T\) meet the requirements of the theorem, they are convergent and have a finite limit. Let the limit of \(M_{n}\) as \(n\) tends to \(∞\) be \(z\) and the limit of \(T_{n}\) as \(n\) tends to \(∞\) be \(g\).

\(_\square\)

Now, we set out to prove that the limits indeed satisfy the equation:

Satisfaction

Because the sequence converges, as \(i \to \infty\), \[(x_i,y_i) \to (x_{i+1}, y_{i+1}) \to \lim_{ r \to \infty}(x_r,y_r) = (x', y'). \qquad \text{(say)} \] By construction, \[\begin{align} y_i &= k^{\frac{1}{x_i}} \\ y' &= k^{\frac{1}{x'}} \\ {(y')}^{x'} &= k. \end{align} \] Similarly, \[\begin{align} x_{i+1} &= k^{\frac{1}{y_i}} \\ x' &= k^{\frac{1}{y'}} \\ {(x')}^{y'} &= k. \end{align} \]

Therefore, \[(x')^{y'} = (y')^{x'} = k. \ _\square \]

Python

1
2
3
4
5
6

def soumava(x0,h,k):
    x = x0
    y = k**(1.0/x)
    while abs(x**y - k) > h:
            x, y = k**k**(-1.0/x), k**k**(-1.0/y)
    return x, y

This section requires expansion