Detailed mathematical approach

Problem Summary

Problem 770 asks for the smallest \(n\) for which the Delphi Flip value reaches a prescribed target \(x\). The implementations reduce that value to the closed form

$D_n=\frac{2}{1+r_n},\qquad r_n=\frac{\binom{2n}{n}}{4^n}.$

Therefore the search problem becomes: given \(x\in(1,2)\), find the least \(n\ge 0\) such that \(D_n\ge x\). Because \(r_n\) decreases to \(0\), this is equivalent to detecting the first time a central-binomial ratio drops below a threshold.

Mathematical Approach

Let

$g(x)=\min\{n\ge 0:D_n\ge x\}.$

The implementations solve this by turning the original inequality into a monotone threshold test for \(r_n\), then combining an exact recurrence with a large-\(n\) asymptotic estimate.

Step 1: Rewrite the target inequality

Starting from

$D_n=\frac{2}{1+r_n},$

the condition \(D_n\ge x\) is equivalent to

$\frac{2}{1+r_n}\ge x \iff 1+r_n\le \frac{2}{x} \iff r_n\le \frac{2}{x}-1.$

If we define the threshold

$\tau=\frac{2}{x}-1,$

then the whole problem becomes

$g(x)=\min\{n\ge 0:r_n\le \tau\}.$

This reformulation is the key reason the code never needs to simulate the game directly.

Step 2: Derive the exact recurrence for the central ratio

The central ratio is

$r_n=\frac{(2n)!}{(n!)^2\,4^n}.$

Comparing consecutive terms gives

$\frac{r_n}{r_{n-1}}=\frac{(2n)!}{(n!)^2\,4^n}\cdot\frac{((n-1)!)^2\,4^{n-1}}{(2n-2)!}=\frac{2n-1}{2n}.$

Hence

$r_0=1,\qquad r_n=r_{n-1}\frac{2n-1}{2n}\quad(n\ge 1).$

Because \(\frac{2n-1}{2n}<1\) for every \(n\ge 1\), the sequence \((r_n)\) is strictly decreasing. That monotonicity guarantees that once \(r_n\) has gone below \(\tau\), the first crossing index is unique.

Step 3: Use the large-\(n\) asymptotic expansion

For small thresholds, the answer is large, so a direct forward sweep would take too many steps. The implementations therefore use the asymptotic expansion of the central binomial coefficient:

$r_n\approx \frac{1}{\sqrt{\pi n}}\left(1-\frac{1}{8n}+\frac{1}{128n^2}+\frac{5}{1024n^3}-\frac{21}{32768n^4}\right).$

The leading term is \(1/\sqrt{\pi n}\), so the first approximation to the crossing point is obtained by solving

$\frac{1}{\sqrt{\pi n}}\approx \tau,$

which yields

$n\approx \frac{1}{\pi\tau^2}.$

This gives a very good starting index when \(x\) is close to \(2\), precisely the regime that matters for the final query.

Step 4: Correct the estimate deterministically

The asymptotic series gives an estimate, not an exact answer, so the implementations finish with exact multiplicative updates. First an initial guess is taken as

$n_0=\left\lfloor\frac{1}{\pi\tau^2}\right\rfloor.$

The truncated asymptotic formula is evaluated at \(n_0\). If that estimated value is already at or below the threshold, the implementations walk backward using

$r_{n-1}=r_n\frac{2n}{2n-1}$

until they are just above the threshold. Then they move forward again with

$r_{n+1}=r_n\frac{2n+1}{2n+2}$

until the first valid index is reached. Because the sequence is monotone and the asymptotic start is close to the true answer, only a short correction loop is needed in the large-\(n\) regime.

Step 5: Use a direct branch when the answer is small

When the estimate \(n_0\) is modest, the simplest method is also the most reliable: start from \(r_0=1\) and repeatedly apply

$r_n=r_{n-1}\frac{2n-1}{2n}$

until \(r_n\le \tau\). The implementations switch to this direct branch whenever the asymptotic estimate is below a fixed cutoff. That avoids unnecessary asymptotic work for easy inputs.

Worked Example: \(x=1.7\)

This checkpoint appears in the implementations. First compute

$\tau=\frac{2}{1.7}-1=\frac{3}{17}\approx 0.1764705882.$

Now compare the two consecutive central ratios around the crossing:

$r_9=\frac{\binom{18}{9}}{4^9}=\frac{12155}{65536}\approx 0.1854705811,$

$r_{10}=\frac{\binom{20}{10}}{4^{10}}=\frac{46189}{262144}\approx 0.1761970520.$

Since \(r_9>\tau\) but \(r_{10}\le \tau\), the first valid index is

$g(1.7)=10.$

Equivalently, \(D_9<1.7\) and \(D_{10}\ge 1.7\), so the minimum is exactly \(10\).

How the Code Works

The C++, Python, and Java implementations follow the same strategy. They first convert the requested target \(x\) into the threshold \(\tau=2/x-1\). Next they compute the coarse estimate \(\lfloor 1/(\pi\tau^2)\rfloor\). If that estimate is small, they iterate the exact recurrence from \(n=0\), updating the ratio by a single multiplication at each step.

If the estimate is large, they evaluate the truncated asymptotic series at that index and then repair any approximation error by stepping backward or forward with the exact recurrence ratio until the minimal valid \(n\) is found. No factorials, huge binomial coefficients, or large integer tables are required; the algorithm works entirely with a few floating-point quantities and exact multiplicative transitions between consecutive terms.

Complexity Analysis

The direct branch takes \(O(g(x))\) time because it visits every index from \(0\) up to the answer, and it uses \(O(1)\) memory. In the large-\(n\) branch, the asymptotic estimate is computed in \(O(1)\) time and the correction loop is typically very short, so the practical running time is close to constant while the memory usage remains \(O(1)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=770
2. Central binomial coefficient: Wikipedia — Central binomial coefficient
3. Binomial coefficient: Wikipedia — Binomial coefficient
4. Stirling's approximation: Wikipedia — Stirling's approximation
5. Asymptotic expansions related to central binomial coefficients: MathWorld — Central Binomial Coefficient