Approximate $\pi$ using Gauss Circle Problem and Pick's Theorem.

115 Views Asked by At

Introduction

For any non-negative integer $k$, $x^2+y^2=5^k$ has $4(k+1)$ integer solutions (vertices).

For example, here are 3 circles for $k=1,2,3$. The blue dots represent the vertices (integer solutions), then connect the dots to form polygons (dash lines). The red dots represent the points in-between the vertices.

circle_pi

Tabulated the number of in-between points using this formula

$$\sum_{i=0}^{4(k+1)-1} \left( \gcd \left( |x_{i+1} - x_i|, |y_{i+1} - y_i| \right) - 1 \right)$$

k    Vertices 4(k+1)     In-between Points
1    8                   4                   
2    12                  0                   
3    16                  28                  
4    20                  40                  
5    24                  116                 
6    28                  144                 
7    32                  524                 
8    36                  1272                
9    40                  3028                
10   44                  5984                
11   48                  10780               
12   52                  23440               
13   56                  63444               
14   60                  117480  <--- Used in the example below

Approximation Formula for $\pi$

$$\small\pi \approx \frac{1}{5^k} \left[ 4 \sum_{i=0}^{\infty} \left( \left\lfloor \frac{5^k}{4i+1} \right\rfloor - \left\lfloor \frac{5^k}{4i+3} \right\rfloor \right) - 2(k+1) - \frac{1}{2} \sum_{i=0}^{4(k+1)-1} \left( \gcd \left( |x_{i+1} - x_i|, |y_{i+1} - y_i| \right) - 1 \right) \right] $$

Example

Let $k = 14$, then

$$\small\pi \approx \frac{1}{5^{14}} \left[ 4 \sum_{i=0}^{\infty} \left( \left\lfloor \frac{5^{14}}{4i+1} \right\rfloor - \left\lfloor \frac{5^{14}}{4i+3} \right\rfloor \right) - 30 - \frac{1}{2} \sum_{i=0}^{59} \left( \gcd \left( |x_{i+1} - x_i|, |y_{i+1} - y_i| \right) - 1 \right) \right] $$

Applying the precomputed value (see table above) shows

$$\sum_{i=0}^{59} \left( \gcd \left( |x_{i+1} - x_i|, |y_{i+1} - y_i| \right) - 1 \right) = 117480$$

and reduces to

$$\pi \approx \frac{1}{5^{14}} \left[ 4 \sum_{i=0}^{\infty} \left( \left\lfloor \frac{5^{14}}{4i+1} \right\rfloor - \left\lfloor \frac{5^{14}}{4i+3} \right\rfloor \right) - 58770 \right] $$

Plugging into WolframAlpha gives

$$\pi \approx 3.14158$$

Question

Is it possible to compute the number of in-between points on-the-fly instead of using a precomputed table lookup? I tried WolframAlpha but without success.

I've never used Mathematica but it would be nice run a calculation for $\pi$ by prepping it first and then supplying

$$\small\frac{1}{5^k} \left[ 4 \sum_{i=0}^{\infty} \left( \left\lfloor \frac{5^k}{4i+1} \right\rfloor - \left\lfloor \frac{5^k}{4i+3} \right\rfloor \right) - 2(k+1) - \frac{1}{2} \sum_{i=0}^{4(k+1)-1} \left( \gcd \left( |x_{i+1} - x_i|, |y_{i+1} - y_i| \right) - 1 \right) \right] $$

Reference