Problem Summary

A modified Collatz process uses three step types \(D,U,d\), chosen by the current value modulo \(3\). For a given long step string and a large lower bound \(L\), we want the smallest starting value \(n>L\) whose trajectory begins with exactly that prescribed prefix. Whatever happens after the prefix is irrelevant.

Mathematical Approach

Let the prescribed prefix be \(s_1s_2\cdots s_m\), where each \(s_i\in\{D,U,d\}\).

1) Forward rules and why brute force is hopeless

The process is deterministic once the residue class modulo \(3\) is known:

$$D:\ x\equiv0\pmod3,\qquad x\mapsto \frac{x}{3},$$

$$U:\ x\equiv1\pmod3,\qquad x\mapsto \frac{4x+2}{3},$$

$$d:\ x\equiv2\pmod3,\qquad x\mapsto \frac{2x-1}{3}.$$

The lower bound in the actual problem is around \(10^{15}\), so testing consecutive starting values forward is not realistic. The correct idea is to reverse the prefix and describe all valid starts in one shot.

2) Inverting a single step

If \(y\) is the value after one step, then the previous value \(x\) must satisfy:

$$D^{-1}:\ x=3y,$$

$$U^{-1}:\ y=\frac{4x+2}{3}\Longrightarrow x=\frac{3y-2}{4},$$

$$d^{-1}:\ y=\frac{2x-1}{3}\Longrightarrow x=\frac{3y+1}{2}.$$

So every reverse step is an affine rational map.

3) Why the reverse formulas already enforce the correct residue class

At first sight, one might worry that the reverse maps only guarantee integrality, not the required modulo \(3\) condition. In fact integrality is enough:

If \(x=(3y-2)/4\in\mathbb Z\), then \(4x+2\) is divisible by \(3\). Since \(4\equiv1\pmod3\), this gives

$$x+2\equiv0\pmod3\Longrightarrow x\equiv1\pmod3.$$

Likewise, if \(x=(3y+1)/2\in\mathbb Z\), then \(2x-1\) is divisible by \(3\). Because \(2\equiv-1\pmod3\),

$$-x-1\equiv0\pmod3\Longrightarrow x\equiv2\pmod3.$$

So once the reverse step yields an integer, it is automatically a valid predecessor for the intended letter.

4) Reverse-composing the whole prefix gives one affine formula

Let \(t\) be the value obtained after the entire prescribed prefix has been executed. Running the prefix backward reconstructs the starting value \(n\). Because each reverse step is affine-rational, the full composition has the shape

$$n=\frac{At+B}{C}$$

for some integers \(A,B,C\) depending only on the prefix.

This is the central structural fact: the infinitely many valid starts are parameterized by a single integer \(t\).

5) Coefficient updates used by the code

Suppose the current reverse formula is

$$x=\frac{At+B}{C}.$$

If the next reverse step is \(D\), then

$$x\mapsto 3x=\frac{3At+3B}{C},$$

so

$$A\leftarrow3A,\qquad B\leftarrow3B,\qquad C\leftarrow C.$$

If the next reverse step is \(U\), then

$$x\mapsto \frac{3x-2}{4}=\frac{3(At+B)-2C}{4C},$$

so

$$A\leftarrow3A,\qquad B\leftarrow3B-2C,\qquad C\leftarrow4C.$$

If the next reverse step is \(d\), then

$$x\mapsto \frac{3x+1}{2}=\frac{3(At+B)+C}{2C},$$

so

$$A\leftarrow3A,\qquad B\leftarrow3B+C,\qquad C\leftarrow2C.$$

The implementation starts from the identity map \(n=t\), that is

$$A=1,\qquad B=0,\qquad C=1,$$

and scans the prefix from right to left.

6) Closed form for \(A\) and \(C\)

Every reverse step multiplies \(A\) by \(3\), so after a prefix of length \(m\),

$$A=3^m.$$

The denominator changes only for \(U\) and \(d\): \(U\) multiplies \(C\) by \(4=2^2\), and \(d\) multiplies \(C\) by \(2\). Therefore

$$C=2^{\,2\#U+\#d}.$$

In particular,

$$\gcd(A,C)=1.$$

This is why the congruence step in this problem is especially clean.

7) Integrality becomes a linear congruence

We need \(n=(At+B)/C\) to be an integer, so

$$At+B\equiv0\pmod C.$$

In a completely general affine-rational problem one would first set

$$g=\gcd(A,C),$$

check that \(g\mid B\), and reduce the congruence to

$$\frac{A}{g}t\equiv-\frac{B}{g}\pmod{\frac{C}{g}}.$$

The code keeps exactly this generic gcd-based path. But here \(g=1\), so there is always a unique residue class modulo \(C\):

$$t\equiv -B\,A^{-1}\pmod C.$$

Thus all valid \(t\) are of the form

$$t=t_0+kC,\qquad k\in\mathbb Z,$$

where \(t_0\) is the least nonnegative solution of the congruence.

8) The starting values themselves form an arithmetic progression

Substitute \(t=t_0+kC\) into \(n=(At+B)/C\):

$$n=\frac{At_0+B}{C}+kA=n_0+kA.$$

So the valid starting values are not scattered randomly; they form one arithmetic progression with step size \(A\).

This is the decisive optimization. Instead of checking many candidates, we compute one base solution \(n_0\) and jump directly by multiples of \(A\).

9) Choosing the smallest solution above the lower bound

Suppose the progression is

$$n=n_0+kA,\qquad k\ge0.$$

If \(n_0>L\), then the answer is simply \(n_0\). Otherwise we need the least integer \(k\) such that

$$n_0+kA>L.$$

This gives

$$k=\left\lfloor\frac{L-n_0}{A}\right\rfloor+1.$$

The code also makes one extra positivity adjustment on \(t\), because the least residue-class representative \(t_0\) can be \(0\). Replacing \(t\) by \(t+C\) increases \(n\) by \(A\), so this adjustment is perfectly consistent with the same arithmetic progression.

10) Worked example: prefix \(UD\)

Process the prefix backward.

First invert \(D\):

$$y\mapsto 3y.$$

Then invert \(U\):

$$n=\frac{3(3t)-2}{4}=\frac{9t-2}{4}.$$

Integrality requires

$$9t-2\equiv0\pmod4.$$

Since \(9\equiv1\pmod4\), this is

$$t\equiv2\pmod4.$$

The smallest positive choice is \(t=2\), giving

$$n=\frac{18-2}{4}=4.$$

Check the prefix forward:

$$4\xrightarrow{U}6\xrightarrow{D}2.$$

So \(4\) is indeed the smallest starting value whose trajectory begins with \(UD\).

11) Sample checkpoint from the source code

The program validates the sample sequence

$$\texttt{DdDddUUdDD}$$

with lower bound \(10^6\). The computed answer is

$$1004064.$$

Then the helper follows_prefix() runs the process forward and confirms that this value really starts with the required prefix. This is a strong end-to-end validation of the affine-congruence method.

How the Code Works

1) Parsing. The solver accepts --sequence=..., --lower-bound=..., and --skip-checkpoints.

2) Backward coefficient build. solve() scans the string from right to left and updates \((A,B,C)\) with the three formulas above.

3) Generic congruence solve. Even though this problem always has \(\gcd(A,C)=1\), the implementation still computes \(g=\gcd(A,C)\), reduces the congruence, and uses mod_inverse(). This makes the code robust and mathematically transparent.

4) Progression jump. Once it has one base solution, the code computes the least term above the lower bound without scanning any intermediate starts.

5) Integer safety. Intermediate affine coefficients are stored in __int128, because the prefix is long enough that ordinary 64-bit arithmetic would be risky during composition.

Complexity Analysis

If the prefix length is \(m\), building \((A,B,C)\) is \(O(m)\). Solving the modular inverse is \(O(\log C)\), and jumping to the first term above the lower bound is constant time. So the total runtime is linear in the prefix length, with \(O(1)\) memory.

Further Reading

1. Problem page: https://projecteuler.net/problem=277
2. Modular arithmetic and linear congruences: https://en.wikipedia.org/wiki/Modular_arithmetic
3. Extended Euclidean algorithm: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm