Problem 277: A Modified Collatz Sequence

Project Euler Problem 277 Solution

EulerSolve provides an optimized solution for Project Euler Problem 277, A Modified Collatz Sequence, with C++, Python, Java, and a step-by-step mathematical explanation.

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

Detailed mathematical approach

Problem Summary

A sequence of integers starts from a value $a_1$, and every value chooses its step by its remainder on division by $3$. If $3$ divides $a_n$, the large downward step $\mathtt D$ gives $a_{n+1}=a_n/3$; if the remainder is $1$, the upward step $\mathtt U$ gives $a_{n+1}=(4a_n+2)/3$; if it is $2$, the small downward step $\mathtt d$ gives $a_{n+1}=(2a_n-1)/3$. The sequence stops as soon as some $a_n=1$, and the letters of the steps taken form its step word. For $a_1=231$ the values are $231,77,51,17,11,7,10,14,9,3,1$, so the step word is $\mathtt{DdDddUUdDD}$. The step word of $1004064$ has $29$ letters and begins with the same ten, and $1004064$ is the smallest $a_1\gt10^6$ with this property. We must find the smallest $a_1\gt10^{15}$ whose step word begins with the $30$ letters UDDDUdddDDUDDddDdDddDDUDDdUUDd; what the sequence does after these $30$ steps does not matter. ^[1]

The whole solution in one sentence: the starts whose first $30$ steps follow the given word are exactly the numbers with one particular remainder on division by $3^{30}$, running the word backwards from its unknown last value reveals this remainder, and the answer is the first number above $10^{15}$ that has it.

Mathematical Approach

Small cases show that every word of $m$ letters belongs to one remainder modulo $3^m$; we prove this and then compute the remainder by running the word backwards, as the programs do.

1. One step, written with the quotient

Write the current value as $a=3q+r$ with remainder $r\in\{0,1,2\}$. The three rules then read:

$\mathtt D$: $a=3q$ goes to $q$;
$\mathtt U$: $a=3q+1$ goes to $(4a+2)/3=4q+2$;
$\mathtt d$: $a=3q+2$ goes to $(2a-1)/3=2q+1$.

So every step produces an integer again, and the step taken is decided by the last digit of $a$ in base $3$; for example $77=3\cdot25+2$ takes $\mathtt d$ to $2\cdot25+1=51$. Maps with one affine formula per remainder class are called generalized Collatz functions; the Collatz map in its shortcut form, $n/2$ for even $n$ and $(3n+1)/2$ for odd $n$, is the case of remainders modulo $2$. ^[2] ^[3]

For a positive value, a step divides by at most $3$: $\mathtt D$ divides by exactly $3$, $\mathtt U$ enlarges the value, and $(2a-1)/3\ge a/3$ for $a\ge1$. Hence $a_{n+1}\ge a_n/3$, and all values stay positive. The value $1$ would take $\mathtt U$ to $2$, and $2$ takes $\mathtt d$ back to $1$; this loop is why the sequence is stopped at $1$.

2. Two steps and nine remainders

Until Section 10 we keep applying the rules after a value $1$ as well; Section 10 shows that this cannot change the answer. The first letter is decided by the remainder of $a_1$ modulo $3$; two letters need the remainder modulo $9$. For example, if $a_1=9j+4=3(3j+1)+1$, the first step is $\mathtt U$ and gives $4(3j+1)+2=12j+6$, a multiple of $3$, so the second step is $\mathtt D$. All nine remainders give:

remainders $0,3,6$ modulo $9$: $\mathtt{DD}$, $\mathtt{DU}$, $\mathtt{Dd}$;
remainders $1,4,7$ modulo $9$: $\mathtt{Ud}$, $\mathtt{UD}$, $\mathtt{UU}$;
remainders $2,5,8$ modulo $9$: $\mathtt{dU}$, $\mathtt{dD}$, $\mathtt{dd}$.

Each of the nine two-letter words appears exactly once.

3. Every word belongs to one remainder

The rules make sense for every integer, positive or not, so we state the pattern for all integers. We write $x\equiv y\pmod M$ when $M$ divides $x-y$, that is, when $x$ and $y$ leave the same remainder on division by $M$; the integers with one fixed remainder form a residue class modulo $M$, such as the class $\dots,-5,4,13,22,\dots$ of $4$ modulo $9$.

Claim. For every word $w$ of $m$ letters, the integers whose first $m$ steps spell $w$ form exactly one residue class modulo $3^m$.

Proof by induction on $m$. For $m=0$ the empty word belongs to all integers, one class modulo $1$. Let $w$ be a letter $s$ followed by a word $w'$ of $m-1$ letters, whose integers form, by the induction hypothesis, one class $c$ modulo $3^{m-1}$. An integer spells $w$ exactly when it is $3q+r$ with the remainder $r$ of $s$ and its next value spells $w'$. By Section 1 that next value is $\alpha q+\beta$ with $(\alpha,\beta)=(1,0)$, $(4,2)$ or $(2,1)$, so the condition is

$$\alpha q+\beta\equiv c\pmod{3^{m-1}}.$$

As $\alpha$ has no factor $3$, it has an inverse $\alpha'$ modulo $3^{m-1}$, with $\alpha\alpha'\equiv1$. ^[4] Multiplying by $\alpha'$ shows that the condition holds exactly for the $q$ in one class modulo $3^{m-1}$, and then $3q+r$ runs through one class modulo $3^m$. Since an integer has only one step word, different words have disjoint classes, and as there are $3^m$ words and $3^m$ classes, every class belongs to exactly one word.

This is the analogue of a classical fact about the shortcut Collatz map of Section 1: two integers have the same parities in their first $k$ values exactly when they are congruent modulo $2^k$. ^[2] For our word the starts are therefore $r$, $r+3^{30}$, $r+2\cdot3^{30}$, … for one $0\le r\lt3^{30}$; testing numbers above $10^{15}$ one by one could take $3^{30}\approx2.06\cdot10^{14}$ tests. The proof could find $r$ digit by digit; the programs run the word backwards instead.

4. Running a step backwards

If a step takes $x$ to $y$, the letter and $y$ determine $x$:

$\mathtt D$: $x=3y$;
$\mathtt U$: $x=(3y-2)/4$;
$\mathtt d$: $x=(3y+1)/2$.

Going back by $\mathtt U$ or $\mathtt d$ works only when the result is an integer: from $y=1$, $\mathtt U$ would give $1/4$, while $\mathtt d$ gives $2$.

5. The whole word backwards

Let $t=a_{m+1}$ be the value after the last letter. Running the word backwards expresses every earlier value as a fraction $(At+B)/C$ with integers $A$, $B$, $C$. We start with $t$ itself, $(A,B,C)=(1,0,1)$, and each letter, read from right to left, replaces the current fraction $x=(At+B)/C$ by the value before it:

$\mathtt D$: $3x=(3At+3B)/C$, so $(A,B,C)$ becomes $(3A,3B,C)$;
$\mathtt U$: $(3x-2)/4$${}=(3At+3B-2C)/(4C)$, so it becomes $(3A,3B-2C,4C)$;
$\mathtt d$: $(3x+1)/2$${}=(3At+3B+C)/(2C)$, so it becomes $(3A,3B+C,2C)$.

After the first letter the fraction is the start:

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

Every letter multiplies $A$ by $3$; each $\mathtt U$ multiplies $C$ by $4$ and each $\mathtt d$ by $2$. If the word has $u$ letters $\mathtt U$ and $v$ letters $\mathtt d$, then $A=3^m$ and $C=2^{2u+v}$, so $\gcd(A,C)=1$. For the word $\mathtt{UD}$, the letter $\mathtt D$ gives $(3,0,1)$, then $\mathtt U$ gives $(9,-2,4)$, and $a_1=(9t-2)/4$.

6. One integrality condition is enough

Every value along the way, not only $a_1$, must be an integer with the remainder its letter demands. Both requirements follow from the integrality of $a_1$ alone.

Claim. If $t\ge1$ and $a_1=(At+B)/C$ are integers, then the first $m$ steps of $a_1$ spell the word and lead to $t$. Conversely, every start whose first $m$ steps spell the word arises in this way from its own $t=a_{m+1}\ge1$.

Proof. Let $x_{m+1}=t$ and $x_m,\dots,x_1=a_1$ be the values given by the backward formulas. These divide only by $2$ or $4$, so every $x_j$ is an integer divided by a power of $2$. Read forwards from the integer $x_1$, the formula of each letter divides only by $3$, so every $x_j$ is also an integer divided by a power of $3$. Its reduced denominator divides both powers and is therefore $1$: every $x_j$ is an integer. If $(4x_j+2)/3$ is an integer, then $3$ divides $4x_j+2$, which is congruent to $x_j+2$ modulo $3$, so $x_j\equiv1\pmod3$ and the step from $x_j$ really is $\mathtt U$. Likewise $(2x_j-1)/3\in\mathbb Z$ forces $x_j\equiv2$, and $x_j/3\in\mathbb Z$ forces $x_j\equiv0$. A positive integer $y$ gives a positive $x$ in all three backward formulas, as $(3y-2)/4\ge1/4$, so all $x_j$ are positive. The converse is Section 5 applied to the actual values.

7. Solving the congruence

By Section 6 we need the integers $t\ge1$ with

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

Since $\gcd(A,C)=1$, $A$ has an inverse $A'$ modulo $C$, which the extended Euclidean algorithm finds. ^[4] ^[5] Multiplying by $A'$ shows that the congruence holds exactly when $t\equiv t_0\pmod C$, where $t_0$ is the remainder of $-BA'$ modulo $C$, so $0\le t_0\lt C$. Substituting $t=t_0+kC$ gives

$$a_1=\frac{A(t_0+kC)+B}{C}=n_0+kA,$$

with $n_0=(At_0+B)/C$. The starts form an arithmetic progression with difference $A=3^m$, in agreement with Section 3. For $\mathtt{UD}$, $9t-2\equiv0\pmod4$ means $t\equiv2\pmod4$, because $9\equiv1$; so $t_0=2$ and the starts are $4,13,22,\dots$, the remainder $4$ modulo $9$ of Section 2. Indeed $4$ goes to $6$ and then to $2$.

8. Worked example: $\mathtt{DdDddUUdDD}$

Read from right to left, the letters of the statement's word are $\mathtt D,\mathtt D,\mathtt d,\mathtt U,\mathtt U,\mathtt d,\mathtt d,\mathtt D,\mathtt d,\mathtt D$, and the rules of Section 5 turn $(A,B,C)=(1,0,1)$ successively into $(3,0,1)$, $(9,0,1)$, $(27,1,2)$, $(81,-1,8)$, $(243,-19,32)$, $(729,-25,64)$, $(2187,-11,128)$, $(6561,-33,128)$, $(19683,29,256)$ and $(59049,87,256)$. At $t=1$ these fractions are $3,9,14,10,7,11,17,51,77,231$, the sequence of $231$ read backwards, which checks every triple. Hence $a_1=(59049t+87)/256$. Modulo $256$, $59049\equiv169$ and $-87\equiv169$, so the congruence reads $169t\equiv169\pmod{256}$.

The extended Euclidean algorithm divides with remainder, starting from $256$ and $169$, and produces the remainders $256,169,87,82,5,2,1$. It attaches the multiplier $0$ to $256$ and $1$ to $169$, and whenever a division has quotient $q$, it forms the next multiplier from the last two in the same way as the next remainder: $82=16\cdot5+2$, for example, turns the multipliers $2$ and $-3$ of $82$ and $5$ into $2-16\cdot(-3)=50$. This keeps every remainder congruent to $169$ times its multiplier modulo $256$ and gives the multipliers $0,1,-1,2,-3,50,-103$. The last pair gives $169\cdot(-103)\equiv1$, so $A'=-103+256=153$; indeed $169\cdot153=25857=101\cdot256+1$. Then $t_0=169\cdot153\bmod256=1$ and $n_0=(59049+87)/256=231$: the starts are $231+59049k$, with $t=1+256k$.

Above $10^6$ the first one has $k=\lfloor(10^6-231)/59049\rfloor+1=17$, which gives $231+17\cdot59049=1004064$ and $t=1+17\cdot256=4353$. The sequence of $1004064$ indeed passes through $334688$, $223125$, $74375$, $49583$, $33055$, $44074$, $58766$, $39177$ and $13059$ and reaches $4353$ after ten steps.

9. The smallest start above the bound

For a bound $L$ we need the least $k$ with $n_0+kA\gt L$ and $t_0+kC\ge1$. Since $0\le t_0\lt C$, the second condition forces $k\ge0$ and fails at $k=0$ only when $t_0=0$. Both expressions grow with $k$, so the least $k$ satisfying both conditions is the larger of the two separate least values. If $n_0\gt L$, the first condition holds for $k=0$; otherwise its least value is

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

10. The stop at 1 cannot interfere

A start qualifies only if none of $a_1,\dots,a_m$, the values that still have to make a step, equals $1$. By Section 1, $a_j\ge a_1/3^{j-1}$, so for $a_1\gt10^{15}$ and $j\le30$ we get $a_j\gt10^{15}/3^{29}\approx14.6$. In general, a start that meets $1$ among its first $m$ values is at most $3^{m-1}$, so the backward method is exact whenever $L\ge3^{m-1}$; here $3^{29}\approx6.9\cdot10^{13}$ is far below $10^{15}$. For tiny bounds the rule matters: for the word $\mathtt U$ and $L=0$ the backward method gives $a_1=1$, whose sequence stops before its first step, while the true answer is $4$.

11. The word of the problem

The word UDDDUdddDDUDDddDdDddDDUDDdUUDd has $m=30$ letters: $u=6$ letters $\mathtt U$, $v=10$ letters $\mathtt d$ and $14$ letters $\mathtt D$. Hence $A=3^{30}=205891132094649$, about $2.06\cdot10^{14}$, and $C=2^{22}=4194304$. Every block of $3^{30}$ consecutive integers contains exactly one start, so the answer lies between $10^{15}+1$ and $10^{15}+3^{30}$. The numerator $At+B=Ca_1$ exceeds $2^{22}\cdot10^{15}\approx4.2\cdot10^{21}$, far beyond the largest signed 64-bit integer, about $9.2\cdot10^{18}$.

How the Code Works

The C++ program ^[6] keeps the word and the bound in an Options structure, by default those of the problem. parse_arguments accepts --sequence=, --lower-bound= and --skip-checkpoints and rejects malformed arguments and letters other than D, U and d; it does not check whether a bound fits into 64 bits, which $10^{15}$ does. Unless skipped, run_checkpoints first solves the example of the statement, requires $1004064$ for $\mathtt{DdDddUUdDD}$ and the bound $10^6$, and lets follows_prefix replay the ten steps from that value; a failure ends the program with exit code $2$.

solve carries out Sections 5 to 9. It runs through the word from right to left with the updates of Section 5, holding $A$, $B$, $C$ in the signed 128-bit type __int128_t, a GCC and Clang extension; ^[7] 128 bits are needed at the end, where $At+B$ exceeds $4.2\cdot10^{21}$. It converts $A$ and $C$ to 64 bits, which is exact while $3^m$ and $2^{2u+v}$ stay below $2^{63}$, computes $g=\gcd(A,C)$ with gcd_i64 and divides the congruence by $g$, a general safeguard that changes nothing here, since $g=1$. mod_inverse is the extended Euclidean algorithm of Section 8 with the remainders r, new_r and the multipliers t, new_t; it returns $-1$ if the last nonzero remainder is not $1$, and otherwise the multiplier reduced to the range $0$ to $C-1$. Then solve forms $t_0$ and $n_0$, chooses $k$ as in Section 9 with the steps n_step $=A$ and t_step $=C$, first from the bound and then, if needed, from $t\ge1$, and returns $(At+B)/C$, which i128_to_string turns into decimal digits for main to print.

The Python solve does the same arithmetic, with the problem's word and bound as default arguments, and returns a decimal string; its integers have no fixed size, and it takes the inverse from the built-in pow(a_mod, -1, mod), available since Python 3.8. ^[8] The Java version uses BigInteger throughout, with gcd, mod and modInverse. ^[9] Neither port runs the checkpoint; both print the result for the problem's word and bound.

Complexity and Verification

For a word of $m$ letters the backward pass makes $m$ updates of a few arithmetic operations each. The extended Euclidean algorithm needs at most five times as many division steps as the smaller number has decimal digits, ^[10] here at most $35$, since $A\bmod C\lt2^{22}$ has at most seven digits; it actually takes $12$ steps for the problem's word and $6$ in Section 8. In total the method takes $O(m)$ arithmetic operations on integers of $O(m+\log L)$ bits and stores only a handful of them, so the answer appears at once.

The C++ program checks itself on the example of the statement, and all three programs print the same number. These further checks were run for this article and are not part of the published solutions:

For every $m\le8$, the first $m$ letters of every integer from $0$ to $3^{m+1}-1$ depend only on its remainder modulo $3^m$, and all $3^m$ words occur.
For all $1092$ words of one to six letters and the bounds $L=0,1,2,5,10,100,1000,12345$, the Python solve agrees in all $8736$ cases with a search that tests $L+1,L+2,\dots$ while ignoring the stop at $1$; a search that respects the stop differs in $349$ cases, all with results of at most $3^{m-1}$ that meet $1$ inside the word.
C++ and Python agree on $400$ random words of up to $30$ letters with bounds up to $10^{17}$, Java and Python on $500$ random words of up to $45$ letters.
For the problem's word, the remainder modulo $3^{30}$ was also built forward, one base-$3$ digit at a time as in Section 3. It gives the same answer, whose sequence follows all $30$ letters without meeting $1$, and the answer minus $3^{30}$ is at most $10^{15}$.

Footnotes and References

The references below supply the background facts used above. The description of the starts by one remainder modulo $3^m$, the integrality argument for the backward formula and the bound that makes the stop at $1$ harmless are derived in this article.

Project Euler 277 — A Modified Collatz Sequence. The official statement defines the steps D, U and d, stops the sequence at 1, gives the steps DdDddUUdDD of 231 and names 1004064 as the smallest start above 10⁶ whose steps begin with them, and asks for the smallest start above 10¹⁵ whose steps begin with UDDDUdddDDUDDddDdDddDDUDDdUUDd.
Wikipedia — Collatz conjecture. Its section on parity sequences uses the map n/2 for even n and (3n + 1)/2 for odd n and states, citing Terras and Lagarias, that the parity sequences of two numbers agree in their first k terms if and only if the numbers are congruent modulo 2ᵏ.
J. C. Lagarias — The 3x+1 Problem: An Overview (arXiv:2111.02635). Section 4 treats maps f(x) = (aᵢx + bᵢ)/d for x ≡ i (mod d), which send integers to integers exactly when i·aᵢ + bᵢ ≡ 0 (mod d). Our map is such a map with d = 3 and the pairs (1, 0), (4, 2) and (2, −1).
Wikipedia — Modular multiplicative inverse. An inverse of a modulo m exists if and only if gcd(a, m) = 1, it is then unique modulo m, and the extended Euclidean algorithm finds it.
Wikipedia — Extended Euclidean algorithm. Besides the greatest common divisor, the algorithm computes Bézout coefficients; its routine for modular inverses, with the variables t, newt, r and newr, is the scheme of mod_inverse.
C++ — Euler277.cpp. The linked immutable C++ revision contains solve, mod_inverse, follows_prefix and run_checkpoints. It is the implementation record for this article.
GCC manual — 128-bit Integers. GCC supports the extension types __int128 and unsigned __int128 on targets with a 128-bit integer mode.
Python documentation — pow. Since Python 3.8, pow(base, exp, mod) accepts a negative exponent when base is relatively prime to mod, so pow(a, −1, m) is an inverse of a modulo m.
Java documentation — BigInteger. Arbitrary-precision integers; mod never returns a negative result, and modInverse throws an ArithmeticException when no inverse exists.
Wikipedia — Euclidean algorithm. By Lamé's theorem of 1844, the algorithm never needs more steps than five times the number of decimal digits of the smaller number.

Problem 277 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>

namespace {

using i64 = long long;
using i128 = __int128_t;

struct Options {
    std::string sequence = "UDDDUdddDDUDDddDdDddDDUDDdUUDd";
    i64 lower_bound = 1000000000000000LL;
    bool run_checkpoints = true;
};

bool parse_i64_after_prefix(const std::string& arg, const std::string& prefix, i64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    i64 parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<i64>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_string_after_prefix(const std::string& arg, const std::string& prefix, std::string& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    value = arg.substr(prefix.size());
    return !value.empty();
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_i64_after_prefix(arg, "--lower-bound=", options.lower_bound) ||
            parse_string_after_prefix(arg, "--sequence=", options.sequence)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    if (options.lower_bound < 0) {
        return false;
    }
    for (char c : options.sequence) {
        if (c != 'U' && c != 'D' && c != 'd') {
            return false;
        }
    }
    return true;
}

i64 gcd_i64(i64 a, i64 b) {
    while (b != 0) {
        const i64 t = a % b;
        a = b;
        b = t;
    }
    return a >= 0 ? a : -a;
}

i64 mod_inverse(i64 a, i64 mod) {
    i64 t = 0;
    i64 new_t = 1;
    i64 r = mod;
    i64 new_r = a;

    while (new_r != 0) {
        const i64 q = r / new_r;
        const i64 next_t = t - q * new_t;
        t = new_t;
        new_t = next_t;

        const i64 next_r = r - q * new_r;
        r = new_r;
        new_r = next_r;
    }

    if (r != 1) {
        return -1;
    }

    t %= mod;
    if (t < 0) {
        t += mod;
    }
    return t;
}

i128 solve(const std::string& sequence, const i128 lower_bound) {
    i128 A = 1;
    i128 B = 0;
    i128 C = 1;

    for (int i = static_cast<int>(sequence.size()) - 1; i >= 0; --i) {
        const char step = sequence[static_cast<std::size_t>(i)];
        if (step == 'D') {
            A = 3 * A;
            B = 3 * B;
        } else if (step == 'U') {
            A = 3 * A;
            B = 3 * B - 2 * C;
            C = 4 * C;
        } else {
            A = 3 * A;
            B = 3 * B + C;
            C = 2 * C;
        }
    }

    const i64 a64 = static_cast<i64>(A);
    const i64 c64 = static_cast<i64>(C);
    const i64 g = gcd_i64(a64, c64);

    const i64 mod = c64 / g;
    const i64 a_reduced = a64 / g;

    const i64 a_mod = (a_reduced % mod + mod) % mod;
    const i64 inv = mod_inverse(a_mod, mod);
    if (inv < 0) {
        return -1;
    }

    const i128 B_reduced = B / g;
    const i64 rhs = static_cast<i64>(((-B_reduced) % mod + mod) % mod);
    const i64 t0 = static_cast<i64>((static_cast<i128>(rhs) * inv) % mod);

    const i128 n0 = (A * static_cast<i128>(t0) + B) / C;
    const i128 n_step = A / g;
    const i128 t_step = mod;

    i128 k = 0;
    if (n0 <= lower_bound) {
        k = (lower_bound - n0) / n_step + 1;
    }

    const i128 t_min = static_cast<i128>(t0) + k * t_step;
    if (t_min <= 0) {
        const i128 add = (-t_min) / t_step + 1;
        k += add;
    }

    const i128 t = static_cast<i128>(t0) + k * t_step;
    return (A * t + B) / C;
}

bool follows_prefix(i128 value, const std::string& sequence) {
    for (char c : sequence) {
        const int mod3 = static_cast<int>(value % 3);
        if (c == 'D') {
            if (mod3 != 0) {
                return false;
            }
            value /= 3;
        } else if (c == 'U') {
            if (mod3 != 1) {
                return false;
            }
            value = (4 * value + 2) / 3;
        } else {
            if (mod3 != 2) {
                return false;
            }
            value = (2 * value - 1) / 3;
        }
    }
    return true;
}

bool run_checkpoints() {
    const std::string sample_seq = "DdDddUUdDD";
    const i128 sample = solve(sample_seq, 1000000);
    if (sample != 1004064) {
        std::cerr << "Checkpoint failed for sample sequence" << '\n';
        return false;
    }
    if (!follows_prefix(sample, sample_seq)) {
        std::cerr << "Checkpoint failed for sample prefix validation" << '\n';
        return false;
    }
    return true;
}

std::string i128_to_string(i128 value) {
    if (value == 0) {
        return "0";
    }
    bool neg = value < 0;
    if (neg) {
        value = -value;
    }

    std::string out;
    while (value > 0) {
        const int digit = static_cast<int>(value % 10);
        out.push_back(static_cast<char>('0' + digit));
        value /= 10;
    }
    if (neg) {
        out.push_back('-');
    }
    std::reverse(out.begin(), out.end());
    return out;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    const i128 answer = solve(options.sequence, options.lower_bound);
    std::cout << i128_to_string(answer) << '\n';
    return 0;
}

Python

import math

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return abs(a)

def solve(sequence="UDDDUdddDDUDDddDdDddDDUDDdUUDd", lower_bound=1000000000000000):
    A = 1
    B = 0
    C = 1

    for step in reversed(sequence):
        if step == 'D':
            A = 3 * A
            B = 3 * B
        elif step == 'U':
            A = 3 * A
            B = 3 * B - 2 * C
            C = 4 * C
        elif step == 'd':
            A = 3 * A
            B = 3 * B + C
            C = 2 * C
            
    g = gcd(A, C)
    mod = C // g
    a_reduced = A // g
    
    a_mod = a_reduced % mod
    try:
        inv = pow(a_mod, -1, mod)
    except ValueError:
        return -1
        
    B_reduced = B // g
    rhs = (-B_reduced) % mod
    t0 = (rhs * inv) % mod
    
    n0 = (A * t0 + B) // C
    n_step = A // g
    t_step = mod
    
    k = 0
    if n0 <= lower_bound:
        k = (lower_bound - n0) // n_step + 1
        
    t_min = t0 + k * t_step
    if t_min <= 0:
        add = (-t_min) // t_step + 1
        k += add
        
    t = t0 + k * t_step
    return str((A * t + B) // C)

if __name__ == '__main__':
    print(solve())

Java

import java.math.BigInteger;

public class Euler277 {
    static BigInteger solve(String sequence, BigInteger lowerBound) {
        BigInteger A = BigInteger.ONE;
        BigInteger B = BigInteger.ZERO;
        BigInteger C = BigInteger.ONE;

        BigInteger THREE = BigInteger.valueOf(3);
        BigInteger TWO = BigInteger.valueOf(2);
        BigInteger FOUR = BigInteger.valueOf(4);

        for (int i = sequence.length() - 1; i >= 0; --i) {
            char step = sequence.charAt(i);
            if (step == 'D') {
                A = A.multiply(THREE);
                B = B.multiply(THREE);
            } else if (step == 'U') {
                A = A.multiply(THREE);
                B = B.multiply(THREE).subtract(C.multiply(TWO));
                C = C.multiply(FOUR);
            } else if (step == 'd') {
                A = A.multiply(THREE);
                B = B.multiply(THREE).add(C);
                C = C.multiply(TWO);
            }
        }

        BigInteger g = A.gcd(C);
        BigInteger mod = C.divide(g);
        BigInteger aReduced = A.divide(g);

        BigInteger aMod = aReduced.mod(mod);
        BigInteger inv;
        try {
            inv = aMod.modInverse(mod);
        } catch (ArithmeticException e) {
            return BigInteger.valueOf(-1);
        }

        BigInteger bReduced = B.divide(g);
        BigInteger rhs = bReduced.negate().mod(mod);
        BigInteger t0 = rhs.multiply(inv).mod(mod);

        BigInteger n0 = A.multiply(t0).add(B).divide(C);
        BigInteger nStep = A.divide(g);
        BigInteger tStep = mod;

        BigInteger k = BigInteger.ZERO;
        if (n0.compareTo(lowerBound) <= 0) {
            k = lowerBound.subtract(n0).divide(nStep).add(BigInteger.ONE);
        }

        BigInteger tMin = t0.add(k.multiply(tStep));
        if (tMin.compareTo(BigInteger.ZERO) <= 0) {
            BigInteger add = tMin.negate().divide(tStep).add(BigInteger.ONE);
            k = k.add(add);
        }

        BigInteger t = t0.add(k.multiply(tStep));
        return A.multiply(t).add(B).divide(C);
    }

    public static String solve() {
        String sequence = "UDDDUdddDDUDDddDdDddDDUDDdUUDd";
        BigInteger lowerBound = new BigInteger("1000000000000000");
        return solve(sequence, lowerBound).toString();
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}