# Pieces of Pi

#### 8115911521155115811821195119311921193?

Happy Tau Day! I’m only 2 weeks late.

## Problem statement

Source: https://www.reddit.com/comments/vgrrmp

Shoutout for the extremely fun question!

### Explanation

It might be a little confusing, but let’s run through the example.

$$

72843227 \\

(7 - 2) \times 8 \div 4 + 3 - 2 \times 2 \div 7 \\

(5 \times 8 \div 4) + 3 - 2 \times 2 \div 7 \\

(10 + 3 - 2) \times 2 \div 7 \\

11 \times 2 \div 7 \\

22/7

$$

Note that PEMDAS (or BODMAS) doesn’t apply here. The operations are run left to right, in the order that they appear. The result is the commonly known $22/7$ approximation to $\pi$.

Our task is to find a sequence that gives us an approximation to $\pi$, off by no more than $10^{-9}$ percent. As an extra challenge, let’s try to be as efficient as possible (in terms of length).

## Simplifications

We can quickly see than in most cases, we can condense down the addition and subtraction into a single addition. Well, conceptually at least. If we do end up needing to add by $n$, the resulting sequence will be `"{n+1}1"`

, since we can’t use $0$.

Between multiplication and division, we can choose to simplify it by setting one of them to always be $1$. While this could possibly increase the number of required characters, we’ll see later that there’s enough leeway that this shouldn’t matter. In this case, we choose to make multiplication set to $1$, since division is the only way to get decimals, and in general reduce the size of the number.

So, we’ve reduced it down into a series of additions and divisions:

$$

\frac{\frac{0 + a}A + b} B +\ …\ \approx \pi

$$

### Algebra

We can bring down all the expressions:

$$

\frac{\frac{0 + a}A + b} B +\ …\ \approx \pi \\

\frac{a}{ABC…Z} + \frac{b}{BC…Z} +\ …\ + \frac zZ \approx \pi

$$

And multiply by $ABC…Z$:

$$

a + Ab + ABc +\ …\ + ABC…Y\ z \approx ABC…Z\ \pi

$$

And notably, all variables here are integers! More specifically, integers between $1$ and $9$ inclusive. Sans $\pi$.

## Approximations to $\pi$

With that in mind, we’re now on the hunt for a rational approximation to $\pi$, where the denominator factors into numbers lesser than or equal to $9$ ($ABC…Z$). In that case, our equation becomes

$$

a + Ab + ABc +\ …\ + ABC…Y\ z = \text{numerator} \\

ABC…Z = \text{denominator} \\

\frac {\text{numerator}}{\text{denominator}} \approx \pi

$$

### Continued fraction failure

Initially I hoped there would be a “proper” approximation using continued fractions, but of course their denominators blow the limit way out.

Below: Continued fraction approximations to $\pi$, and factorisations of their denominators.

1 | for cutoff in range(1, 10): |

1 | 3/1 1 |

### Brute force

Instead, we’ll use a blunter approach. Let’s take combinations of factors below $10$, multiply them together and check if $\operatorname{round}(\pi d)/d$ is close enough to $\pi$. Additionally, we’re trying to get as small of a sequence as possible. The number of factors in $d$ directly relates to how long the sequence is, hence we should try to reduce the number of factors.

Using `itersum`

, we can define a generator that gives us tuples where their sums are a constant number:

1 | def itersum(sums, n): |

1 | (3, 0, 0) |

We can correspond each index to a certain factor. A factor of $1$, while technically allowed in this scheme, is useless and increases our sequence length unnecessarily. Hence, we only allow factors from $2$ to $9$. After some trial and error (or binary search if you’re fancy), we see that $9$ is the minimum number of factors such that there exists a good enough approximation.

1 | def isclose(x): |

1 | 103059947 32805000 (0, 0, 0, 4, 0, 0, 1, 4) |

1 | print(103059947/32805000) |

## Coefficient solving

With that, we can define the final equation to solve:

$$

x_0 + 5x_1 + 25x_2 +\ …\ + 3645000x_9 = 103059947

$$

Here, each $x$ can take on any integer between $-8$ and $8$ inclusive. $8$ comes from the fact that the maximum allowed number for the addition is $9$, while the minimum for subtraction is $1$. Similar logic applies for $-8$.

For this final section I’ll be using z3. If you’re not familiar with it, you can check out my Oooo writeup. It’s not really needed since the equation is quite simple, but I’m lazy.

1 | from z3 import * |

1 | [7, 8, 1, 4, 7, 1, 4, 2, 1, 3] |

1 | print( |

## The sequence

Finally, we can combine it back to derive the sequence.

As mentioned before, for each of the coefficients $n$, we can add `"{n+1}1"`

to the sequence. As for the factors, we set multiplications to $1$, so we have `"1{n}"`

.

1 | out = "" |

1 | 8115911521155115811821195119311921193 |

Do note the final $+3$.

Using the convenient checker that the original question posed, we can verify our solution:

Our final length is $37$, which isn’t half bad! As of today, the 12th of July 2022, this is the shortest known sequence (52 was the shortest prior to my solution). I suspect it could be possible to get rid of the final $+3$, perhaps by shifting it earlier into the sequence as part of other additions, making for $36$.

And if you’re interested, these is the steps that are taken (also courtesy of the checker)

1 | 0 + 8 = 8 |

### $\tau$’s sequence

From here, it should be trivial to modify to give a sequence for $\tau$. We simply need to insert a $\times 2$. Of course, we first need to perform a subtraction by $1$, so the last addition becomes a $4$. A possible sequence is hence

1 | 811591152115511581182119511931192119412 |

But we can do better! Repeating the whole process with $\tau$, we obtain:

1 | 5115411511155115811841199119511931196 |

### Other sequences

Here, I’ll dump some other constants and their sequences as found by my method. Following the original question, all sequences here evaluate to within $10^{-9}$ percent of the constant.

Constant | Sequence | Length |
---|---|---|

$\sqrt 2$ | 31184118711851188118511811185118311841181 | 41 |

$\varphi$ | 21177119411961193119911951191119611961191 | 41 |

$e$ | 7118611841198119611961192119511971192 | 37 |

$\ln 2$ | 6117611741188119611971193119211931197119 | 40 |

$\gamma$ | 5115511581151115711561177117211781174117 | 40 |