Subscribe to DSC Newsletter

* 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

Views: 7992

Reply to This

Replies to This Discussion

The core of the problem is whether or not 1/(1+2/(1+3/(1+4/(1+5/...)))) = 0.525135276... = function of Pi, e, SQRT, erfc,  can be expressed using a finite combination of elementary functions - that is, not including erfc. The interest is because most its sister continued fractions do, but this one does not seem to. 

It's known that it can't be expressed in terms of elementary functions. I believe the Risch algorithm shows this.

Yes for efrc in general (as a function). But here we are dealing with a specific value. Even proving that 0.5251... is irrational, is no easy task, and has probably never been done.

The continued fraction form tells you it cannot be rational (or quadratic algebraic).

All rational or quadratic algebraic numbers have periodic developments as continued fractions. But there are many ways to represent a number as a continued fraction, for instance Pi has its traditional standard a-periodic development (that looks chaotic) and one that uses 1, 9, 25, 49, 81 (the odd squares) which is also a-periodic. But I'm not aware of a theorem that claims that a rational or quadratic algebraic number can not be represented by an a-periodic (obviously non standard) continued fraction. Maybe such a result exists, I'm just not aware of it. If it does exist, it would help solve the mystery regarding the nature of many numbers (is it a rational or not). I would think - maybe I'm wrong - that you can create a made-up continued, a-periodic fraction, converging to a rational number, by design.

[Not to worry, the house is safe so far as this post is concerned.]

the limiting behavior should be a root of f_infinity=1/(1 + n*f_infinity). This is a quadratic and one gets solutions (-1 - sqrt(1 + 4 n))/(2 n) and (-1 + ...)/...

That first one is the "correct" one in terms of the sequence having an asymptotic behavior, at least for initial values I have tried.

If one does a forward iteration say from 1 to 50 with whatever initial value 'a' for f(1) then, iterating backwards from f(50) should NOT approximate your f(2). But perturbing slightly from f(50) and iterating backwards will give an approximation to that value. "Slightly" is loose wording: make it small enough and again you do not recover that f(2) value.

I think what happens is along these lines. If your initial value for f(large n) is sufficiently close to (-1 - sqrt(1 + 4 n))/(2 n), then it will correspond to a value obtained by iterating forward from some seed value 'a' for f(1). In that case, iterating backwards will simply give approximately (1 - a)/a. Away from (-1 - sqrt(1 + 4 n))/(2 n), backwards iterations will approach the value you found. There is a midrange for perturbations, wherein one approaches neither of these.

Since the iteration for nth term is defined explicitly in terms of n this seems to be a generalization of the dynamics that involve Fatou and Julia sets. Might be related though (I simply do not know enough about that stuff to say).

Here's an interesting comment from one of our readers:


You've just found a mathematical thing, that is called a 'chaotic attractor'. Read: Tönu Puu:"Attractors, Bifurcations, and Chaos: Nonlinear Phenomena in Economics"http://www.springer.com/gp/book/9783662040942

These often appear like 'natural constants' and sometimes appear in context of well known, mathematical functions or irrational mathematical constants, which can also be produced by recursive functions.

Also see 'point clouds' and Haussdorff. Mathematics, around 100 years old.

Have fun!

RSS

On Data Science Central

© 2019   AnalyticBridge.com is a subsidiary and dedicated channel of Data Science Central LLC   Powered by

Badges  |  Report an Issue  |  Privacy Policy  |  Terms of Service