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{aligned} 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{aligned}$

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{aligned} 1/{a_{1}} &< 1/{a_{3}}\\ k^{1/{a_{1}}} &< k^{1/{a_{3}}}\\ a_{2} &< a_{4}. \end{aligned}$

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{aligned} y_i &= k^{\frac{1}{x_i}} \\ y' &= k^{\frac{1}{x'}} \\ {(y')}^{x'} &= k. \end{aligned}$ Similarly, $\begin{aligned} x_{i+1} &= k^{\frac{1}{y_i}} \\ x' &= k^{\frac{1}{y'}} \\ {(x')}^{y'} &= k. \end{aligned}$

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