Problem 736: Paths to Equality
View on Project EulerProject Euler Problem 736 Solution
EulerSolve provides an optimized solution for Project Euler Problem 736, Paths to Equality, with C++, Python, Java, and a step-by-step mathematical explanation.
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....
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
- Problem page: Project Euler 736 - Paths to Equality
- Dynamic programming: Wikipedia - Dynamic programming
- Memoization: Wikipedia - Memoization
- Branch and bound: Wikipedia - Branch and bound
- Affine transformation: Wikipedia - Affine transformation
Problem 736 source code
C++
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <optional>
#include <string>
#include <unordered_map>
#include <vector>
namespace {
using u64 = std::uint64_t;
using u128 = __uint128_t;
using i128 = __int128_t;
constexpr u128 kStartX = 45;
constexpr u128 kStartY = 90;
constexpr int kMaxM = 120;
u64 splitmix64(u64 x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30U)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27U)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31U);
}
struct StateKey {
u128 x;
u128 y;
std::uint16_t r;
std::uint16_t s;
bool operator==(const StateKey& other) const {
return x == other.x && y == other.y && r == other.r && s == other.s;
}
};
struct StateKeyHash {
std::size_t operator()(const StateKey& key) const {
const u64 x_lo = static_cast<u64>(key.x);
const u64 x_hi = static_cast<u64>(key.x >> 64U);
const u64 y_lo = static_cast<u64>(key.y);
const u64 y_hi = static_cast<u64>(key.y >> 64U);
u64 h = splitmix64(x_lo);
h ^= splitmix64(x_hi + 0x123456789abcdef0ULL);
h ^= splitmix64(y_lo + 0x3141592653589793ULL);
h ^= splitmix64(y_hi + 0x2718281828459045ULL);
h ^= splitmix64((static_cast<u64>(key.r) << 16U) ^ static_cast<u64>(key.s));
return static_cast<std::size_t>(h);
}
};
std::string to_string_u128(u128 value) {
if (value == 0) {
return "0";
}
std::string out;
while (value > 0) {
const int digit = static_cast<int>(value % 10);
out.push_back(static_cast<char>('0' + digit));
value /= 10;
}
std::reverse(out.begin(), out.end());
return out;
}
struct SearchSolver {
int R;
int S;
const std::vector<u128>& pow2;
std::unordered_map<StateKey, std::uint8_t, StateKeyHash> memo;
SearchSolver(const int r_target, const int s_target, const std::vector<u128>& pow2_ref)
: R(r_target), S(s_target), pow2(pow2_ref) {
memo.reserve(4096U);
}
bool can_reach_zero(const u128 x, const u128 y, const int r_rem, const int s_rem) const {
const i128 min_diff = static_cast<i128>(x) * static_cast<i128>(pow2[static_cast<std::size_t>(s_rem)]) +
static_cast<i128>(r_rem) -
(static_cast<i128>(y) * static_cast<i128>(pow2[static_cast<std::size_t>(r_rem)]) +
static_cast<i128>(s_rem) * static_cast<i128>(pow2[static_cast<std::size_t>(r_rem)]));
const i128 max_diff = static_cast<i128>(x) * static_cast<i128>(pow2[static_cast<std::size_t>(s_rem)]) +
static_cast<i128>(r_rem) * static_cast<i128>(pow2[static_cast<std::size_t>(s_rem)]) -
(static_cast<i128>(y) * static_cast<i128>(pow2[static_cast<std::size_t>(r_rem)]) +
static_cast<i128>(s_rem));
return min_diff <= 0 && max_diff >= 0;
}
std::uint8_t count_paths(const u128 x, const u128 y, const int r_used, const int s_used) {
if (r_used == R && s_used == S) {
return (x == y) ? 1U : 0U;
}
if (x == y) {
return 0U;
}
const int r_rem = R - r_used;
const int s_rem = S - s_used;
if (!can_reach_zero(x, y, r_rem, s_rem)) {
return 0U;
}
const StateKey key{x, y,
static_cast<std::uint16_t>(r_used),
static_cast<std::uint16_t>(s_used)};
const auto it = memo.find(key);
if (it != memo.end()) {
return it->second;
}
std::uint8_t total = 0U;
if (r_used < R) {
total = static_cast<std::uint8_t>(
std::min<int>(2, total + count_paths(x + 1U, y * 2U, r_used + 1, s_used)));
}
if (s_used < S && total < 2U) {
total = static_cast<std::uint8_t>(
std::min<int>(2, total + count_paths(x * 2U, y + 1U, r_used, s_used + 1)));
}
memo.emplace(key, total);
return total;
}
std::string reconstruct_one_path() {
std::string path;
path.reserve(static_cast<std::size_t>(R + S));
u128 x = kStartX;
u128 y = kStartY;
int r_used = 0;
int s_used = 0;
while (!(r_used == R && s_used == S)) {
bool moved = false;
if (r_used < R && count_paths(x + 1U, y * 2U, r_used + 1, s_used) > 0U) {
path.push_back('r');
x = x + 1U;
y = y * 2U;
++r_used;
moved = true;
} else if (s_used < S && count_paths(x * 2U, y + 1U, r_used, s_used + 1) > 0U) {
path.push_back('s');
x = x * 2U;
y = y + 1U;
++s_used;
moved = true;
}
if (!moved) {
return {};
}
}
return path;
}
};
u128 apply_path_and_final_value(const std::string& path) {
u128 x = kStartX;
u128 y = kStartY;
for (std::size_t i = 0; i < path.size(); ++i) {
if (path[i] == 'r') {
x = x + 1U;
y = y * 2U;
} else {
x = x * 2U;
y = y + 1U;
}
if (i + 1U < path.size() && x == y) {
return 0U;
}
}
return (x == y) ? x : 0U;
}
struct SearchResult {
int m = -1;
int R = -1;
int S = -1;
std::uint8_t count = 0;
u128 final_value = 0;
std::string path;
};
std::optional<SearchResult> find_first_solution(const bool only_even_m,
const std::vector<u128>& pow2) {
for (int m = 0; m <= kMaxM; ++m) {
if (only_even_m && (m % 2 != 0)) {
continue;
}
SearchResult best{};
bool found = false;
for (int R = 0; R <= m; ++R) {
const int S = m - R;
SearchSolver solver(R, S, pow2);
const std::uint8_t c = solver.count_paths(kStartX, kStartY, 0, 0);
if (c == 0U) {
continue;
}
const std::string path = solver.reconstruct_one_path();
const u128 final_value = apply_path_and_final_value(path);
if (final_value == 0U) {
continue;
}
if (!found) {
found = true;
best.m = m;
best.R = R;
best.S = S;
best.count = c;
best.path = path;
best.final_value = final_value;
} else {
best.count = 2U;
}
}
if (found) {
return best;
}
}
return std::nullopt;
}
} // namespace
int main() {
std::vector<u128> pow2(static_cast<std::size_t>(kMaxM + 1), 1U);
for (int i = 1; i <= kMaxM; ++i) {
pow2[static_cast<std::size_t>(i)] = pow2[static_cast<std::size_t>(i - 1)] * 2U;
}
const auto first_any = find_first_solution(false, pow2);
assert(first_any.has_value());
assert(first_any->m == 9);
assert(first_any->final_value == 1476U);
const auto first_odd_length = find_first_solution(true, pow2);
assert(first_odd_length.has_value());
assert(first_odd_length->count == 1U);
std::cout << to_string_u128(first_odd_length->final_value) << '\n';
return 0;
}
Python
kStartX = 45
kStartY = 90
kMaxM = 120
def can_reach_zero(x, y, r_rem, s_rem):
pow2_s = 1 << s_rem
pow2_r = 1 << r_rem
min_diff = x * pow2_s + r_rem - (y * pow2_r + s_rem * pow2_r)
max_diff = x * pow2_s + r_rem * pow2_s - (y * pow2_r + s_rem)
return min_diff <= 0 and max_diff >= 0
class SearchSolver:
def __init__(self, r_target, s_target):
self.R = r_target
self.S = s_target
self.memo = {}
def count_paths(self, x, y, r_used, s_used):
if r_used == self.R and s_used == self.S:
return 1 if x == y else 0
if x == y:
return 0
r_rem = self.R - r_used
s_rem = self.S - s_used
if not can_reach_zero(x, y, r_rem, s_rem):
return 0
key = (x, y, r_used, s_used)
if key in self.memo:
return self.memo[key]
total = 0
if r_used < self.R:
total += self.count_paths(x + 1, y * 2, r_used + 1, s_used)
total = min(2, total)
if s_used < self.S and total < 2:
total += self.count_paths(x * 2, y + 1, r_used, s_used + 1)
total = min(2, total)
self.memo[key] = total
return total
def reconstruct_one_path(self):
path = []
x = kStartX
y = kStartY
r_used = 0
s_used = 0
while r_used < self.R or s_used < self.S:
moved = False
if r_used < self.R and self.count_paths(x + 1, y * 2, r_used + 1, s_used) > 0:
path.append('r')
x += 1
y *= 2
r_used += 1
moved = True
elif s_used < self.S and self.count_paths(x * 2, y + 1, r_used, s_used + 1) > 0:
path.append('s')
x *= 2
y += 1
s_used += 1
moved = True
if not moved:
return None
return "".join(path)
def apply_path_and_final_value(path):
x = kStartX
y = kStartY
for i, char in enumerate(path):
if char == 'r':
x += 1
y *= 2
else:
x *= 2
y += 1
if i + 1 < len(path) and x == y:
return 0
return x if x == y else 0
def solve():
for m in range(0, kMaxM + 1, 2):
found = False
best_count = 0
best_final_value = 0
for r_target in range(m + 1):
s_target = m - r_target
solver = SearchSolver(r_target, s_target)
c = solver.count_paths(kStartX, kStartY, 0, 0)
if c == 0:
continue
path = solver.reconstruct_one_path()
if not path:
continue
final_value = apply_path_and_final_value(path)
if final_value == 0:
continue
if not found:
found = True
best_count = c
best_final_value = final_value
else:
best_count = 2
if found:
if best_count == 1:
return str(best_final_value)
return None
if __name__ == "__main__":
print(solve())
Java
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
public class Euler736 {
static final BigInteger START_X = BigInteger.valueOf(45);
static final BigInteger START_Y = BigInteger.valueOf(90);
static final int MAX_M = 120;
static boolean canReachZero(BigInteger x, BigInteger y, int rRem, int sRem) {
BigInteger pow2S = BigInteger.ONE.shiftLeft(sRem);
BigInteger pow2R = BigInteger.ONE.shiftLeft(rRem);
BigInteger term1 = x.multiply(pow2S);
BigInteger term2 = BigInteger.valueOf(rRem);
BigInteger term3 = y.multiply(pow2R);
BigInteger term4 = BigInteger.valueOf(sRem).multiply(pow2R);
BigInteger minDiff = term1.add(term2).subtract(term3).subtract(term4);
BigInteger term2Max = BigInteger.valueOf(rRem).multiply(pow2S);
BigInteger term4Max = BigInteger.valueOf(sRem);
BigInteger maxDiff = term1.add(term2Max).subtract(term3).subtract(term4Max);
return minDiff.compareTo(BigInteger.ZERO) <= 0 && maxDiff.compareTo(BigInteger.ZERO) >= 0;
}
static class StateKey {
BigInteger x, y;
int r, s;
StateKey(BigInteger x, BigInteger y, int r, int s) {
this.x = x;
this.y = y;
this.r = r;
this.s = s;
}
@Override
public boolean equals(Object o) {
if (this == o)
return true;
if (o == null || getClass() != o.getClass())
return false;
StateKey stateKey = (StateKey) o;
return r == stateKey.r && s == stateKey.s && x.equals(stateKey.x) && y.equals(stateKey.y);
}
@Override
public int hashCode() {
return Objects.hash(x, y, r, s);
}
}
static class SearchSolver {
int R, S;
Map<StateKey, Integer> memo;
SearchSolver(int rTarget, int sTarget) {
this.R = rTarget;
this.S = sTarget;
this.memo = new HashMap<>();
}
int countPaths(BigInteger x, BigInteger y, int rUsed, int sUsed) {
if (rUsed == R && sUsed == S) {
return x.equals(y) ? 1 : 0;
}
if (x.equals(y)) {
return 0;
}
int rRem = R - rUsed;
int sRem = S - sUsed;
if (!canReachZero(x, y, rRem, sRem)) {
return 0;
}
StateKey key = new StateKey(x, y, rUsed, sUsed);
Integer cached = memo.get(key);
if (cached != null)
return cached;
int total = 0;
if (rUsed < R) {
total += countPaths(x.add(BigInteger.ONE), y.shiftLeft(1), rUsed + 1, sUsed);
if (total > 2)
total = 2;
}
if (sUsed < S && total < 2) {
total += countPaths(x.shiftLeft(1), y.add(BigInteger.ONE), rUsed, sUsed + 1);
if (total > 2)
total = 2;
}
memo.put(key, total);
return total;
}
String reconstructOnePath() {
StringBuilder path = new StringBuilder();
BigInteger x = START_X;
BigInteger y = START_Y;
int rUsed = 0;
int sUsed = 0;
while (rUsed < R || sUsed < S) {
boolean moved = false;
if (rUsed < R && countPaths(x.add(BigInteger.ONE), y.shiftLeft(1), rUsed + 1, sUsed) > 0) {
path.append('r');
x = x.add(BigInteger.ONE);
y = y.shiftLeft(1);
rUsed++;
moved = true;
} else if (sUsed < S && countPaths(x.shiftLeft(1), y.add(BigInteger.ONE), rUsed, sUsed + 1) > 0) {
path.append('s');
x = x.shiftLeft(1);
y = y.add(BigInteger.ONE);
sUsed++;
moved = true;
}
if (!moved)
return null;
}
return path.toString();
}
}
static BigInteger applyPathAndFinalValue(String path) {
BigInteger x = START_X;
BigInteger y = START_Y;
for (int i = 0; i < path.length(); ++i) {
if (path.charAt(i) == 'r') {
x = x.add(BigInteger.ONE);
y = y.shiftLeft(1);
} else {
x = x.shiftLeft(1);
y = y.add(BigInteger.ONE);
}
if (i + 1 < path.length() && x.equals(y)) {
return BigInteger.ZERO;
}
}
return x.equals(y) ? x : BigInteger.ZERO;
}
public static String solve() {
for (int m = 0; m <= MAX_M; m += 2) {
boolean found = false;
int bestCount = 0;
BigInteger bestFinalValue = BigInteger.ZERO;
for (int rTarget = 0; rTarget <= m; ++rTarget) {
int sTarget = m - rTarget;
SearchSolver solver = new SearchSolver(rTarget, sTarget);
int c = solver.countPaths(START_X, START_Y, 0, 0);
if (c == 0)
continue;
String path = solver.reconstructOnePath();
if (path == null)
continue;
BigInteger finalValue = applyPathAndFinalValue(path);
if (finalValue.equals(BigInteger.ZERO))
continue;
if (!found) {
found = true;
bestCount = c;
bestFinalValue = finalValue;
} else {
bestCount = 2;
}
}
if (found) {
if (bestCount == 1) {
return bestFinalValue.toString();
}
}
}
return null;
}
public static void main(String[] args) {
System.out.println(solve());
}
}