The goal is to demonstrate by
computing upper bounds for the sigma(n) and tau(n) functions
relative to n, there are no further possible solutions.
Our goal is to find more cases where
x = tau( sigma(x) ) * sigma ( tau(x))
Let's consider the tau function
Because tau(n) is based on the
number of prime divisors, it's clear to see that the ratio of
tau(n) / n converges to zero as n gets large. One important
insight is the relationship between sigma(n) / n, the greater
tau(n) for a given n s, the greater tau(n)/n and sigma(n)/n
In fact, the greatest n such that
tau(n)^2 > n is only n = 1260 (which has 36 divisors).
(Note: 9 is the only case such
that tau(x)^2 = x)
Checking further out, the min(n)
such that tau(n) = 1000 is 810,810,000. The tau ^2 is < 1/810
Sigma(n) is at a minimum n + 1 for
a prime and generally less than 2n. Exceptions exist for
extremely smooth numbers.. Let's say that the maximum: sigma(n)
through n is: k^2 * n where k is some upper bound. For
reference, let's refer to the concept and listing of
superabundant numbers: http://oeis.org/A004394 which
helps gives us an idea of how quickly sigma(n)/n grows so that
we can create an upper bound for k^2.
Let's manipulate the original formula
tau( sigma(x) ) * sigma ( tau(x)) <=
tau (k^2 * x) * sigma (tau x) <=
k * tau(x) * k^2 * tau(x) = k^3 *
So in order to have a solution to x = tau( sigma(x) ) * sigma (
We need for cases to exist such that k^3 * tau(x)^2 >= x
In order for there to be another
solution, we need to first compare how k^3 grows with respect to
how tau(x)^2 decreases (as a proportion of sqrt(x)).
The author of the puzzle had
searched through 100M. Let's check the OEIS list and find the
first number greater than 100M. This serves as the ideal
candidate in terms of tau(x) with respect to sqrt(x).
Let n = 122522400
tau n = 864.
n / tau(n)^2 = 164.1300154320988
k^2 = sigma(n) / n =
k^3 = 11.224133180426811
k^3 * tau^2 = x *
11.224133180426811 / 164.1300154320988 ~ .07x
So, even the upper bound for this
optimal computation around n is less than 7% of what is needed
for a match.
What if we derived k from tau n =
164^(2/3) = k^2 ~ 30
Let's go back to the list and find
a superabundant number such that sigma(x)/x = 30 or somewhere
On reviewing this list, you will
see the ratio with each number in the list grows extremely
Here is the massive but minimal n
such that sigma(n)/n >= 10. It's "abundantly" clear, that this
ratio sigma(n)/n grows extremely slowly with respect to n.
n = 25635551923920545633428119107919642299618796225234764843733449059620074026936003401444
tau(n) = 210667131569323376640
If we compute div n (tau^2(n)), we
Clearly, we are in a much worse
situation now. There is no point in raising this to the 2/3
power to compute k^2.
I can say with certainty that
there are no other solutions.
To illustrate this concept of upper bounds, let's check two
examples of numbers less than 100M.
In the range of the last solution,
we pick n = 5040
k^2 = sigma n / n = 3.836
tau n = 19344
n / tau(n)^2 = 1.4
1.4 ^ (2/3) = 1.25 < 3.836 so it
was worth checking around this n. There is a possibility.
I also computed this for a smaller
number on the superabundant list 1441440.
sigma n / n = 4.5818
div n / (tau(n)^2) = 17.3784
(17.3784)^(2/3) = 6.6115 > 4.5818
(much closer with this smaller figure but still impossible)