A Data Science Central Community
* Disclaimer: This is a very challenging problem, for serious research mathematicians only, and it is almost certain that no one will ever find a solution, so I don't think my house is really at stake. Yet a very fascinating problem, great to hone your data science skills. Other examples of $1 million awards for very tough math problems can be found here.
This week we investigate a very interesting question about continued fractions. We start with the recursion
f(n) = 1 / (1 + n*f(n+1)) for n > 1
with the initial condition f(1) = a.
Regardless of a and n, this leads to
f(2) = 1/(1+2/(1+3/(1+4/... 1/(1+n*f(n+1))...)))
for any n > 1.
Note that f(n+1) can be iteratively computed using the recursion
f(n+1) = (1/f(n) - 1)/n
for n > 0, with f(1) = a.
The Paradox
In the second formula, the one that expands f(2), let n tends to infinity. Will the right hand side of the formula converge? It looks like it won't, if you use the recursion (third formula) to compute f(n+1). It won't unless f(2) = 0.525135276...
It seems to mean that unless f(2) = 0.525135276... then f(n) tends to -1/n as n tends to infinity, and there's no convergence for the continued fraction. Also note that f(n) depends on f(1) = a, while the limit, for the continued fraction, does not. That's part of the paradox. The formula for f(2) is correct for any value of n and a, except n = infinity.
Yet, if you assign a specific value to f(n), for any large value of n, and iteratively compute f(2) backwards using the first formula, you end up with f(2) being very, very close to 0.525135276...
We did a test, computing f(n) forward starting with f(2) = -0.5, and ended up with f(353)=-0.0547... Doing it the other way around, starting with f(353) = 6 doing backward computations, we ended up with f(2) = 0.525132576... Isn't it fascinating?
It turns out that the only value that guarantees convergence is
f(2) = sqrt(pi*e/2)*erfc(1/sqrt(2))-1 = 0.525135276...
This spreadsheet might help you understand the challenge.
The Challenge
How do you explain this paradox?
Is the limiting value 0.525135276... a number that can be expressed using a finite number of elementary transcendental functions (trigonometric, log, exp, power, polynomials, hyperbolic and their inverses), rational numbers, and/or irrational numbers such as algebraic numbers and Pi, e, or the Euler constant? Most continued fractions such as the one in this challenge have a positive answer to this question: check out the Wolfram encyclopedia or Wikipedia for details.
Hint: One way to attack this problem is use the computational approach - this is the big data approach. Try billions of combinations of numbers generated by formulas involving e, Pi, ln(n), x^a, addition, division etc. For instance, {(e*Pi)^{1/2}}/(ln 2). Compute very accurately the value for each of these billion numbers. Identify those that match 0.525135276... up to (say) 20 decimals. What are the chances, that just by chance, one of these numbers has 40 correct decimals, especially if the second closest number in your list only has 7 correct decimals? Note that if your list of guesses contains 100 billion generated numbers in [0, 1], you should expect your closest approximation to have 11 correct decimals (assuming you did not find an exact match). If indeed you found a number correct up to 40 decimals (assuming you only check the first 40 decimals), chances are that you found the solution.
The Award
If you are the first to successfully answer positively the second question in the Challenge section (that is, proving that such an expression exists) or negatively (such an expression does not exist, or you can prove that neither the result nor its opposite is provable), then you will earn $500,000 in real estate from me (basically, my house in the Seattle area will belong to you).
Award for winning this challenge
Click here to check out our previous challenges.
DSC Resources
Additional Reading
Follow us on Twitter: @DataScienceCtrl | @AnalyticBridge
Tags:
Hi Vincent,
I looked at your paradox and got the convergence of the series f(x)=1/(1+f(x+1)) first and adjusted it to estimate f(n)=1/(1+nf(n+1)). The formula below is a very close estimate for the true values for all values of n.
f(n)=(SQRT(5)-1)/2/(SQRT(n)/(1+(SQRT(5)-1)/2)+(SQRT(5)-1)/4)
I know it looks strange, but it works.
Regards,
Magnus
Hi Magnus, I could not replicate your approximation. Do you have a spreadsheet to illustrate your formula?
Here's a spreadsheet with an illustration.
Your formula looks amazing up to n=260 or so, then the error increases (percentage-wise). Could be an accuracy issue with Excel, but probably there's another explanation. Certainly a very interesting chaotic system.
Hi Vincent,
This strangeness is caused by rounding errors and is not a paradox at all. If we compute results with exact numbers instead of approximate ones, we see both of the definitions of f(2) do indeed agree.
I've attached a pdf with a rough demonstration of the correct behavior (using exact arithmetic) and a rough explanation of what was causing 0.525135276 to show up.
Please let me know what you think and if you'd like me to elaborate.
So the challenge is to express 0.525135276... using a finite number of elementary transcendental functions (trigonometric, log, exp, power, polynomials, hyperbolic and their inverses), rational numbers, and/or irrational numbers such as algebraic numbers and Pi, e, or the Euler constant.
Yet only a few lines earlier, you say, f(2) = sqrt(pi*e/2)*erfc(1/sqrt(2))-1 = 0.525135276... (even though that apparently equals -0.34432045758). Is this not, then, the answer to your challenge?
The point of my post is that this constant arises because of rounding error anomalies, and it actually is not relevant to his recurrence relation. So I don't think he actually needs this information. I guess I am a bit confused now about what he is asking.
So to answer your question,
(SQRT(2/(e*pi))*ERFC(2^-0.5)^-1)-1
...or in Excel:
=(SQRT(2/(EXP(1)*PI()))*ERFC(2^-0.5)^-1)-1
...Where do I pick up the keys?
Hi Jordan,
How much is the rent on that new house you own in Seattle?
The value for f(2) is derived from Wolfram Encyclopedia. It involves the erfc function, which is not an elementary transcendental function from the list that I provided. But can it be represented by these "elementary" functions, using finite combinations? Other similar continued fractions converge to simple expressions such as e, Pi, etc. Why not this one? Do we really need to use erfc or Gamma or Bessel functions to express it? In fact, this 0.525135276... might even be a rational number. Nobody knows, but I guess it is not. This is the 0.5 million dollar question - unanswered yet.
I guess I'm a little bit confused because as I pointed out in my first post (with the attached pdf), f(2) does not equal 0.525135276..., it equals 1/a - 1.
As I said before the reason excel is giving you 0.525135276 as you iterate, is that rounding error propagated and took over. Using a CAS with exact arithmetic showed me this.
So with that said, the constant sqrt(pi*e/2)*erfc(1/sqrt(2)) should be irrelevant to the original problem, right? It has nothing to do with f(2).
Also wasn't the original paradox about how you were observing 1/a - 1 = 0.525135276...? It makes sense to you would call that a paradox, but asking if erfc(1/sqrt(2)) can be expressed in terms of elementary functions doesn't seem like a paradoxical thing to ask.