Pieces of Pi

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.

for cutoff in range(1, 10):
    frac = continued_fraction(pi)[:cutoff]
    frac = frac.value()
    
    numer = frac.numerator()
    denom = frac.denominator()
    
    print(f"{f'{numer}/{denom}':<15}", factor(denom))

3/1             1
22/7            7
333/106         2 * 53
355/113         113
103993/33102    2 * 3^3 * 613
104348/33215    5 * 7 * 13 * 73
208341/66317    17 * 47 * 83
312689/99532    2^2 * 149 * 167
833719/265381   265381

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:

def itersum(sums, n):
    if n == 1:
        yield (sums, )
        return
    if sums == 0:
        yield tuple(0 for _ in range(n))                                    
        return
        
    for i in range(sums+1):
        for lower in itersum(sums-i, n-1):
            yield lower + (i,)
            
    return

for x in itersum(3, 3):
    print(x)

(3, 0, 0)
(2, 1, 0)
(1, 2, 0)
(0, 3, 0)
(2, 0, 1)
(1, 1, 1)
(0, 2, 1)
(1, 0, 2)
(0, 1, 2)
(0, 0, 3)

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.

def isclose(x):
    return 3.141592653558377 <= x <= 3.141592653621209

for nfacs in itersum(9, 8):
    fac = 1
    for pos, x in enumerate(nfacs):
        fac *= (pos+2)^x
        
    top = round(pi * fac)
    if isclose(top/fac):
        print(top, fac, nfacs)

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

print(103059947/32805000)
# 3.1415926535589085

print(4^5 * 8 * 9^4)
# 32805000
# (0, 0, 0, 4, 0, 0, 1, 4)
#  2  3  4  5  6  7  8  9

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.

from z3 import *

vars = [Int(f"x{i}") for i in range(10)]

s = Solver()

# force to specific values
for v in vars:
    s.add(Or([v == i for i in range(9)]))

# actual equation
x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 = vars
cond = x0 + 5*x1 + 25*x2 + 125*x3 + 625*x4 + 5000*x5 + 45000 * \
    x6 + 405000*x7 + 3645000*x8 + 32805000*x9 == 103059947
s.add(cond)

s.check()
m = s.model()
print([m[x].as_long() for x in vars])

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

print(
    7 + 5 * 8 + 25 * 1 + 125 * 4 + 625 * 7 + 5000 * 1 + \
    45000 * 4 + 405000 * 7 + 3645000 * 1 + 32805000 * 3 
)
# 103059947

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}".

out = ""
ads = [7, 8, 1, 4, 7, 1, 4, 2, 1, 3]
facs = [9] * 4 + [8] + [5]*4

for add, fac in zip(ads, facs):
    out += f"{add+1}11{fac}"
    
print(out + str(ads[-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)

0 + 8 = 8
8 - 1 = 7
7 * 1 = 7
7 / 5 = 1.4
1.4 + 9 = 10.4
10.4 - 1 = 9.4
9.4 * 1 = 9.4
9.4 / 5 = 1.8800000000000001
1.8800000000000001 + 2 = 3.88
3.88 - 1 = 2.88
2.88 * 1 = 2.88
2.88 / 5 = 0.576
0.576 + 5 = 5.576
5.576 - 1 = 4.576
4.576 * 1 = 4.576
4.576 / 5 = 0.9151999999999999
0.9151999999999999 + 8 = 8.9152
8.9152 - 1 = 7.9152000000000005
7.9152000000000005 * 1 = 7.9152000000000005
7.9152000000000005 / 8 = 0.9894000000000001
0.9894000000000001 + 2 = 2.9894
2.9894 - 1 = 1.9893999999999998
1.9893999999999998 * 1 = 1.9893999999999998
1.9893999999999998 / 9 = 0.22104444444444443
0.22104444444444443 + 5 = 5.221044444444445
5.221044444444445 - 1 = 4.221044444444445
4.221044444444445 * 1 = 4.221044444444445
4.221044444444445 / 9 = 0.469004938271605
0.469004938271605 + 3 = 3.469004938271605
3.469004938271605 - 1 = 2.469004938271605
2.469004938271605 * 1 = 2.469004938271605
2.469004938271605 / 9 = 0.27433388203017833
0.27433388203017833 + 2 = 2.274333882030178
2.274333882030178 - 1 = 1.2743338820301782
1.2743338820301782 * 1 = 1.2743338820301782
1.2743338820301782 / 9 = 0.14159265355890868
0.14159265355890868 + 3 = 3.1415926535589085

$\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

811591152115511581182119511931192119412

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

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