Detailed mathematical approach

Problem Summary

We begin at \((45,90)\) and may apply the two operations

$r:(x,y)\mapsto(x+1,2y),\qquad s:(x,y)\mapsto(2x,y+1).$

A valid word is a finite string of \(r\) and \(s\) steps that reaches \(x=y\) at the end, but not at any earlier intermediate state. The implementation fixes counts \(R\) and \(S\) for the two operations, counts how many valid words exist for that pair, truncates the count to \(0\), \(1\), or \(\ge 2\), and then searches over total lengths \(m=R+S\). A preliminary unrestricted scan finds a 9-step equality at value \(1476\); the actual output scan then restricts to even lengths and returns the first even-length case with a unique valid word.

Mathematical Approach

The core difficulty is that order matters: the two operations do not commute, and each later doubling amplifies earlier additive contributions. The program therefore combines exact recursion with a strong mathematical pruning rule.

Step 1: Encode a Word by How Many Doublings Happen After Each Additive Step

Suppose we are currently at \((x,y)\) and still plan to use exactly \(R\) letters \(r\) and \(S\) letters \(s\). Every \(r\)-step adds \(1\) to \(x\), but that added \(1\) may later be doubled by some of the remaining \(s\)-steps. Likewise every \(s\)-step adds \(1\) to \(y\), and that contribution may later be doubled by later \(r\)-steps.

If the \(i\)-th \(r\)-step has \(\sigma_i\) later letters \(s\) after it, and the \(j\)-th \(s\)-step has \(\rho_j\) later letters \(r\) after it, then the final coordinates are

$x_{\mathrm{final}}=x\,2^S+\sum_{i=1}^{R}2^{\sigma_i},\qquad y_{\mathrm{final}}=y\,2^R+\sum_{j=1}^{S}2^{\rho_j}.$

This formula explains why the search is delicate: the same multiset of letters can produce very different results depending on their order.

Step 2: Derive Guaranteed Bounds for the Final Difference

From the representation above, each \(r\)-contribution lies between \(1\) and \(2^S\), so

$x\,2^S+R\le x_{\mathrm{final}}\le x\,2^S+R\,2^S.$

Similarly, each \(s\)-contribution lies between \(1\) and \(2^R\), so

$y\,2^R+S\le y_{\mathrm{final}}\le y\,2^R+S\,2^R.$

During the recursion the implementation applies the same idea to a partial state \((x,y)\) with remaining counts \(r_{\mathrm{rem}}\) and \(s_{\mathrm{rem}}\). It computes

$x_{\min}=x\,2^{s_{\mathrm{rem}}}+r_{\mathrm{rem}},\qquad x_{\max}=x\,2^{s_{\mathrm{rem}}}+r_{\mathrm{rem}}\,2^{s_{\mathrm{rem}}},$

$y_{\min}=y\,2^{r_{\mathrm{rem}}}+s_{\mathrm{rem}},\qquad y_{\max}=y\,2^{r_{\mathrm{rem}}}+s_{\mathrm{rem}}\,2^{r_{\mathrm{rem}}}.$

Therefore every possible completion satisfies

$\Delta_{\min}=x_{\min}-y_{\max}\le x_{\mathrm{final}}-y_{\mathrm{final}}\le x_{\max}-y_{\min}=\Delta_{\max}.$

If \(0\notin[\Delta_{\min},\Delta_{\max}]\), no completion can possibly end with equality, so that entire branch is discarded immediately. This is a necessary condition, not a full characterization, but it cuts away most of the hopeless search space.

Step 3: Use Memoized Dynamic Programming for Exact Counting

For fixed targets \(R\) and \(S\), define

$C(x,y,a,b)=\text{number of valid completions from state }(x,y)\text{ after already using }a\text{ letters }r\text{ and }b\text{ letters }s.$

The recursive structure is immediate:

$C(x,y,a,b)=C(x+1,2y,a+1,b)+C(2x,y+1,a,b+1),$

with the understanding that a branch is used only if its corresponding operation count has not yet reached the target.

The terminal rule is

$C(x,y,R,S)=\mathbf{1}_{x=y},$

and any state with \(x=y\) before all letters are consumed is rejected, because equality must occur only at the final step.

The implementation does not store the exact count. It stores only \(0\), \(1\), or \(2\), where \(2\) means “at least two”. That is enough because the outer search only needs to distinguish impossible, unique, and non-unique cases.

Step 4: Search Over Compositions of the Total Length

For each total length \(m\), every split

$R+S=m,\qquad 0\le R\le m$

is tested. For that fixed pair, the memoized recursion determines whether there are no valid words, exactly one valid word, or several. If at least one valid word exists, the implementation can reconstruct a witness by repeatedly moving to a child state whose memoized count is positive.

The unrestricted scan over all \(m\) finds the first successful case at

$m=9,\qquad (R,S)=(4,5),\qquad x_{\mathrm{final}}=y_{\mathrm{final}}=1476.$

The final output phase then scans only even \(m\) and returns the first even length for which the valid word is unique across all tested splits. That first even solution occurs at \(m=96\), with returned value

$25332747903959376.$

Step 5: Worked Example

Consider the unrestricted success found at \(m=9\) with \(R=4\) and \(S=5\). The interval test at the initial state gives

$x_{\min}=45\cdot 2^5+4=1444,\qquad x_{\max}=45\cdot 2^5+4\cdot 2^5=1584,$

$y_{\min}=90\cdot 2^4+5=1445,\qquad y_{\max}=90\cdot 2^4+5\cdot 2^4=1520.$

Because the two intervals overlap, equality is not ruled out. One valid word is

"rssssrsrr", which evolves as

$\begin{aligned} (45,90)&\xrightarrow{r}(46,180)\xrightarrow{s}(92,181)\xrightarrow{s}(184,182)\xrightarrow{s}(368,183)\xrightarrow{s}(736,184),\\ &\xrightarrow{r}(737,368)\xrightarrow{s}(1474,369)\xrightarrow{r}(1475,738)\xrightarrow{r}(1476,1476). \end{aligned}$

This is exactly the shortest successful equality checked by the implementation before the even-length output search begins.

How the Code Works

The C++, Python, and Java implementations all follow the same structure. For each target pair \((R,S)\), they memoize states determined by the current coordinates together with how many times each operation has already been used. Before recursing, they apply the interval test above; if equality is outside the reachable final-difference range, that state returns immediately.

Whenever a state is not pruned, the implementation explores the two possible next moves, truncates the total count at \(2\), and stores that result in the memo table. If a positive count is found for a candidate \((R,S)\), one witness word is reconstructed by following a child whose memoized count remains positive. That witness is then simulated explicitly to confirm that equality occurs at the end and nowhere earlier.

The C++ implementation also performs two built-in checkpoints: first it confirms the shortest unrestricted equality at \(m=9\) with final value \(1476\), then it confirms that the first even-length answer is unique. The final printed value is

$25332747903959376.$

Complexity Analysis

For a fixed pair \((R,S)\), naive enumeration would inspect all \(\binom{R+S}{R}\) words, which is exponential in the total length. Memoization collapses repeated subproblems with the same current state, and the interval bound removes large parts of the recursion tree before they branch further.

Even with those improvements, there is no simple polynomial worst-case bound coming from the code alone, because the numerical states grow under repeated doubling and the number of distinct reachable states still depends on the search path. The practical cost is therefore best described as exponential search with strong pruning. Memory usage is proportional to the number of memoized states for the current \((R,S)\), plus the cost of storing integers large enough to survive many doublings.

Footnotes and References

1. Problem page: Project Euler 736 - Paths to Equality
2. Dynamic programming: Wikipedia - Dynamic programming
3. Memoization: Wikipedia - Memoization
4. Branch and bound: Wikipedia - Branch and bound
5. Affine transformation: Wikipedia - Affine transformation