Project Euler

A Modified Collatz Sequence

A modified Collatz sequence of integers is obtained from a starting value a_1 in the following way: a_(n+1) = a_n / 3 & if a_n equiv 0 (mod 3) (denoted 'D' for down) (4a_n + 2) / 3 & if a_n equiv 1...

Source sync Apr 19, 2026

Problem #0277

Level Level 08

Solved By 3,695

Languages C++, Python

Answer 1125977393124310

Length 367 words

modular_arithmeticnumber_theorysequence

A modified Collatz sequence of integers is obtained from a starting value $a_1$ in the following way:

$a_{n+1} = \, \,\, \frac {a_n} 3 \quad$ if $a_n$ is divisible by $3$. We shall denote this as a large downward step, "D".

$a_{n+1} = \frac {4 a_n+2} 3 \, \,$ if $a_n$ divided by $3$ gives a remainder of $1$. We shall denote this as an upward step, "U".

$a_{n+1} = \frac {2 a_n -1} 3 \, \,$ if $a_n$ divided by $3$ gives a remainder of $2$. We shall denote this as a small downward step, "d".

The sequence terminates when some $a_n = 1$.

Given any integer, we can list out the sequence of steps.

For instance if $a_1=231$, then the sequence $\{a_n\}=\{231,77,51,17,11,7,10,14,9,3,1\}$ corresponds to the steps "DdDddUUdDD".

Of course, there are other sequences that begin with that same sequence "DdDddUUdDD....".

For instance, if $a_1=1004064$, then the sequence is DdDddUUdDDDdUDUUUdDdUUDDDUdDD.

In fact, $1004064$ is the smallest possible $a_1 > 10^6$ that begins with the sequence DdDddUUdDD.

What is the smallest $a_1 > 10^{15}$ that begins with the sequence "UDDDUdddDDUDDddDdDddDDUDDdUUDd"?

Problem 277: A Modified Collatz Sequence

Mathematical Analysis

Inverse Mapping

We can work backwards from the sequence. Given a step type and the result $a_{n+1}$ , we can recover $a_n$ :

D: $a_n = 3 \cdot a_{n+1}$ , and we need $a_n \equiv 0 \pmod{3}$
U: $a_n = (3 \cdot a_{n+1} - 2) / 4$ , and we need $a_n \equiv 1 \pmod{3}$
d: $a_n = (3 \cdot a_{n+1} + 1) / 2$ , and we need $a_n \equiv 2 \pmod{3}$

Forward Approach: Linear Constraint

Each step maps $a_n$ to $a_{n+1}$ via an affine transformation. The composition of all transformations gives us:

a_k = \alpha \cdot a_1 + \beta

for some rational numbers $\alpha, \beta$ that depend on the sequence of steps.

Since each step constrains $a_n \pmod{3}$ , and the transformations are linear, the starting value $a_1$ must satisfy:

a_1 \equiv r \pmod{M}

for some residue $r$ and modulus $M$ , where $M$ is determined by the sequence.

Computing the Modular Constraint

Processing the sequence left to right, we maintain the constraint on $a_1$ as a congruence.

At step $i$ , we know $a_i = \alpha_i \cdot a_1 + \beta_i$ (with rational coefficients). The step type constrains $a_i \pmod{3}$ , which translates to a constraint on $a_1$ .

The modulus $M$ is a power of 3 times powers of 2 and 4 (from the multipliers in U and d steps), specifically $M = 3^k \cdot 2^j \cdot \ldots$

Actually, more precisely:

Each U step introduces a factor of $4/3$ in the multiplier and $+2/3$ in the constant.
Each D step introduces a factor of $1/3$ .
Each d step introduces a factor of $2/3$ and $-1/3$ .

The modulus after processing all steps is $M = 3^{31}$ divided by powers of 2 and 4, which simplifies to some large integer.

Editorial

We process the sequence string to build up the affine transformation and modular constraint. We evaluate the closed-form expressions derived above directly from the relevant parameters and return the resulting value.

Pseudocode

Process the sequence string to build up the affine transformation and modular constraint
The constraint takes the form $a_1 \equiv r \pmod{M}$
Find the smallest $a_1 > 10^{15}$ satisfying this congruence

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity

$O(L)$ where $L$ is the length of the sequence string (31 in this case).
Finding the answer is then a simple modular arithmetic computation.

Answer

\boxed{1125977393124310}

C++ project_euler/problem_277/solution.cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    // Modified Collatz sequence:
    // D: a -> a/3       (a % 3 == 0)
    // U: a -> (4a+2)/3  (a % 3 == 1)
    // d: a -> (2a-1)/3  (a % 3 == 2)
    //
    // Given sequence string, find least a1 > 10^15 producing it.
    //
    // Approach: work backwards from the end of the sequence.
    // After processing all steps, a1 must satisfy a1 ≡ r (mod M).
    // We build this by processing the sequence from right to left.
    //
    // If we know a_{k+1}, we can find a_k:
    // D: a_k = 3 * a_{k+1}        (and a_k % 3 == 0, always satisfied)
    // U: a_k = (3*a_{k+1} - 2)/4  (and a_k % 3 == 1)
    // d: a_k = (3*a_{k+1} + 1)/2  (and a_k % 3 == 2)
    //
    // We represent the constraint on a_1 as: a_1 ≡ r (mod M)
    // Starting from the end, a_{L+1} can be anything, so initially
    // a_{L+1} ≡ 0 (mod 1) (no constraint).
    //
    // Actually, let's think forward with rational arithmetic.
    // a_i = (num_i * a_1 + const_i) / den_i
    // The residue constraint a_i % 3 == required gives us info about a_1.
    //
    // Alternatively, use Python-style big integers via __int128 or just careful modular arithmetic.
    // Since we're dealing with modular constraints, let's track (r, M) where a_1 ≡ r (mod M).

    string seq = "UDDDUdddDDUDDddDdDddDDUDDdUUDd";

    // Forward approach:
    // After k steps, a_{k+1} = (alpha * a_1 + beta) where alpha, beta are rationals.
    // We represent alpha = anum/aden, beta = bnum/bden.
    // But to avoid fractions, track: a_{k+1} * D = A * a_1 + B (all integers).
    // Initially (before step 0): a_1 * 1 = 1 * a_1 + 0, so D=1, A=1, B=0.
    //
    // Step type determines:
    //   a_i = (A * a_1 + B) / D
    //   Required: a_i % 3 == req
    //   This means (A * a_1 + B) / D ≡ req (mod 3)
    //   i.e., A * a_1 + B ≡ req * D (mod 3*D)
    //   i.e., A * a_1 ≡ req * D - B (mod 3*D)
    //
    //   We need gcd(A, 3*D) | (req*D - B), then we can find a_1 mod (3*D/gcd).
    //   This combines with existing constraint a_1 ≡ r (mod M) via CRT.
    //
    // Then update for next step:
    //   D: a_{i+1} = a_i / 3 = (A*a_1 + B) / (3D)  => new D' = 3D, A'=A, B'=B
    //   U: a_{i+1} = (4*a_i + 2)/3 = (4(A*a_1+B)/D + 2)/3 = (4A*a_1 + 4B + 2D)/(3D)
    //      => D'=3D, A'=4A, B'=4B+2D
    //   d: a_{i+1} = (2*a_i - 1)/3 = (2(A*a_1+B)/D - 1)/3 = (2A*a_1 + 2B - D)/(3D)
    //      => D'=3D, A'=2A, B'=2B-D

    // We'll use __int128 to handle large numbers.
    // Actually, the modulus M after 31 steps could be up to 3^31 * 4^... which is huge.
    // Let's use Python for this. But the problem says C++.
    // With careful reduction, we can use long long or __int128.
    // 3^31 ~ 6.17 * 10^14, and with factors of 2 and 4, M could be larger.
    // Actually M divides 3^31 (since each step introduces a factor of 3 in denominator).
    // Wait, U multiplies A by 4, d multiplies A by 2. So A can grow as 4^(count_U) * 2^(count_d).
    // The constraint involves A * a_1 ≡ ... (mod 3*D).
    // D = 3^step (since each step multiplies D by 3).
    // A involves factors of 4 (for U) and 2 (for d) and 1 (for D).

    // Let me use __int128 for safety.
    typedef __int128 lll;

    auto gcd128 = [](lll a, lll b) -> lll {
        if (a < 0) a = -a;
        if (b < 0) b = -b;
        while (b) { a %= b; swap(a, b); }
        return a;
    };

    // Extended GCD
    function<lll(lll, lll, lll&, lll&)> extgcd = [&](lll a, lll b, lll &x, lll &y) -> lll {
        if (b == 0) { x = 1; y = 0; return a; }
        lll x1, y1;
        lll g = extgcd(b, a % b, x1, y1);
        x = y1;
        y = x1 - (a / b) * y1;
        return g;
    };

    // CRT: combine a ≡ r1 (mod m1) and a ≡ r2 (mod m2)
    // Returns (r, m) or (-1, -1) if no solution
    auto crt = [&](lll r1, lll m1, lll r2, lll m2) -> pair<lll,lll> {
        lll g = gcd128(m1, m2);
        if ((r2 - r1) % g != 0) return {-1, -1};
        lll lcm = m1 / g * m2;
        lll x, y;
        extgcd(m1, m2, x, y);
        // solution: r1 + m1 * ((r2-r1)/g * x) mod lcm
        lll diff = (r2 - r1) / g;
        // We need to be careful with overflow. Use __int128.
        lll t = diff % (m2 / g) * (x % (m2 / g)) % (m2 / g);
        lll r = r1 + m1 * t;
        r = ((r % lcm) + lcm) % lcm;
        return {r, lcm};
    };

    lll D = 1, A = 1, B = 0;
    lll r = 0, M = 1; // a_1 ≡ r (mod M), initially no constraint

    for (char c : seq) {
        // a_i = (A * a_1 + B) / D
        // Determine required residue
        int req;
        if (c == 'D') req = 0;
        else if (c == 'U') req = 1;
        else req = 2; // 'd'

        // Constraint: (A * a_1 + B) ≡ req * D (mod 3 * D)
        // => A * a_1 ≡ req * D - B (mod 3 * D)
        lll rhs = (lll)req * D - B;
        lll mod = 3 * D;

        // Reduce: A * a_1 ≡ rhs (mod mod)
        lll g = gcd128(A, mod);
        // rhs must be divisible by g
        // (it should be by construction)
        lll A_red = A / g;
        lll rhs_red = rhs / g;
        lll mod_red = mod / g;

        // Solve A_red * a_1 ≡ rhs_red (mod mod_red)
        lll inv_x, inv_y;
        lll gg = extgcd(A_red, mod_red, inv_x, inv_y);
        // gg should be 1
        lll sol = (rhs_red % mod_red * (inv_x % mod_red) % mod_red + mod_red) % mod_red;

        // Combine with existing constraint via CRT
        auto [nr, nM] = crt(r, M, sol, mod_red);
        r = nr; M = nM;

        // Update A, B, D for next step
        if (c == 'D') {
            // D' = 3D, A' = A, B' = B
            D *= 3;
        } else if (c == 'U') {
            B = 4 * B + 2 * D;
            A = 4 * A;
            D *= 3;
        } else {
            B = 2 * B - D;
            A = 2 * A;
            D *= 3;
        }

        // Simplify by dividing out common factors of A, B, D
        lll common = gcd128(gcd128(A, B), D);
        if (common > 1) {
            A /= common;
            B /= common;
            D /= common;
        }
    }

    // Now a_1 ≡ r (mod M), find smallest a_1 > 10^15
    lll threshold = 1000000000000000LL; // 10^15
    lll answer;
    if (r > threshold) {
        answer = r;
    } else {
        lll k = (threshold + 1 - r + M - 1) / M;
        answer = r + k * M;
    }

    // Print answer (need to convert __int128 to string)
    auto to_string128 = [](lll x) -> string {
        if (x == 0) return "0";
        bool neg = false;
        if (x < 0) { neg = true; x = -x; }
        string s;
        while (x > 0) {
            s += ('0' + (int)(x % 10));
            x /= 10;
        }
        if (neg) s += '-';
        reverse(s.begin(), s.end());
        return s;
    };

    cout << to_string128(answer) << endl;
    return 0;
}

Python project_euler/problem_277/solution.py

#!/usr/bin/env python3
"""
Problem 277: A Modified Collatz Sequence

Find the least starting value > 10^15 that produces the sequence
"UDDDUdddDDUDDddDdDddDDUDDdUUDd"

Method: Track affine transformation a_i = (A * a_1 + B) / D and build
modular constraint on a_1 using CRT.
"""

from math import gcd

def collatz_sequence(a, length):
    """Generate modified Collatz sequence string."""
    s = []
    for _ in range(length):
        if a % 3 == 0:
            s.append('D')
            a = a // 3
        elif a % 3 == 1:
            s.append('U')
            a = (4 * a + 2) // 3
        else:
            s.append('d')
            a = (2 * a - 1) // 3
    return ''.join(s)

def extended_gcd(a, b):
    """Extended Euclidean algorithm. Returns (g, x, y) with a*x + b*y = g."""
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def crt(r1, m1, r2, m2):
    """Chinese Remainder Theorem: combine a = r1 (mod m1) and a = r2 (mod m2)."""
    g = gcd(m1, m2)
    if (r2 - r1) % g != 0:
        return None, None
    lcm = m1 // g * m2
    _, x, _ = extended_gcd(m1, m2)
    diff = (r2 - r1) // g
    t = diff * x % (m2 // g)
    r = (r1 + m1 * t) % lcm
    return r, lcm

def solve():
    seq = "UDDDUdddDDUDDddDdDddDDUDDdUUDd"

    D, A, B = 1, 1, 0
    r, M = 0, 1  # a_1 = r (mod M)

    for c in seq:
        # a_i = (A * a_1 + B) / D
        if c == 'D':
            req = 0
        elif c == 'U':
            req = 1
        else:
            req = 2

        # Constraint: A * a_1 + B = req * D (mod 3*D)
        # => A * a_1 = req*D - B (mod 3*D)
        rhs = req * D - B
        mod = 3 * D

        g = gcd(abs(A), mod)
        A_red = A // g
        rhs_red = rhs // g
        mod_red = mod // g

        _, inv, _ = extended_gcd(A_red % mod_red, mod_red)
        sol = (rhs_red * inv) % mod_red
        if sol < 0:
            sol += mod_red

        r, M = crt(r, M, sol, mod_red)

        # Update for next step
        if c == 'D':
            D *= 3
        elif c == 'U':
            B = 4 * B + 2 * D
            A = 4 * A
            D *= 3
        else:
            B = 2 * B - D
            A = 2 * A
            D *= 3

        # Simplify
        common = gcd(gcd(abs(A), abs(B)), D)
        if common > 1:
            A //= common
            B //= common
            D //= common

    # Find smallest a_1 > 10^15
    threshold = 10**15
    if r > threshold:
        answer = r
    else:
        k = (threshold + 1 - r + M - 1) // M
        answer = r + k * M

    # Verify
    assert collatz_sequence(answer, len(seq)) == seq, "Verification failed!"

    return answer

if __name__ == "__main__":
    answer = solve()
    print(answer)