This is our new challenge of the week. Previous challenges can be found here. 

While infinite products are equivalent to infinite sums when you take the logarithm, here we are interested in off-the-beaten-path, intriguing facts related to some special infinite products representations. Some of the questions raised here are very difficult.   

We are interested in strictly positive real numbers z with z < 1, and representations of z of the form

z = Product[ ( c(k) - 1 + d(k)  )  / c(k) ]

where the product is over all k = 1, 2, 3... and

• d(k) is equal either to 0 or 1
• c(k) is an increasing sequence of integers: either c(k) = k for all k, or c(k) = k^2 for all k.

Let's define a(k) = c(k) - 1 + d(k) and x(k) as the product of the first k factors a(1) / c(1), ... , a(k) / c(k).

The binary coefficients d(k) that uniquely identify z, are recursively defined as follow::

if x(k) * { c(k+1) - 1 } / c(k+1) > z, then d(k+1) = 0, else d(k+1) = 1,

with a(1) = d(1) = x(1) = 1. 

In short, the sequence x(k), starting with x(1) = 1, is decreasing and eventually (hopefully) converges to z as k tends to infinity. 

Code to compute z's expansion as an infinite product

The following piece of code computes all the k's such that d(k) = 0, for a given z. The d(k)'s that are equal to 1 have no impact on the infinite product as the corresponding factors a(k) / c(k) are equal to 1. 

  $z=sqrt(2)/2; # for illustration purposes
  $n=500000;

  $x=1;

  for ($k=1; $k<$n; $k++) {
    $c=$k*$k;
    if ( $z < $x * ($c-1) / $c) {
      $x = $x * ($c-1) / $c;
      print "$k > $c | $x\n";
    }
  }  

This program prints k, c(k) and x(k) any time there is a change (a factor not equal to 1) in the product expansion of z. These values of k with d(k) = 0 are called jump points. As k tends to infinity, the (infinite) product x(k) tends to z. 

Example

For z = SQRT(2) / 2 = 0.707106781186548, we get the successive approximations:

• k = 2 : x(k) = 3/4 = 0.75 
• k = 5 : x(k) = 3/4 * 24/25 = 0.72
• k = 8 : x(k) = 3/4 * 24/25 * 63/64 = 0.70875
• k = 21 : x(k) = 3/4 * 24/25 * 63/64 * 440/441 = 0.707142857142857
• k = 141 : x(k) = 3/4 * 24/25 * 63/64 * 440/441 * 19880/19881 = 0.707107288365776
• k = 1181 : x(k) = 3/4 * 24/25 * 63/64 * 440/441 * 19880/19881 * 1394760/1394761 = 0.707106781391973
• k = 58670 : x(k) = 3/4 * 24/25 * 63/64 * 440/441 * 19880/19881 * 1394760/1394761 * 3442168999/3442168900 = 0.707106781186549

As k increases, x(k) gets closer and closer to the target z = .0.707106781186548.  

The challenge

Here are several questions of increasing difficulty:

• The above piece of code is extremely inefficient as the vast majority of factors being computed are equal to 1. How to optimize the code to skip these useless computations?

• If z = SQRT(2) / 2, by squaring both sides of the inequality x(k) * { c(k+1) - 1 } / c(k+1) > z, we get rid of the irrational number and thus we have found a recursive formula to compute an irrational number as an infinite product, using only rational numbers. Compare this technique with the methodology to produce all binary digits of SQRT(2) / 2, described here. 

• Prove that the algorithm always converges to z if c(k) = k. Is this also true if c(k) = k^2? What if c(k) = k^3? Is convergence faster if c(k) = k or if c(k) = k^2?

• In the above example, the jumps occur at k = 2, 5, 8, 21, 141, 1181, 58670 and so on (see example.) Indeed, the sequence of jumps uniquely characterizes z, just like the digits of z in base 10 also characterizes z. Can you find the asymptotic behavior of these jumps, or some patterns associated with these jumps? Try with various values of z. 

• Same as previous question, but replacing c(k) = k^2 by c(k) = k.Then the jumps get incredibly rare. For instance if z = SQRT(2) / 2, the first four jumps occur at k = 4, 18, 578, 665858.

• Is the following statement true: the number of jumps, for a given z, is finite if and only if z is a rational number.

• Develop the same methodology for representations of z as infinite sums, that is, z = Sum[ ( 1 -  d(k)  )  / c(k) ] where the sum is over all k = 1, 2, 3... and d(k) is equal either to 0 or 1, and c(k) is an increasing sequence of integers: either c(k) = k for all k, or c(k) = k^2 for all k. When c(k) = k and z = SQRT(2) / 2, the jumps occur at 2, 5, 141, 68575 etc. that is, z = 1/2 + 1/5 + 1/141 + 1/68575 + ... With c(k) = k^2, the sequence of x(k)'s does not converge to z. The equivalent source code for infinite sums is

        $z=sqrt(2)/2;
        $n=5000000;

        $x=0;

        for ($k=1; $k<$n; $k++) {
          $c=$k; 
          if ( $z > $x + 1/$c) {
            $x = $x + 1/$c;
            print "$k > $c | $x ($z)\n";
          }
        }

Follow @analyticbridge

Top DSC Resources

• Article: What is Data Science? 24 Fundamental Articles Answering This Question
• Article: Hitchhiker's Guide to Data Science, Machine Learning, R, Python
• Tutorial: Data Science Cheat Sheet
• Tutorial: How to Become a Data Scientist - On Your Own
• Categories: Data Science - Machine Learning - AI - IoT - Deep Learning
• Tools: Hadoop - DataViZ - Python - R - SQL - Excel
• Techniques: Clustering - Regression - SVM - Neural Nets - Ensembles - Decision Trees
• Links: Cheat Sheets - Books - Events - Webinars - Tutorials - Training - News - Jobs
• Links: Announcements - Salary Surveys - Data Sets - Certification - RSS Feeds - About Us
• Newsletter: Sign-up - Past Editions - Members-Only Section - Content Search - For Bloggers
• DSC on: Ning - Twitter - LinkedIn - Facebook - GooglePlus

Follow us on Twitter: @DataScienceCtrl | @AnalyticBridge