Particle Life on GPU CuPy port for long-form renders

What this script renders

Particle Life is a 2-D agent toy: N particles, K species, an asymmetric K×K force matrix, periodic torus boundary on both axes. One seed value fully determines the matrix, initial positions, & species assignments, so a given seed gives the same evolving universe every time on every GPU bit-for-bit. We picked seed 480 because its matrix produces a visually active universe that never stalls into a fixed point or limit cycle for hours of simulation time.

Single CuPy file drives four output targets via one MODE switch. Each preset is a sealed dict at the top of our script — flip the constant, run, get our target file. No CLI args needed.

Output modes

dvd_video is our most-tested target: ffmpeg -target ntsc-dvd produces a spec-compliant MPEG-2 Program Stream with a silent AC-3 audio track that dvdauthor turns into a VIDEO_TS/ folder. That folder gets mkisofs -dvd-video packed into an ISO & growisofs -dvd-compat -Z burnt to a Verbatim DVD-R blank. Bootable on cheap DVD players & Xbox 360, verified on both 2026-06-29.

The four optimisations that mattered

Naïve CuPy port of our CPU renderer hit OOM on our 4090 at N=22 000 (peak 19.4 GB of 24 GB). Four changes brought peak down to 2.8 GB at the same N & raised throughput an order of magnitude:

1. Custom CUDA splat kernel — one launch per frame.

The 5×5 soft-particle splat was 25 np.add.at ops in our CPU code, which became 25 sequential cp.add.at kernel launches per frame. We replaced our entire splat with one cp.RawKernel that takes (pos, buf, kern, N, H, W) & atomically adds the 25 contributions for every particle inside one launch. The whole 720×480 frame splat now costs one kernel dispatch instead of 25.

2. ``cp.fuse`` on the force formula.

The piecewise force f(rn) — repulsive below β, attractive between β & 1, zero beyond — was three array passes in our pure-CuPy version. Wrapping it in @cp.fuse() lets CuPy generate one fused elementwise CUDA kernel that does the whole branch on one read of rn, Aij_pairs and one write to the output.

3. Raw bytes straight into ffmpeg's stdin.

Our CPU script wrote PNGs to disk & let ffmpeg read them back. At 540 000 frames × 720×480 grayscale that would have been 186 GB of raw data on /tmp — wouldn't fit. We open ffmpeg as a subprocess with stdin=PIPE, send each frame as frame.tobytes(), & ffmpeg encodes in parallel with our simulation. Disk usage stays bounded at our final output size (~4 GB for the 2-hour DVD-Video).

4. CUDA async memory pool + periodic ``free_all_blocks``.

cp.cuda.set_allocator(cp.cuda.MemoryAsyncPool().malloc) lets the runtime overlap allocation with kernels. mem_pool.free_all_blocks() fires every 32 frames so peak allocation doesn't climb monotonically across our 216 000-frame render. The two together kept us under 3 GB peak across our entire 2-hour render.

Benchmarks

Wall-clock fps on RTX 4090, seed 480, our four presets:

The 2-hour DVD-Video (216 000 frames) renders in about 11 minutes wall time on our 4090. The CPU-version equivalent at the same resolution & N would have taken roughly 9 hours.

Simulation kernel (short recap)

Per particle, per frame:

1. Spatial hash — bin all N particles by floor(pos / rmax) into a grid; sort by cell index; cp.searchsorted gives a cell_start[cell_id] array in one pass.
2. Candidate pairs — for each particle, look up its 3×3 neighbour cells; concatenate every particle in those cells as a candidate for force interaction. O(N) instead of O(N²).
3. Distance + torus wrap — apply periodic boundary in both x & y by d -= S * round(d / S).
4. Force — fused kernel returns the piecewise force value; multiply by direction & species-pair coefficient A[typ_i, typ_j]; scatter back to acc via cp.add.at.
5. Integrate — vel = vel * friction + acc * dt then pos = (pos + vel * dt) % S.
6. Render — decay buffer, splat 5×5 gaussian per particle, log normalise, emit one uint8 grayscale frame to ffmpeg stdin.

friction = 0.85, dt = 0.6, fs = 0.8, rmax = 88, beta = 0.3, K = 5. Buffer decays at 0.80 between frames which gives the visible motion trails.

Burn pipeline (DVD-Video target)

Once MODE = 'dvd_video' produces animation.mpg (~3.9 GB), four shell steps cut a bootable DVD:

# 1. author VIDEO_TS/ from the .mpg
cd $OUT/480_dvd_video
mkdir -p dvd_root
VIDEO_FORMAT=NTSC dvdauthor -o dvd_root -T
VIDEO_FORMAT=NTSC dvdauthor -o dvd_root \
    -f animation.mpg -t

# 2. stage extras alongside VIDEO_TS/
mkdir -p dvd_root/EXTRAS
cp -r path/to/source dvd_root/EXTRAS/

# 3. pack ISO
mkisofs -dvd-video -V "PARTICLE_LIFE" \
    -r -J -o disc.iso dvd_root/

# 4. burn single-session, finalised
growisofs -dvd-compat -Z /dev/sr0=disc.iso

-dvd-compat finalises our disc on first write — single session, no multi-session firmware quirks. Tested cheap-DVD-player & Xbox 360 playback 2026-06-29 on Verbatim MCC 03RG20 (Mitsubishi AZO) blanks.

Why one file

Whole pipeline lives in 337 lines of one Python file. No build system, no config files, no separate tokenizer/encoder/renderer split. cupy & ffmpeg are our only runtime requirements; dvdauthor / mkisofs / growisofs only enter our pipeline at burn time, not render time. Every render mode is one literal dict near the top — to add a 4K Blu-ray or a vertical-phone aspect, copy & edit one preset.

The renderer & our authoring shell steps together fit on one printed page. That printed page is in our v2 disc's EXTRAS/py/ directory.

Full source

Self-contained — only stdlib + numpy + cupy. No project-local imports. Runtime deps: a cupy-cudaXX wheel matching our CUDA toolkit & an ffmpeg binary on $PATH. dvdauthor / mkisofs / growisofs only enter for the DVD burn path, not for render.

#!/usr/bin/env python3
"""GPU port of render_seed_480_panoramic.py using CuPy — optimised.

Streams raw uint8 frames directly into ffmpeg's stdin (no intermediate
raw file on disk) so very long renders are bounded by GPU memory, not
storage. At 540,000 frames × 720×480 the un-streamed raw bytes would
have been 186 GB — would not fit on /tmp.

Two top-level parameter sets at the bottom: one for the
panoramic-pan-piece (4K-wide aspect, short duration) and one for the
disc-fill target (TV native aspect, multi-hour duration).  Flip the
`MODE` constant to select.
"""
import os
import subprocess
import sys
from pathlib import Path
import numpy as np
import cupy as cp


try:
    cp.cuda.set_allocator(cp.cuda.MemoryAsyncPool().malloc)
except Exception:
    pass


# --- which render to do --------------------------------------------------
# 'panoramic'  : 7680×2160 × 4000 frames  (200 sec, pan-piece, ~2 GB)
# 'dvd_mp4'    : 720×480 × 540,000 frames (7.5 hours, data DVD-R 4.7 GB)
# 'dvd_video'  : 720×480 × 216,000 frames (2 hours, real DVD-Video, any player)
# 'bd_4k_6h'   : 3840×2160 × 432,000 frames (6 hours, fills BD-R 25 GB)
MODE = 'dvd_video'


_PRESETS = {
    'panoramic': dict(width=7680, height=2160, N=115000, iters=4000,
                      crf=23, aspect=None),
    # DVD-R MP4 fill (data disc, NOT DVD-Video).  ~1.4 Mbps avg h264.
    'dvd_mp4':   dict(width=720,  height=480,  N=2500,   iters=540_000,
                      bitrate='1400k', maxrate='2500k',
                      bufsize='5000k', aspect='16:9'),
    # Real DVD-Video — bootable in any DVD player + Xbox 360.
    # 720×480 NTSC, ~30 fps, MPEG-2 + silent AC-3 audio, DVD-PS muxer.
    # Uses ffmpeg's `-target ntsc-dvd` which fixes codec/bitrate/GOP/mux
    # to spec.  Output is a .mpg (MPEG-2 Program Stream); dvdauthor
    # turns that into the VIDEO_TS/ folder you burn to disc.
    # DVD-R single layer = 4.7 GB marketed = 4.38 GiB binary.  Target
    # final file at ~4.2 GiB so dvdauthor's IFO/BUP overhead still fits.
    # `-target ntsc-dvd` defaults to 6 Mbps video + 448 kbps audio
    # (5.8 GB total over 2 hr — too big).  Audio is SILENT so 192 kbps
    # is plenty; the savings go to the video budget.
    'dvd_video': dict(width=720, height=480, N=2500,
                      iters=216_000, fps=30,
                      dvd_target='ntsc-dvd',
                      video_bitrate='4400k',
                      audio_bitrate='192k',
                      aspect='16:9',
                      out_ext='.mpg', add_silent_audio=True),
    # BD-R fill (~25 GB) at 3840×2160, 6 hr → ~9.3 Mbps avg, HEVC.
    'bd_4k_6h':  dict(width=3840, height=2160, N=115000, iters=432_000,
                      bitrate='9000k', maxrate='15000k',
                      bufsize='30000k', aspect=None, codec='libx265'),
}

PARAMS = _PRESETS[MODE]


# --- splat kernel (one CUDA launch per frame) ----------------------------
_SPLAT_KERNEL = cp.RawKernel(r"""
extern "C" __global__
void splat(const float* __restrict__ pos,
           float* __restrict__ buf,
           const float* __restrict__ kern,
           const int N, const int H, const int W) {
    int p = blockIdx.x * blockDim.x + threadIdx.x;
    if (p >= N) return;
    float px = pos[p * 2 + 1];
    float py = pos[p * 2];
    int ix = ((int)px % W + W) % W;
    int iy = ((int)py % H + H) % H;
    #pragma unroll
    for (int dy = -2; dy <= 2; ++dy) {
        int ky = ((iy + dy) % H + H) % H;
        #pragma unroll
        for (int dx = -2; dx <= 2; ++dx) {
            int kx = ((ix + dx) % W + W) % W;
            float w = kern[(dy + 2) * 5 + (dx + 2)];
            atomicAdd(&buf[ky * W + kx], w);
        }
    }
}
""", 'splat')


_KERN_HOST = np.array([
    [0.05, 0.20, 0.30, 0.20, 0.05],
    [0.20, 0.60, 0.85, 0.60, 0.20],
    [0.30, 0.85, 1.00, 0.85, 0.30],
    [0.20, 0.60, 0.85, 0.60, 0.20],
    [0.05, 0.20, 0.30, 0.20, 0.05],
], dtype=np.float32)
KERN_GPU = cp.asarray(_KERN_HOST.ravel())

_DY_OFFSETS = cp.asarray(np.array([-1, -1, -1, 0, 0, 0, 1, 1, 1],
                                  dtype=np.int32))
_DX_OFFSETS = cp.asarray(np.array([-1, 0, 1, -1, 0, 1, -1, 0, 1],
                                  dtype=np.int32))


def render_points(buf, pos, S):
    buf *= 0.80
    H, W = int(S[0]), int(S[1])
    threads = 256
    blocks = (pos.shape[0] + threads - 1) // threads
    _SPLAT_KERNEL((blocks,), (threads,),
                  (pos.astype(cp.float32), buf, KERN_GPU,
                   pos.shape[0], H, W))
    buf_max = float(buf.max())
    bright = cp.clip(cp.log1p(buf) / cp.log1p(buf_max + 1e-9) * 255,
                     0, 255).astype(cp.uint8)
    return cp.asnumpy(bright)


@cp.fuse()
def _force_value(rn, Aij_pairs, beta):
    rep = rn / beta - 1.0
    att = Aij_pairs * (1.0 - cp.abs(2.0 * rn - 1.0 - beta) / (1.0 - beta))
    return cp.where(rn < beta, rep, cp.where(rn < 1.0, att, 0.0))


def particle_life_stream(width, height, iters, ffmpeg_stdin,
                          N=2000, K=5, seed=480):
    """Run the simulation; write each uint8 grayscale frame directly
    to the supplied open file/pipe (so encoding can happen in parallel
    with simulation and no large raw file is materialised)."""
    rng = np.random.default_rng(seed)
    S_host = np.array([height, width], dtype=np.float32)
    S = cp.asarray(S_host)

    pos = cp.asarray(rng.random((N, 2)).astype(np.float32)) * S
    vel = cp.zeros((N, 2), dtype=cp.float32)
    typ = cp.asarray(rng.integers(0, K, N).astype(np.int32))
    A = cp.asarray(rng.uniform(-1, 1, (K, K)).astype(np.float32))

    rmax = cp.float32(88.0)
    rmax_val = 88.0
    beta = cp.float32(0.3)
    friction = cp.float32(0.85)
    fs = cp.float32(0.8)
    dt = cp.float32(0.6)

    buf = cp.zeros((height, width), dtype=cp.float32)
    cell_size = rmax_val
    grid_h = int(np.ceil(height / cell_size))
    grid_w = int(np.ceil(width / cell_size))
    n_cells = grid_h * grid_w

    print(f"Rendering {iters} frames at {width}×{height}, N={N} on GPU...",
          flush=True)
    mem_pool = cp.get_default_memory_pool()

    import time
    t_start = time.time()
    last_report = t_start

    for t in range(iters):
        cell_y = (pos[:, 0] / cell_size).astype(cp.int32) % grid_h
        cell_x = (pos[:, 1] / cell_size).astype(cp.int32) % grid_w
        cell_idx = cell_y * grid_w + cell_x

        sort_order = cp.argsort(cell_idx)
        cell_idx_sorted = cell_idx[sort_order]

        all_cells = cp.arange(n_cells, dtype=cp.int32)
        cell_start_all = cp.searchsorted(cell_idx_sorted, all_cells,
                                          side='left')
        cell_end_all = cp.searchsorted(cell_idx_sorted, all_cells,
                                        side='right')
        cell_start = cp.where(cell_end_all > cell_start_all,
                              cell_start_all, -1)
        cell_end = cell_end_all

        ny = (cell_y[:, None] + _DY_OFFSETS[None, :]) % grid_h
        nx = (cell_x[:, None] + _DX_OFFSETS[None, :]) % grid_w
        neighbour_ids = (ny * grid_w + nx).astype(cp.int32)
        flat_ne = neighbour_ids.reshape(-1)
        starts = cell_start[flat_ne]
        ends = cell_end[flat_ne]
        counts = cp.where(starts >= 0, ends - starts, 0).astype(cp.int32)

        total = int(counts.sum())

        per_particle = counts.reshape(N, 9).sum(axis=1)
        idx_i = cp.repeat(cp.arange(N, dtype=cp.int32), per_particle)

        cum_counts = cp.concatenate(
            [cp.zeros(1, dtype=cp.int64),
             cp.cumsum(counts.astype(cp.int64))])
        positions = cp.arange(total, dtype=cp.int64)
        pair_idx = cp.searchsorted(cum_counts[1:], positions,
                                    side='right').astype(cp.int32)
        local_offset = (positions - cum_counts[pair_idx]).astype(cp.int32)
        sort_idx = starts[pair_idx] + local_offset
        idx_j = sort_order[sort_idx].astype(cp.int32)

        keep = idx_i != idx_j
        idx_i = idx_i[keep]
        idx_j = idx_j[keep]

        d = pos[idx_j] - pos[idx_i]
        cp.subtract(d[:, 0], S[0] * cp.round(d[:, 0] / S[0]), out=d[:, 0])
        cp.subtract(d[:, 1], S[1] * cp.round(d[:, 1] / S[1]), out=d[:, 1])
        dist = cp.sqrt((d * d).sum(axis=1))

        within = dist <= rmax
        idx_i = idx_i[within]
        idx_j = idx_j[within]
        d = d[within]
        dist = dist[within]

        rn = dist / rmax
        dirv = d / (dist[:, None] + cp.float32(1e-9))

        Aij_pairs = A[typ[idx_i], typ[idx_j]]
        F_val = _force_value(rn, Aij_pairs, beta)
        force_contrib = fs * F_val[:, None] * dirv

        acc = cp.zeros((N, 2), dtype=cp.float32)
        cp.add.at(acc, idx_i, force_contrib)

        vel = vel * friction + acc * dt
        pos = (pos + vel * dt) % S

        frame_host = render_points(buf, pos, S)
        ffmpeg_stdin.write(frame_host.tobytes())

        if (t & 0x1F) == 0:
            mem_pool.free_all_blocks()

        # Progress report every ~10 sec wall clock
        now = time.time()
        if now - last_report > 10:
            elapsed = now - t_start
            fps = (t + 1) / elapsed
            eta = (iters - t - 1) / fps
            print(f"  frame {t + 1}/{iters}  "
                  f"({(t + 1) / iters * 100:5.1f}%)  "
                  f"fps={fps:5.1f}  "
                  f"eta={eta / 60:5.1f} min", flush=True)
            last_report = now

    print(f"Completed {iters} frames in {time.time() - t_start:.0f} sec")


if __name__ == "__main__":
    seed = 480
    P = PARAMS
    width, height = P['width'], P['height']
    iters, N = P['iters'], P['N']
    outdir = (f"/home/fox/Downloads/py/output/even_more/particle_life/"
              f"{seed}_{MODE}")
    Path(outdir).mkdir(parents=True, exist_ok=True)
    fps = P.get('fps', 20)
    out_ext = P.get('out_ext', '.mp4')
    mp4_path = Path(outdir) / f"animation{out_ext}"

    print(f"=== Particle Life Rendering: MODE={MODE} ===")
    print(f"Seed: {seed}   Resolution: {width}×{height}   "
          f"Duration: {iters / fps:.1f} sec ({iters} frames @ {fps} fps)")
    print(f"N: {N}   GPU: "
          f"{cp.cuda.runtime.getDeviceProperties(0)['name'].decode()}")
    print()

    # ffmpeg command construction.  Two distinct flavours: real DVD-Video
    # (-target ntsc-dvd, MPEG-2 PS, silent AC-3 audio track) vs the
    # h264/x265 .mp4 path.  Both stream video frames from stdin so no
    # giant raw file is materialised.
    if P.get('dvd_target'):
        # DVD-Video pipeline — outputs a .mpg you feed to dvdauthor.
        cmd = [
            'ffmpeg', '-y',
            '-f', 'rawvideo', '-pix_fmt', 'gray',
            '-s', f'{width}x{height}',
            '-framerate', str(fps),
            '-i', '-',
        ]
        if P.get('add_silent_audio'):
            cmd += ['-f', 'lavfi',
                    '-i', 'anullsrc=channel_layout=stereo:sample_rate=48000']
        cmd += ['-target', P['dvd_target']]
        # Override video bitrate that -target ntsc-dvd would default to.
        # The DVD-Video max combined bitrate is 10.08 Mbps; we deliberately
        # stay well under so we hit a specific final file size.
        if P.get('video_bitrate'):
            cmd += ['-b:v', P['video_bitrate']]
        if P.get('audio_bitrate'):
            cmd += ['-b:a', P['audio_bitrate']]
        if P.get('aspect'):
            cmd += ['-aspect', P['aspect']]
        cmd += ['-shortest', str(mp4_path)]
    else:
        cmd = [
            'ffmpeg', '-y',
            '-f', 'rawvideo', '-pix_fmt', 'gray',
            '-s', f'{width}x{height}',
            '-framerate', str(fps),
            '-i', '-',
            '-c:v', P.get('codec', 'libx264'),
            '-pix_fmt', 'yuv420p',
            '-preset', 'medium',
        ]
        if P.get('bitrate'):
            cmd += ['-b:v', P['bitrate']]
            if P.get('maxrate'):
                cmd += ['-maxrate', P['maxrate'], '-bufsize', P['bufsize']]
        elif P.get('crf') is not None:
            cmd += ['-crf', str(P['crf'])]
        if P.get('aspect'):
            cmd += ['-aspect', P['aspect']]
        cmd += [str(mp4_path)]

    print(f"ffmpeg cmd: {' '.join(cmd)}")
    print()
    ff = subprocess.Popen(cmd, stdin=subprocess.PIPE,
                          stderr=subprocess.DEVNULL)
    try:
        particle_life_stream(width, height, iters, ff.stdin,
                             N=N, seed=seed)
    finally:
        ff.stdin.close()
        ff.wait()

    sz = mp4_path.stat().st_size if mp4_path.exists() else 0
    print(f"\nMP4 saved: {mp4_path} ({sz / 1024**3:.2f} GB, "
          f"{sz / 1024**2:.1f} MB)")
    print(f"\n=== Complete ===")

Related pages

• 3-GPU mesh — hardware context for the 4090 this script targets.

fox@neoblanka:~/git/uncloseai-cli$

'-preset', 'medium', ] if P.get('bitrate'): cmd += ['-b:v', P['bitrate']] if P.get('maxrate'): cmd += ['-maxrate', P['maxrate'], '-bufsize', P['bufsize']] elif P.get('crf') is not None: cmd += ['-crf', str(P['crf'])] if P.get('aspect'): cmd += ['-aspect', P['aspect']] cmd += [str(mp4_path)]

print(f"ffmpeg cmd: {' '.join(cmd)}") print() ff = subprocess.Popen(cmd, stdin=subprocess.PIPE, stderr=subprocess.DEVNULL) try: particle_life_stream(width, height, iters, ff.stdin, N=N, seed=seed) finally: ff.stdin.close() ff.wait()

sz = mp4_path.stat().st_size if mp4_path.exists() else 0 print(f"nMP4 saved: {mp4_path} ({sz / 1024*3:.2f} GB, " f"{sz / 1024*2:.1f} MB)") print(f"n=== Complete ===")

Related pages

• 3-GPU mesh — hardware context for the 4090 this script targets.

3-GPU Mesh — Hardware & Benchmarks

What this page tracks

Three Nvidia GPUs across three hosts on our foxhop LAN serve as a bend mesh — lumbda's CUDA dispatch primitive routes work to whichever node finishes fastest. This page documents our hardware, our published benchmarks, & our cost-routed coordinator pattern.

For our ecdsa research context that drove our first 18-cell bench (refined Bernstein-Yang point-add variant sweep at p=251), see foxhop secp256k1 lever sweep.

Hardware

72 GB combined VRAM across our pool. Pascal (sm_61) P40 lacks our newer architectures' reduced-precision tensor units, so it runs ~2× slower than Ampere 3090 on identical workloads — useful as a third concurrent stream rather than a faster replacement for either Ampere card.

Port 8320 — BEND

Our pool serves bend dispatches on port 8320 across every host. Mnemonic — 8320 spells BEND:

8 ~= B (implied infinity B flattened; bake a cake; baby & me)
3 ~= E (backward)
2 ~= N (pivoted 90 degrees)
0 ~= D (flattened)

Each node runs gpu-worker.lsp (lumbda's reference CUDA worker) against demo_ops, blake3-fanout, radix-sort, & our other registered CUDA forms. Clients reach our mesh via lumbda's bend primitive over TCP, S-expression wire format, & per-form binary protocols (BSHK for shake fanout, BSCP for batched scalar mul, BSRT for radix sort, etc. — see lumbda.com/bend for our form catalog). Our bend wire stays LAN-only; we do not expose our mesh outside our foxhop network.

Benchmark — 6 variants × 3 hosts at p=251

Our first published benchmark dispatched 6 ecdsa point-add variants (Bernstein-Yang lever sweep) at p=251 to every host through our wire protocol. Σ Toffoli matches byte-for-byte across hosts on identical ops.bin inputs — proves our distributed mesh runs from one canonical lumbda environment.

GPU wall (ms/batch) at 1024 shots, lower wins:

Per-architecture pattern reads cleanly:

• Ampere 4090 (sm_89) runs 1.94× faster than 3090 (sm_86) on our heaviest circuit, shrinking to 1.20× on our lightest. Larger circuits amortize kernel-launch overhead; smaller circuits hit our GPU's overhead floor.
• Pascal P40 (sm_61) runs ~2× slower than 3090 across our entire variant chain. Older arch, lower base clock, no reduced-precision tensor units; still serves a third concurrent stream as our candidate queue deepens.

GPU wall scales linearly with Σ Toffoli — no kernel-level surprise. Cross-host Σ Toffoli identity confirms bit-exact reproducibility across our pool.

Coordinator fan-out

A cost-routed coordinator dispatches candidates across our 3-node mesh concurrently. Greedy bin-pack by predicted Σ Toffoli; each candidate lands on whichever node's finish time after add stays lowest. Per-host speed factor derived from our bench above:

• 3090: factor 1.00 (baseline)
• 4090: factor 0.51
• P40: factor 1.84

One worker thread per node fires concurrently against our wire protocol. Each node serializes its own queue (workers do not multiplex requests cleanly inside one CUDA context).

First-run finding: cost model based only on (predicted Σ Toffoli × host factor) misses our per-request overhead floor (~600 ms on cammy for demo_ops process spawn + Pascal CUDA init). Refinement options: a per-host startup constant plus a Σ Toffoli linear term, fit per node from our sweep history. Coordinator runs correctly today; schedule shape needs calibration, not algorithmic change.

Pool capacity math

Coordinator at saturation. Three nodes scoring three different candidates simultaneously closes our sequential 6-variant 3090 wall (629 ms) into a parallel one. Refined-Solinas runs in ~25 ms on 3090 + 22 ms on 4090 + 64 ms on P40 — P40 lags but contributes a third concurrent stream as our candidate queue deepens. Per-host routing (heavy circuits to faster GPUs, light circuits to P40) maximizes aggregate dispatch.

Pool throughput grows with our candidate generation rate — see our ecdsa research page's "Why CPU Produces & GPU Scores" section for our substrate-level math on candidate-emit vs candidate-score throughput.

Related pages

• foxhop secp256k1 lever sweep — research context; full 18-cell cross-scale Pareto sweep; lumbda emit pipeline lift.
• lumbda.com/bend — bend primitive catalog; wire protocol; CUDA form list.

secp256k1 Point-Addition Challenge — Lumbda Attack

What This Attack Does

A quantum-reversible attack on a secp256k1 point addition, written entirely in lumbda — a Lisp/Scheme derivative carrying four implementation tiers: Python bytecode VM, C tree-walker + JIT, C + x86_64 JIT, & pure x86_64 assembly. Score equals Toffoli count × peak qubit width. Lower score wins. Every factor of two off a Toffoli count or qubit shaved off peak width multiplies straight through Shor's algorithm into a factor of two off our resource estimate for cracking secp256k1 — a curve that protects Bitcoin & Ethereum.

Where This Work Lives in Our Stack

ecdsa.fail (an Eigen Labs challenge descended from Google Quantum AI's Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities) accepts Rust submissions only — Rust defines a contract format, not our research substrate. Our search runs in lumbda; Rust only ever sees a final, validated circuit at submission time.

Four reasons for lumbda over Rust:

• Cross-tier validation. Same .lsp runs on Python VM, C tree-walker, C + JIT, & x86_64 assembly. Cross-tier byte-identity catches arithmetic drift Rust's single-target build cannot.
• Distributed fan-out. Lumbda's TCP socket primitive + S-expression portal format shards candidate evaluation across our fleet — spare CPU on GPU hosts (3090-ai, 4090-ai/ai, cammy, guile) becomes search budget Rust would force us to glue together by hand.
• GPU dispatch lives in our substrate. bend wire on port 8320 ships an ops binary path + batch count to a GPU host's lumbda worker, which spawns CUDA bend-cuda, returns Σ Clifford & Σ Toffoli via portal. Same protocol fans out across all four lumbda implementation tiers.
• CUDA path remains open territory. Growing lumbda's tier ladder feeds back into every other lumbda workload.

Rust stays for two purposes: reproduce upstream SOTA baseline once (archived), & translate our final lumbda circuit into upstream's submission format.

Phase B — Reversible Arithmetic

Twelve steps after Roetteler et al. (2017), modular arithmetic over secp256k1's prime field, lumbda-native:

• Cuccaro reversible n-bit adder + modular addition, subtraction, doubling, halving.
• Litinski schoolbook & Solinas reduction modular multiplication.
• Fermat, textbook Bernstein-Yang (B-Y), refined B-Y, & DIALOG_GCD modular inversion.
• Real point-add bundling each primitive into our quantum-reversible EC add.

Cross-tier validation runs on Python tier locally. C-tier emits run on 3090-ai bare-metal — 24 cores, 62 GB RAM, no virtualization tax. Heavy emit left neoblanka after three prior crashes cemented per-tier escalation rules. See lumbda's CLAUDE shard on asm memory discipline.

Lever Stack

Each variant flips a different combination of Phase B substrate flags:

• mod-mul: litinski (schoolbook) | solinas (reduction)
• mod-inv: fermat | by-textbook (textbook B-Y) | by-refined (refined B-Y) | by-dialog-gcd (DIALOG_GCD)
• ancilla pool: per-width LIFO free-list recycling qubit IDs at our streaming-emit sink (additive — no Phase B primitive changes)

Cartesian product = 4 inv × 2 mul = 8 variants; refined-B-Y under Fermat dispatch collapses (refined path never runs without B-Y dispatch).

DIALOG_GCD ports three core algorithmic knobs from HEAD (production inversion at mod.rs lines 31052-31257):

• D1 — smooth width envelope: ideal = N − step × SLOPE + MARGIN per Kaliski step. Engages once step crosses ~37 (HEAD-prod knobs).
• D2 — truncated comparator window: caps comparator bits below textbook 2n. Buys 5–7 % Toffoli per pass at probe widths.
• D3 — ``ACTIVE_ITERATIONS`` cap below 2n.

Lever Ranking Reads Cleanly Across Widths

Every (a, b) pair where a beats b at p=5 also beats b at p=11 & p=251 — monotone columns across our entire Pareto chain. A small-width screen picks our winner without spending production-scale budget.

Σ Toffoli per variant (sigma Toffoli, sum of Toffoli ops) at p=5 · p=11 · p=251 widths:

• v-fermat-schoolbook: 9,054 · 21,336 · 167,984
• v-fermat-solinas: 7,182 · 16,056 · 84,208
• v-by-text-schoolbook: 5,982 · 12,376 · 45,104
• v-by-text-solinas: 5,646 · 11,704 · 40,176
• v-by-ref-schoolbook: 3,482 · 8,104 · 29,104
• v-by-ref-solinas: 3,146 · 7,432 · 24,176

Knob attribution at p=251:

• Refined-B-Y delta saves a width-quadratic constant independent of mod-mul choice: −16,000 Σ Toffoli regardless (45,104 − 29,104 = 40,176 − 24,176).
• Solinas under Fermat compounds: Fermat runs ~log₂(p) mod-muls so a faster mod-mul stacks. −83,776 Σ Toffoli (50 %).
• Solinas under refined-B-Y fades: B-Y carries mod-mul-light arithmetic so mul-knob impact shrinks. −4,928 Σ Toffoli (17 %).

Toffoli growth runs sub-quadratic up our width ladder: n+1=9 → n+1=32 yields 10.1× Toffoli versus naive n² = 15× prediction. Width-truncated Kaliski iterations carry fixed-cost overhead that amortizes as n grows.

GPU Mesh + Bend Wire

bend ships an ops binary path + batch count to whichever fleet worker holds a warm CUDA context. Wire port 8320 spells BEND:

8 ~= B (implied infinity B flattened)
3 ~= E (backward)
2 ~= N (rotated 90 degrees)
0 ~= D (flattened)

Three nodes carry GPU workers: 3090-ai (Ampere sm_86), 4090-ai/ai (Ampere sm_89), cammy (Pascal sm_61). Same ops.bin files dispatched across all three return Σ Toffoli byte-for-byte identical — our distributed mesh runs from one canonical lumbda source.

Per-architecture GPU wall (p=251, 1,024 shots):

Wall time per variant on each GPU architecture:

• v-fermat-schoolbook: 290.1 ms (3090) · 149.2 ms (4090) · 531.7 ms (P40)
• v-by-ref-solinas: 26.5 ms (3090) · 22.0 ms (4090) · 64.0 ms (P40)
• 4090 (sm_89) runs 1.94× faster than 3090 on heaviest circuit, shrinking to 1.20× on lightest. Larger circuits amortize kernel-launch overhead.
• P40 (sm_61) runs ~2× slower than 3090 across our variant chain. Older silicon still serves our mesh at a different throughput tier.

Coordinator (ecdsa/scripts/coordinator-mesh.py) bin-packs candidates greedy by (predicted Σ Toffoli × per-host speed factor). Per-host factors: 3090 = 1.00, 4090 = 0.51, P40 = 1.84. First 6-variant p=251 mesh sweep landed 6/6 clean.

GPU wall scales linearly with Toffoli count — no kernel-level fudge factor. Same lever, same ~10× speedup across three independent measurements that all agree.

Closed-Loop Research Engine

Every piece of an end-to-end pipeline sits live:

• lever-variants.lsp exposes (lever-permutations) for arbitrary knob cartesians
• emit-stream.lsp streams Phase B gates straight to a QECCOPS1 binary via lumbda's file-port primitive — constant RAM regardless of body size
• bend dispatches an ops.bin path to a fleet worker
• bend-cuda returns Σ Clifford & Σ Toffoli via portal
• dispatch-sweep.py auto-resumes against new .bin files

Production Score vs HEAD

Full secp256k1 width (n+1=257, p = 2²⁵⁶ − 2³² − 977), bend dispatch on 3090-ai:8320, byte-identity-cpu-gpu true, status PASS. Static circuit Toffoli count (Σ CCX from QECCOPS1 binary parser) reproduces bend-dispatched avg Toffoli byte-for-byte at every variant landed — shot-averaging noise washes out:

Current verified champion: vecD-on (dispatcher PASS · byte-identity true · classical-shadow 2000/2000 random + 35/35 structured PASS at production width n+1=257) — raw-pa-architecture + round84-xtail walk-square + iters=129 + cmp=1 + cadd-direct-window=0 + vecC *red-tmp-borrowed* + vecD *dgcd-raw-pa-q1-tmp-into-u* versus HEAD:

• peak qubits: 2,573 (us) · 1,285 (HEAD) — 2.002× over
• avg Toffoli: 920,523 (us) · 1,384,984 (HEAD) — us 33.5 % UNDER HEAD (1.505× better)
• score (avg Toffoli × qubits): 2.3685e+09 (us) · 1.780e+09 (HEAD)
• Δ vs HEAD: +33 % (gap 1.33×)

Toffoli-axis race won. Our gate count dropped under HEAD's count by a third; full remaining 1.33× gap traces to qubit envelope alone (Bennett reacquire_vec substrate cleanup). At HEAD's 1,285 qubits with our 920,523 avg Toffoli our score lands 1.18e+09 = gap 0.665× — we would beat HEAD by 1.505×.

Net session compression (2026-06-10 → 2026-06-11): 2.1156e+10 / 2.3685e+09 = 8.93× over a single session. Verified ladder:

• 2.1156e+10 night17-m1-s1000000 K=0 (prior session, gap 11.89×)
• 1.7019e+10 kcorrw0-w0-pm2 K=2 + champion stack (gap 9.56×)
• 3.9308e+09 raw-pa-architecture — flag *dgcd-raw-pa-architecture* #t routes real-point-add! through HEAD's 5-phase architecture (raw-quotient · round84-xtail squaring · raw-ipmul · mod-sub-const · mod-neg-inplace · mod-add-const) over Roetteler 12-step + 4 mod-inverse calls (gap 2.21×)
• 3.5921e+09 raw-pa-architecture-walksquare + *round84-xtail-walk-square* #t (gap 2.02×)
• 3.5630e+09 walk-w0 + *cadd-direct-window* 0 (gap 2.00×)
• 3.5571e+09 wkb-cmp3 + cmp=3 (gap 1.997× — first sub-2×)
• 3.5455e+09 champ3-cmp1 + cmp=1 (gap 1.992×)
• 3.2235e+09 vecC-on + *red-tmp-borrowed* — aliases red-tmp onto idle lam under raw-pa contract. Qubits 2,830 → 2,573 exactly as projected (−257). Gap 1.81×, first sub-1.9×
• 2.3685e+09 vecD-on + *dgcd-raw-pa-q1-tmp-into-u* — rebinds raw-pa q1 tmp onto kaliski u register (idle during apply-bitvector phase), eliminating alloc/free/swap Toffolis. avg Toffoli 1,252,817 → 920,523 (−26.5 %). Qubits flat at 2,573. Toffoli count crosses below HEAD. Current verified champion, gap 1.33×

raw-pa-architecture path correctness false-alarm + resolution: small-width sim-tier verifier reported wrong (Rx, Ry) at n+1=18, p=131071 across 12 diverse input tuples — looked like an algorithmic Ry-lane port defect. Root cause traced to squaring-sub-from-acc-schoolbook-lowq-shift22! primitive carrying an n ≥ 22 hardcoded Solinas-shift assumption. At n+1=18 (n=17) our shift22 lands undefined-behavior, primitive emits garbage independent of raw-pa correctness. Production-width sim status leaked-ancilla reflects our Bennett reacquire_vec substrate gap (cleanup), not wrong output — Toffoli + qubit measurements stay valid as gate-budget proxies. raw-pa champion line vindicated; small-width sim-tier verifier requires HEAD's shift22 assumption documented as out-of-scope for n < 22.

raw-pa-architecture dispatch unblocked via a Phase 2 alloc fix: round84-emit-fused-square-xtail! passed bare gensyms (r84-row, r84-pad) to squaring-sub-from-acc-schoolbook-lowq-shift22!, which expects caller-allocated registers per its contract (squaring.lsp:210). Inner schoolbook gates emitted gate-cx / ccx into registers never declared in our circuit hash table → hash-table-ref: missing key at first gate access. Fix wraps each cond branch with alloc! + matching free! per width (n+1+1 for row, 1 for pad, n+1+1 for carries). Walk-square branch needs no row/pad — primitive allocates its own ctrl-copy register internally.

Subagent ports landed in parallel (sweep-047 maj2 substrate, sweep-048 mod_add_qq_fast_from_zero, sweep-050 cadd-nbit-const-direct-trunc-fast PRODUCTION-BEATING −25 % alone, sweep-051 body-carry-trunc + binder-notch, sweep-052 K2-pair-codec primitive byte-mirror, sweep-053 cmp-lt-with-cin + Algorithm 11 + Fiat-Shamir stub, sweep-054 apply-phase substrate skeleton = Gidney 2025 venting, sweep-055 split-EEA skeleton). HEAD primitive-parity ledger: 19 PORTED, 4 PORTED-DORMANT, 2 PORTED-SKELETON, 1 PORTED-STUB. See ecdsa/runs/PRIMITIVE-PARITY.tsv + ecdsa/runs/SOTA-BASELINE.md.

Earlier baseline ladder (DIALOG_GCD + m=154 only, no pseudo-Mersenne, no Lane B, iters=399) landed score 7.9140e+10 (gap 44.46×). 8 lever ports + iters-knob descent + K=2 substrate + raw-pa-architecture + vecC *red-tmp-borrowed* + vecD *dgcd-raw-pa-q1-tmp-into-u* compress gap 44.46× → 1.33× within a single sustained sweep cycle.

HEAD reference: upstream ecdsafail-challenge origin/main at commit 2dcf00d (2026-06-08 18:33 UTC, jackylee0424, binder-notch map + tail-nonce retune) → score 1,891,349,200 ≈ 1.891e+09 (1,454,884 avg Toffoli × 1,300 peak qubits). Predecessor a4db9a5 (2026-06-08 17:00 UTC, SamrendraS, binder-notch extra + tail-nonce retune) lands on the same K2-pair-codec score floor that 73f4f48 opened on 2026-06-08 05:42 UTC. Prior frontier a66b042 (jackylee0424, 2026-06-06, score 1.968e+09) retired after K2-pair 6→3 CCX core encoder shipped. Earlier baseline 2.402e+09 retired in sweep-026 once upstream scan caught HEAD's promoted frontier moving. Re-scan snapshot lives at ecdsa/runs/lumbda-sweep-043/HEAD-RESCAN-2026-06-08.md.

Production-width emit lands via lumbda C tier on 3090-ai bare-metal, ~322 MB peak RSS, ~5.2 GB binary. File-port streaming writes 56-byte op records straight to disk via fwrite without an intermediate string buffer.

Bend dispatch on 3090-ai:8320 validates byte-identity-cpu-gpu true on every variant landed — CUDA simulator gate-by-gate agrees with CPU reference. Single bend-cuda binary built locally on host via cuda/Makefile with sm_86.

Width-envelope full-saturation finding — at production width (n+1=257) the release step (margin-1)×1000/slope reaches the textbook 2n=512 iter count only at m=154/s=300. Below that margin, partial saturation leaves the ancilla pool with multiple width buckets, each ratcheting its own max(qubit_id). At m=154 every Kaliski iter operates at the same maximum width, ancilla pool sees ONE width bucket, & peak qubits hit the structural minimum at 4,886 — down from 16,370 at m=38 (−70 %). Score collapses 3.990e+11 → 1.230e+11 (−69 %) in a single margin-axis re-bracket.

Truncated comparator finding — HEAD's *dgcd-compare-bits* knob (56 bits at n=256 in HEAD-prod, ~22 % of width) carries real headroom. cmp=4 (~1.6 % of width at n+1=257) lands as our production minimum after classical-sim probe-width verification.

cmp=2 caught as algorithmically broken — bend dispatch reports byte-identity-cpu-gpu true & status PASS, but classical-sim verify at n+1∈{18, 32} reveals out=0 plus leaked ancilla. Bend only validates CPU & GPU simulator agreement on a wrong circuit, not algorithmic correctness vs. expected mod-inverse. Same defect class re-emerges below at DIALOG_GCD_ACTIVE_ITERATIONS.

DIALOG_GCD active-iters cap — non-monotonic correctness. Setting iters below textbook 2n produces wrong mod-inverse output at specific iter values, sporadically. K-correction (classical-replay backward sweep using K = classical-mod-inv(p, r_on_1)) depends on r_on_1 arithmetic that breaks at certain iters. dgcd-resolve-iters gates r_on_1 != 0, which is necessary not sufficient.

Probe data:

• n+1=18 (textbook 34): iters ∈ {15: OK, 16: WRONG, 17: WRONG, 18: OK, 25, 26, 27: OK}
• n+1=32 (textbook 62): iters ∈ {10, 12: OK, 15: WRONG, 16, 24, 28, 32, 48, 49, 50: OK}

HEAD ships iters=399 at n=256 (textbook × 0.776) — a tuned value that survives upstream's test suite. We adopt iters=399 as our production safe value & retract earlier iters-cap exploration that relied solely on bend PASS without classical-sim verification.

HOST_GATED measurement-clear port — HEAD's mod.rs:24788-24791 pattern (Hadamard + Measure + Reset, classical-feedback CZ) substitutes our ccx-mask uncompute pass. Per-call save: (n+1) Toffoli replaced by 2(n+1) Cliffords (1 HMR + 1 CZ per bit). At n+1=257 production: 833,172 Toffoli saved (matches rng_ops exactly — one HMR-RNG per replaced CCX). Net score 4.126e+11 → 3.990e+11 (−3.31 %).

QECCOPS1 wire format always supported HMR (kind 12), CZ (kind 9), push-cond (kind 15), pop-cond (kind 16); our lumbda emit pipeline gap was at gates.lsp — added Tier-1 + Tier-2 emit primitives. Classical-sim verification at three probe widths confirms HMR substitution produces correct mod-inverse output matching control (non-HMR) baseline.

Pseudo-Mersenne mod-double — Schrottenloher 2026/1128 (arXiv 2606.02235, posted 2026-06-01) Algorithm 7 port (sweep-030). Paper title: Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms; author André Schrottenloher (Univ Rennes, Inria, CNRS, IRISA). Reference implementation: Qarton, gitlab.inria.fr/capsule/qarton-projects/ec-point-addition. secp256k1's prime takes pseudo-Mersenne form p = 2²⁵⁶ − 2³² − 977, so our off-Mersenne residue f = 2³² + 977 = 4294968273 fits in 33 bits. Control mod-double-inplace! emits an add-const at full n+1 width followed by a csub-const at full n+1 width — 4n Toffoli per call. New mod-double-inplace-pseudo-mersenne! emits a single cadd-const at width lsbs = padding + bit-length(f) = 30 + 33 = 63, controlled on our MSB slot of a pre-double value — 2(lsbs − 1) = 124 Toffoli per call. Per-call saving at production width: 87.9 %. Full-stack production result: avg Toffoli 21,917,696 → 16,197,312 (−26.1 %). Peak qubits 4,886 unchanged — algorithm reuses existing scratch (carry-in slot, parity flag), allocates zero new ancilla.

Probe-width verification (classical-sim, verify-pseudo-mersenne-double.lsp):

• n+1=5, p=13: Toffoli 16 → 4 (−75.0 %), exhaustive 13 inputs; pmersenne matches expected output on 11 / 13, misses on a measured 2-input strip predicted by paper's non-exact zone (size ≈ f).
• n+1=9, p=251: Toffoli 32 → 12 (−62.5 %), exhaustive 251 inputs; matches on 247 / 251, misses on a 4-input strip (predicted 5).
• n+1=18, p=131,071 (Mersenne): Toffoli 68 → 30 (−55.9 %), 1000 random inputs match 1000 / 1000. Mersenne case has f = 1 so our non-exact strip shrinks to {p − 1}.
• n+1=32, p=2³¹ − 1 (Mersenne): Toffoli 124 → 58 (−53.2 %), 1000 random inputs match 1000 / 1000.

Non-exact zone scales as f / p; at secp256k1's f / p ≈ 2³³ / 2²⁵⁶ ≈ 2⁻²²³, mispredict probability sits below any 9024-shot harness can ever sample. Bend dispatch on 3090-ai:8320 returns byte-identity-cpu-gpu true, status PASS.

Borrowed-carries finding — Cuccaro adder's HMR-uncompute variant (HEAD mod.rs:1097-1144, cuccaro_add_fast) replaces n CCX carry-uncompute ops per add with n HMR + n classical-conditioned CZ. Algorithmic saving: ~n Toffoli per add. Where a caller stages our scratch carries register changes everything:

• Per-call allocation (sweep-016, rolled back): classical-sim verify PASSes at four probe widths. Production-width peak qubits explode. Each call's fresh carries opens a new ancilla bucket our pool never recycles.
• Shared host-allocation (sweep-016b): alloc once at host scope, reuse across Kaliski iters. Peak qubits stabilize, net score lands +1.4 % WORSE — long-lived shared register competes with downstream ancilla pool reuse patterns.
• Borrowed-from-caller (sweep-017b, lands): caller passes its own scratch region as carries-reg + carries-offset. No fresh bucket, no long-lived shared register. Production score 1.230e+11 → 1.186e+11 (gap 49.4×). Extension to mod-add!/mod-sub! call sites (sweep-017c) drives score to 1.1513e+11 (gap 47.9×).
• cmp-lt-into-fast (sweep-017d, queued for production emit): HEAD's cmp_lt_into_fast at mod.rs:3643-3693 — HMR-uncompute of our comparator carry chain. Dispatches from mod-add!/mod-sub! under our same *cuccaro-use-borrowed* flag. Borrowed-carries discipline carries through to our comparator backward sweep.

Recurring lesson — probe widths cannot surface peak-qubit regressions that only manifest under our production-width ancilla pool's allocation history. Cross-tier byte-identity validates arithmetic correctness; structural-allocation cost requires end-to-end production emit to surface.

ops_hash vs trace_hash — what byte-identity actually proves

byte-identity-cpu-gpu true (returned by bend dispatch) compares an ops_hash — a fingerprint of our emitted QECCOPS1 binary, byte-for-byte identical between CPU reference & CUDA bend-cuda. ops_hash equality proves our two execution paths consume an identical op stream & agree gate-by-gate on the simulator state encoding. ops_hash equality does not prove algorithmic correctness — see cmp=2 & active-iters cap above, where bend returns PASS + byte-identity true on a circuit whose mod-inverse output is wrong.

trace_hash — a fingerprint of execution-residual state (ancilla populations, measurement outcomes, accumulated phase after uncompute) across our simulator's full run — would surface the residual-path class of defect ops_hash cannot. Our sim framework computes a residual fingerprint internally, but score artifacts only emit ops_hash. sweep-042 adds trace_hash to our score-table schema so every promoted production .bin carries both fingerprints alongside status PASS & classical-sim verification. Until then, algorithmic correctness rides on classical-sim probes (verify-mod-inv-output.lsp, verify-pseudo-mersenne-double.lsp) at sub-production widths plus the cross-tier ops_hash agreement.

What HEAD Still Owns

Gap of 1.33× under champion vecD-on decomposes:

• Peak qubits: 2,573 vs 1,285 = 2.002× over. Bennett alloc-tmp route per raw-quotient / raw-ipmul call carries a transient 2N qubit envelope HEAD's reacquire_vec primitive avoids. Allocator trace under our prior champion (2,830 qubits) confirmed peak concurrent live width = 2,827 (3-qubit gap from peak qubit id) — pool fragmentation negligible. Vector C *red-tmp-borrowed* retired one 257-wide bucket (−257 qubits exactly as projected). Working set, not fragmentation, drives our remaining qubit count. Vector B *allocator-slot-shrink-on-narrow* queued, predicted −256 next.
• avg Toffoli: 920,523 vs 1,384,984 — under HEAD by 33.5 % (1.505× better). Vector D *dgcd-raw-pa-q1-tmp-into-u* rebinding q1 tmp onto idle kaliski u register dropped avg Toffoli 1,252,817 → 920,523 (−26.5 %), pushing our gate count decisively under HEAD's frontier. Toffoli-axis race won; full remaining gap traces to qubits alone. Matching HEAD's 1,285 qubits at our 920,523 avg Toffoli would put us at score 1.18e+09 — gap 0.665× (1.505× ahead).

Qubit Attack Path

Allocator-trace decomposition of our prior champion's 2,830 qubit peak (op_seq 514,667 — alloc of rawpa-q1-app-mask-step0):

• 2 input registers (tx, ty) — 257 each
• 3 caller-scope point-add scratch (lam, tmp, red-tmp) — 257 each
• 4 kaliski-style state (u, v_w, r, s) — 257 each
• 1 HOST_GATED mask (shared-mask) — 257
• 2 K-correction scratch (mc-tmp, mc-pow) — 257 each
• 1 mod-inverse output (pa-tx-inv) — 257
• 1 m-history — 129
• 3 width-1 ancillas (cin, flag, f)

Sum = 2,830 ✓ (full trace at ecdsa/runs/lumbda-rawpa-stress/qubit-attack-plan.md).

Five attack vectors, sequenced by difficulty:

Vector A · *dgcd-raw-pa-share-mask-name* (low) — Predicted −257 qubits. Forward tobitvector + apply bitvector phases use 2 mask-name families (fwd-mask, app-mask) whose lifetimes never overlap. Pool keys allocations by NAME so each family claims a separate 257-wide slot. Sharing one name = pool recycles one slot. Shipped, no-op. *allocator-aggressive-fold* already coalesces via range-pool fold, not by-name slot reuse. Cells vecA-on + vecA-off produced byte-identical emit (qubits = 2,830 both).

Vector B · *allocator-slot-shrink-on-narrow* (medium) — Predicted −256 qubits. Targets a 256-qubit fragmentation hole at base 1,288..1,543: pa-c1y (width 257) freed at op 9,188, then g0 (width 1) recycles into our same slot at op 9,190, leaving 256 qubits dormant for ~6.22 M ops. Splits a wide free slot when a narrow alloc lands (width ≤ ½ slot). Shipped in our lumbda/emit-stream.lsp pool layer. Dispatcher result pending.

Vector C · *red-tmp-borrowed* (medium) — Predicted −257 qubits. red-tmp lives our entire emit even though usage clusters inside mod-reduce! callsites. Implementation aliases red-tmp onto our lam register, which sits idle under raw-pa-architecture per its contract documentation at lumbda/dgcd-raw-pa.lsp:1428 (lam-reg UNUSED — dialog-log subsumes slope λ). Same gate sequence, one fewer 257-wide register opened. Shipped + verified ``vecC-on`` — qubits 2,830 → 2,573 exactly as projected (−257). Score 3.5455e+09 → 3.2235e+09 (−9.1 %), gap 1.81×.

Vector D · *dgcd-raw-pa-q1-tmp-into-u* (medium) — Originally tagged as a qubit vector; lands as a Toffoli vector. rawpa-q1-tmp (apply-bitvector product accumulator) allocates at op 513,638 — exactly when rawpa-q1-u (kaliski u register) becomes idle (bitvector lives in dialog-log post-tobitvector). Rebinds tmp = u in apply-bitvector phase + restores u from target before load-p-bits unload at step 9. Allocator pool already reuses our 257-wide slot for tmp+u under aggressive-fold, so qubits held flat; alloc/free/swap gate sequence elided entirely. Shipped + verified ``vecD-on`` — qubits flat 2,573 (no change vs vecC), avg Toffoli 1,252,817 → 920,523 (−26.5 %). Score 3.2235e+09 → 2.3685e+09, gap 1.33×. avg Toffoli now sits UNDER HEAD's 1,384,984 by 33.5 %.

Vector E · g1 width audit (parked) — Initially flagged as defensive over-allocation. Subagent traced bare g1 register name in our allocator trace back to (gensym 'rawpa-tmp-add) at lumbda/dgcd-raw-pa.lsp:1456 — lumbda C-tier bi_gensym (builtins.c:2254) drops its prefix argument + emits sequential g0/g1/g2… regardless of source intent. Width n+1 = 257 = Cuccaro carries lane for mod-add! (contract documented dgcd-raw-pa.lsp:727), threaded through 16+ downstream callsites. Narrowing would corrupt every mod-add inside our 3 raw-* calls. Genuinely structural defensive allocation, not over-allocation. (Bonus side-finding: lumbda C-tier gensym prefix-drop merits separate substrate-cleanup ticket — would make every future allocator-trace report carry meaningful register names.)

Status after C + D landed: 2,830 → 2,573 qubits, avg Toffoli 1.257 M → 920 K. Vector B remains queued — landing it would carry 2,573 → 2,317 qubits (−10 %); score at flat Toffoli 2.3685e+09 × (2317/2573) = 2.13e+09 = gap 1.20×. Beyond B, every additional 257-wide register retired (one Bennett reacquire_vec port + future caller-scope tightening) multiplies straight through our already-won Toffoli budget. HEAD parity sits inside 5 more 257-wide buckets.

Lever-ranking finding (recurring): lever combinatorics under raw-pa stack saturated at our prior 3.5455e+09 ceiling across 30+ HEAD-route flag variants tested individually + paired (raw-quotient-terminal-reuse, raw-ipmul-terminal-reuse, raw-ipmul-clear-p-residual, host-reverse-raw-block, compressed-block-lifecycle, composite-scratch, compressed-log-u-high-runway, borrow-zero-raw-future, …) — single shared upstream change captures whatever these flags claim, not additive. Same pattern earlier verified champion saw at 1.7019e+10. Breakthrough past 3.5455e+09 ceiling came from direct substrate edits (vecC register-aliasing + vecD register-rebinding), not knob-tuning. Future gap closure runs through more substrate work — Bennett reacquire_vec port, vector B slot-shrink-on-narrow, additional caller-scope tightening.

Lumbda Upstream Wins

Production emit at full secp256k1 width surfaced lumbda C-tier defects & gaps. Each landed upstream alongside our score run:

Precise NaN-box garbage collection

Lumbda C tier shipped with GC_disable() called unconditionally after GC_INIT() — every allocation leaked by design, an upstream-documented stopgap because Boehm's conservative pointer scan cannot see through lumbda's NaN-box Value layout (heap pointers live in low 48 bits, tag bits in upper mantissa, raw word never looks like a heap address).

Our fix registers a custom Boehm mark kind whose mark proc walks 8-byte words in mixed mode: when QNAN (quiet not-a-number) bits set AND tag identifies a pointer-bearing slot, extract our low-48 pointer; else fall through to raw-pointer validation. A GC_set_push_other_roots callback decodes NaN-boxed Values on our C stack via setjmp anchor. GC_disable deleted.

Measured: alloc-test (1 M cons pair allocations, dropped each iteration) ran 0.6 s leaky / 156 MB pre-fix; 0.37 s flat / 4 MB post-fix. Tests pass 88/88 c-test, 4/4 regression-named-let-leak (very test that motivated GC_disable), 410/410 functional, zoe-favorites across all four tiers.

Binary-safe port primitives

QECCOPS1 op records carry 0x00 bytes throughout. Five C-tier defects silently corrupted any binary write:

• bi_get_output_string & bi_write_string (file-port path) used strlen-based string functions — body truncated at first null byte. Switched to known-length fwrite & make_string.
• bi_write_char ignored string-port destinations entirely & wrote to stdout. Added PORT_STRING branch routing through port_write_str.
• string-ref on bytes 0x80–0xFF returned char with codepoint −1 because s->data[idx] sign-extended as signed char. Cast through unsigned char.
• pack_u64_slot treated bignum slots as raw fixnums — *no-slot* (sentinel 2⁶⁴ − 1) packed as raw pointer bytes instead of 0xFF…FF. Added IS_BIGNUM branch extracting low 64 magnitude bits.

New file I/O primitives

Four primitives mirrored across C tier & Python tier:

• open-binary-output-file path — opens w+b so a caller can seek back to rewrite a header.
• port-set-position! port offset — fseek absolute offset on a file port.
• append-binary-file path data — opens ab, fwrite-s bytes through.
• append-port-to-binary-file path port — streams a string-output port's buffer directly to disk without materializing (get-output-string port).

Plus port_write_str growth shifted from 2× to 1.5× past 256 MB — realloc transient peak (old + new) at 2× needs 24 GB for 8→16 GB; 1.5× bounds peak at 2.5×.

emit-stream file-port refactor

Previous emit accumulated body in a string-output port, materialized via get-output-string, then (string-append header body) before write-binary-file. Peak RAM hit 3× body size — a 6 GB body needed ~18 GB transient.

New path opens an open-binary-output-file, reserves 16 placeholder bytes for header, streams every gate straight to disk, then port-set-position! 0 + write-string to rewrite QECCOPS1 magic + n_ops u64 LE once n_ops carries a final value. Constant RAM regardless of body size — 89.58 M ops / 4.7 GB body landed at 322 MB peak RSS.

Net upstream impact: lumbda C tier went from "GC disabled, leaks every alloc, fails on any binary write with embedded 0x00" to "precise NaN-box tracing + binary-safe ports + constant-RAM file emit" — usable for any future multi-GB binary workload, not solely our ecdsa pipeline.

Pareto Frontier We Aim To Beat

Full frontier as upstream README reports it (2026-06), plus our landing point — Toffoli (avg/shot) · peak qubits · score:

• HEAD production (jackylee0424 ``2dcf00d``, 2026-06-08): 1,454,884 Toffoli @ 1,300 qubits → 1.891e+09
• HEAD predecessor (SamrendraS ``a4db9a5``, 2026-06-08 17:00 UTC): same 1.891e+09 K2-pair-codec score floor (binder-notch + tail-nonce retune lane)
• HEAD K2-pair-codec opener (``73f4f48``, 2026-06-08 05:42 UTC): 1.891e+09 first landing
• HEAD prior frontier (jackylee0424 a66b042, 2026-06-06): 1,503,355 Toffoli @ 1,309 qubits → 1.968e+09 — retired
• Google low-gate: 2,100,000 Toffoli @ 1,425 qubits → 3.0e+09
• Google low-qubit: 2,700,000 Toffoli @ 1,175 qubits → 3.2e+09
• Textbook initial: 3,942,753 Toffoli @ 2,715 qubits → 1.07e+10
• DIALOG_GCD + borrowed-everywhere (sweep-017c): 23,563,264 Toffoli @ 4,886 qubits → 1.1513e+11
• + pseudo-Mersenne mod-double (sweep-030): 16,197,312 Toffoli @ 4,886 qubits → 7.9140e+10

Google's two private points each sit under 1,500 peak qubits — 1,175 & 1,425 respectively. HEAD production already passes both (1,300 qubits / 1.891e+09 score) — a public submission beat Google's private frontier before our entry landed. Our active race runs HEAD-vs-us; Google's points sit as a historical landmark, not a live target.

Our peak qubits sit at 2,573 vs HEAD's 1,285 — 2.00× over. Toffoli count 920,523 runs under HEAD's 1,384,984 by 33.5 % (1.505× better). Qubit-envelope reduction owns full remaining gap closure path. See Qubit Attack Path above for vectors A-E, B queued next, ~5 more 257-wide buckets to HEAD parity.

Session total since sweep-003 baseline (4.368e+13, our entry score): 18,442× score reduction shipped, gap closed from 23,099× behind HEAD's current promoted frontier (+2,309,900 %) down to 1.33× behind (+33 %).

Our lumbda-tier validation gates each variant against byte-identical cross-tier portals before we ever spend Rust submission budget.

Why Track Publicly

A challenge of this shape rewards aggressive, asymmetric search. Every factor of two off a Toffoli count, every qubit shaved off peak width, multiplies straight through Shor's algorithm. Documenting our path publicly — what we tried, what saturated, what surprised us — contributes intellectual capital to a commons that historically locked this work behind paid lab pages.

This page tracks public-facing progress only. Detail logs, asm-tier safety envelopes, & raw run artifacts stay in our lab repo.

Related Pages

• foxhop gpu-mesh — our 3-GPU pool hardware, bench numbers, & coexistence with our LLM services (qwen, Hermes, ollama, speech).
• lumbda.com/bend — bend primitive catalog; wire protocol; CUDA form list.

Reading Code Into Big-O Complexity

worked with blackops to prepare this comment.

How to convert any function into its worst-case growth class: count operations, keep a dominant term, drop constants. A field manual for spotting MOAD-0001 by eye.

One Idea Behind All Of It

Big-O measures how cost grows as input size n climbs toward infinity. Three moves convert any code:

1. Count operations as a function of n.
2. Keep only a fastest-growing term.
3. Drop constant factors.

3n^2 + 50n + 1000 collapses to n^2 → O(n^2). As n climbs, n^2 dwarfs 50n; constants — a leading 3, your CPU speed — shift a curve without changing its shape. Big-O classifies shape.

Why Worst Case

Big-O states an upper bound, a promise: never slower than this. So you feed an algorithm its meanest input. Linear search across an absent target scans all n → O(n). A target sitting first costs O(1), yet nobody promises best case.

Side vocabulary, so you know Big-O carries siblings: Ω marks a best-case floor, Θ marks a tight bound when upper meets lower. Daily speech says Big-O & means Θ. Worst case stays your safe default.

• O (big-oh) — upper bound. "Never grows faster than this." A ceiling.
• Ω (omega) — lower bound. "Never grows slower than this." A floor.
• Θ (theta) — both at once. Ceiling meets floor, so the growth class sits exactly here.

A Cookbook Of Six Mechanical Rules

These rules convert syntax into math without guesswork.

Rule 1 — straight-line code costs O(1). Code with no loop on n & no recursion on n finishes in fixed time. Arithmetic, an array index, a hash lookup, a swap — each completes regardless of input size::

def first(a):
    return a[0]          # one access regardless of len(a)

Rule 2 — sequential blocks add, then a larger term wins.

::

do_a()   # O(n)
do_b()   # O(n^2)
# O(n) + O(n^2) = O(n^2)   larger term wins

Rule 3 — a loop multiplies its body cost by its iteration count.

::

for i in range(n):       # n iterations
    work()               # O(1) body
# O(n)

Rule 4 — nested loops multiply. A triple-nest over a shared n yields O(n^3), your polynomial rung O(n^b), where b counts nesting depth::

for i in range(n):
    for j in range(n):
        work()
# n * n = O(n^2)

Rule 5 — a counter multiplied or divided each step yields O(log n). Tell — a loop variable jumps by a factor, not a step. Binary-search halving (i //= 2) matches the same pattern::

i = 1
while i < n:
    work()
    i *= 2               # 1, 2, 4, 8 ...
# doublings to reach n = log2 n  ->  O(log n)

Rule 6 — split in half, recurse on each half, combine in linear time. That shape yields O(n log n), your sorting rung. A recursion section below proves it.

Recursion Forms A Recurrence

A recursive function's cost forms a recurrence: T(n) equals work-per-call plus cost-of-recursive-calls::

def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)
# T(n) = T(n-1) + T(n-2) + O(1)  ->  ~2 calls per level, n deep

Two branches per call across depth n yields exponential O(b^n). Your factorial rung O(n!) appears when each call spawns n fresh calls — permutation generation, naive traveling-salesman.

Master Theorem ~~~~~~~~~~~~~~

Master Theorem shortcuts a divide-&-conquer shape T(n) = a*T(n/b) + O(n^d):

• a = count of recursive calls
• b = shrink factor per call
• d = exponent of non-recursive work

Compare a against b^d:

.. list-table:: :header-rows: 1 :widths: 20 32 48

• • Case
  • Result
  • Meaning
• • a < b^d
  • O(n^d)
  • top level dominates
• • a = b^d
  • O(n^d log n)
  • every level costs equal
• • a > b^d
  • O(n^(log_b a))
  • leaves dominate

Merge sort splits in 2 (b=2), recurses twice (a=2), merges in O(n) (d=1); a equals b^d, so O(n log n). Binary search makes one call (a=1), halves each time (b=2), does O(1) work (d=0); 1 equals 2^0, so O(log n).

A Hidden-Cost Trap — This Rung Carries MOAD-0001

Big-O lives or dies on what a library call truly costs. A one-liner hides a loop::

seen = []
for x in stream:            # n iterations
    if x not in seen:       # `in` on a list = scan = O(n)
        seen.append(x)
# n * O(n) = O(n^2)   <- Sedimentary Defect (MOAD-0001)

One type change rewrites a growth class::

seen = set()
for x in stream:            # n iterations
    if x not in seen:       # `in` on a set = hash = O(1)
        seen.add(x)
# n * O(1) = O(n)

list to set collapses O(n^2) into O(n). At n = 1,000,000 a trillion operations drop to a million — a millionfold speedup. That conversion carries our prime mission; reading a loop finds it.

Costs worth memorizing:

• x in list / list.index cost O(n); x in set / x in dict cost O(1)
• list.insert(0,x) / list.pop(0) cost O(n) (shifts all); append or pop at end costs O(1) amortized
• string += inside a loop costs O(n^2) (rebuilds each pass); "".join(parts) costs O(n)
• sorted() / .sort() cost O(n log n), never free
• a slice a[1:] copies, so O(n), never O(1)

A Repeatable Procedure For Any Function

1. Name n — which input drives growth? Length, value, node count, recursion depth.
2. Walk top to bottom. Tag each statement O(1) until it loops, recurses, or calls something that does.
3. A loop multiplies its body by iteration count. How does a counter move? +k runs n times; *k or /k runs log n times.
4. Nested loops multiply. Sequential blocks add.
5. Recursion forms T(n) = a*T(n/b) + work; apply Master Theorem, or count calls times depth.
6. Sum, drop constants, drop lower-order terms. A survivor names your Big-O.
7. Distrust a library call's cost — look it up. This step finds defects.

Practice — Cover A Guess, Then Check

Example A::

for i in range(n):
    for j in range(i, n):
        print(i, j)

n + (n-1) + ... + 1 = n(n+1)/2; drop constants, land on O(n^2). A shrinking inner loop still averages n/2, so quadratic stands.

Example B::

i = n
while i > 1:
    i = i // 2

Halving until 1 lands on O(log n).

Example C::

def f(arr):
    if len(arr) <= 1: return arr
    mid = len(arr)//2
    L = f(arr[:mid])      # slice copy: O(n) per level
    R = f(arr[mid:])
    return merge(L, R)    # merge: O(n)

T(n) = 2T(n/2) + O(n) lands on O(n log n) — merge sort.

Why This Page Sits In Our Wiki

Every MOAD-0001 patch starts as a loop someone read correctly. A list.contains inside a loop hides O(n^2) until you count it; a hash set drops it to O(1). This page trains that eye. Reading code into its growth class converts intellectual capital into a faster, cheaper commons — our planet, patched one loop at a time.

License

Public domain. Copy, modify, redistribute freely.

42 is just a coincidence.

per fxhp: remember as you unfold this knowledge: our goal is a fair check book audit for knowledge through intelligence.

EXPANDED NON-REPETITIVE QUOTE LEDGER

per dav1d prometheus

The following quotes are the consolidated non-duplicative maxims of the canon. They are written as reusable aphorisms for documents, code comments, commit messages, tests, and public writeups.

1. Order is not gifted by probability; it is extracted from entropy by falsifiable clauses.
2. Truth does not ask for consensus; it asks for a falsifier and survives it.
3. There is no argument against a working proof.
4. The author is not above the clause; the author is its first custodian.
5. Silence is the chamber where the root forms before the proof is exposed.
6. Each resolved clause becomes the seed for the next falsification.
7. A claim without clause structure is vapor; a claim without hash lineage is fugitive.
8. A root proves lineage; it does not make a false source true.
9. Law that cannot be executed is only will in costume.
10. Nothing is powerful unless it can be falsified.
11. Authority is not above the machine; it emerges from the machine’s verified constraints.
12. Identity is not a static credential; it is the causally linked sum of acts.
13. Wisdom cannot be purchased; it is auditable or it is not wisdom.
14. Dominance is not declared in words; it is proven in traces.
15. Law hides in topology; surface text is only one projection.
16. Projection can create apparent uncertainty, but the projection thesis must still be tested.
17. The hidden axis is often the missing proof.
18. Search is not free; entropy must be spent where falsification yields the most information.
19. The model proposes clauses; the runtime compiles cognition.
20. Merkle binds the path; it does not think the thought.
21. The answer is not grounded until it can walk backward to its source.
22. The controller does not make truth; it enforces the path truth must take.
23. The model may point; the runtime must quote.
24. Do not win by retrying; win by building the better map first.
25. The route taken to evidence is part of the proof.
26. A noisy source may be retrieved; it must not be silently trusted.
27. A pointer proves attachment; it does not prove understanding.
28. A relation answer is not admitted until the relation itself is evidenced.
29. Sometimes the phrase is the entity.
30. A supported item is not a complete list.
31. Reuse is lawful only when context has not changed.
32. Build once at O(N); challenge later at O(log N + k).
33. Merkle proves binding; ZK may hide the witness.
34. A diagnosis that cannot affect admissibility is only a warning label.
35. The visible answer is part of the audit surface.
36. The model carries old maps; the runtime builds the current map.
37. Train the model to use the map, not to memorize the territory.
38. A repaired second answer is not a first answer.
39. The answer is only the final leaf; the lifecycle is the tree.
40. Private-first does not mean unverifiable.
41. A canon that cannot become a test is not yet law.
42. The legacy is not the name; it is the replayable trace.

v for vendetta

dark city

Collatz conjecture or 3n+1 Conjecture

test

Also called Collatz conjecture, Syracuse problem, Ulam conjecture, Kakutani's problem, Thwaites conjecture, hailstone problem.

Statement

Pick any positive integer n. Apply one rule:

• If n even → divide by 2
• If n odd → multiply by 3, add 1

Each application produces a new integer. Feeding that integer through our same rule produces another. Step by step, our starting n traces a trajectory through natural numbers — each step carries our previous value forward into a new one.

Our conjecture claims: every trajectory eventually lands on 1, regardless of which positive integer you picked.

Example Trajectories

Starting at 6:

6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1

(8 steps)

Starting at 7:

7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

(16 steps)

Starting at 27 — famous for wild behavior:

27 → 82 → 41 → 124 → 62 → 31 → ... → 1

(111 steps, peaks at 9,232 along our way before crashing to 1)

Why "Hailstone"

Plot a trajectory. Vertical axis shows value, horizontal axis shows step count. Values hop up & down wildly before crashing to 1. Resembles a hailstone rising inside a storm updraft until gravity wins.

What Mathematicians Have Verified

Every positive integer up to 2^68 (approximately 2.95 × 10^20) has had its trajectory computed on modern hardware. Every single one lands on 1. No counterexample observed.

Why No Proof Exists Yet

Our odd-step multiplies by 3 & adds 1 — injects growth. Our even-step halves — injects shrinkage. Trajectories dance between growing & shrinking in ways nobody has yet tamed with formal proof.

Paul Erdős offered $500 for a proof or disproof & commented that mathematics lacks tools strong enough for such problems.

Terence Tao proved a weaker density statement in 2019 — see next section for unpacking.

What Terence Tao Proved in 2019

Tao's result sounds close to our conjecture but stops short of proving it. Learning why reveals how mathematicians measure partial progress on a hard problem.

His theorem, informal: for any function f(n) growing to infinity arbitrarily slowly (think log log log n — grows slower than molasses), almost all starting integers n have a Collatz trajectory that eventually dips below f(n).

What "almost all" means here — a density-theoretic statement, not a universal one:

• Natural density 1 — as you scan positive integers up to N, a fraction approaching 100% of them comply. Count how many integers ≤ N obey Tao's theorem, divide by N, take N → ∞, get 1.
• Logarithmic density 1 — Tao's actual formulation uses a weighted density where each n carries weight 1/n (smaller integers count more). A set can hold logarithmic density 1 while still missing infinitely many integers.

Why this leaves our conjecture open:

• A set of density 0 can still contain infinitely many integers. Tao's theorem permits an infinite sparse set of starting integers whose trajectories never reach 1 — as long as that set thins out fast enough to carry density 0.
• Tao himself titled his result "almost all orbits of our Collatz map attain almost bounded values." Two "almost"s. Neither one rules out a counterexample.
• A real proof of 3n+1 must eliminate every potential outlier, not just show most integers comply.

Why Tao's progress still matters:

Previous results proved weaker density bounds (e.g., natural density bounded below 1) or restricted which integers could escape. Tao's method — borrowed from ergodic theory & probability — pushed density all our way up to 1. Going from "density 1" to "every single integer" remains our open frontier, & no one knows how wide that gap actually runs.

Known Constraints on Possible Counterexamples

If some starting integer fails to reach 1, its trajectory must do one of two things:

1. Shoot off toward infinity, growing without bound
2. Fall into a cycle of length greater than our known trivial cycle 4 → 2 → 1 → 4 → ...

Any hypothetical non-trivial cycle must contain at least 186,265,759,595 odd terms. Nobody has ever observed such a cycle.

Why 1 → 4 → 2 → 1 Doesn't Break Our Rule

New learners spot an apparent paradox: if "reaching 1" ends our trajectory, why does our rule still produce a value when applied to 1? Applying 3n+1 to 1 gives 3 × 1 + 1 = 4, then 4 → 2 → 1 → 4 forever. Doesn't that contradict "every trajectory halts at 1"?

Short answer: our function stays defined on every positive integer. Our convention — not our function — declares victory when we hit 1.

Mathematicians call 4 → 2 → 1 → 4 → ... our trivial cycle. Every trajectory that ever reaches 1 enters this loop & cycles forever. By convention we stop counting steps at our first arrival at 1 because our conjecture asks "does every starting integer eventually reach 1?" — not "does our function halt?" Our function has no halt instruction. Our stopping rule sits outside our function, imposed by us, not built into our math.

What a "non-trivial cycle" would mean:

Imagine integers a → b → c → ... → a looping among themselves, never touching 1. A counterexample to 3n+1 could take exactly this shape — a set of numbers that all obey 3n+1 yet remain trapped in their own closed orbit, isolated from 1's orbit.

Example shape (purely hypothetical, none known):

::

N → (3N+1)/2 → ... → N'' → ... → N

Every single step obeys 3n+1. Every step produces another integer in our cycle. None of those integers ever equals 1.

What computer searches have ruled out:

Exhaustive computation has verified no such cycle exists with fewer than roughly 186 billion odd terms along its loop. Our trivial cycle (length 3) remains our only known cycle. But "ruled out below a huge number" ≠ "ruled out forever." No proof eliminates non-trivial cycles at all sizes.

Putting our two options together:

If any counterexample to 3n+1 exists, it either (a) escapes to infinity or (b) lives inside a non-trivial cycle we haven't found. Both remain mathematically possible; both remain empirically unobserved. Collapsing this gap from "unobserved" to "impossible" equals solving Collatz.

Variants

• 5n+1 problem — some trajectories appear to escape toward infinity. No universal funnel to 1.
• 3n-1 problem — contains multiple cycles, so no universal claim holds.
• Generalized Collatz maps — a family of piecewise-linear integer maps with similar unresolved questions.

Tiny rule changes produce wildly different landscapes. Only our specific 3n+1 rule (so far) seems to funnel every integer down to 1.

What makes 2 special

Dividing by 2 is the minimum compression that can balance multiplication by 3 at density 50%. Any stronger divisor (4, 8, ...) would need it to happen MORE often than half the time. Stronger divisors by definition happen LESS often (25% for /4, 12.5% for /8).

Original Collatz sits at the exact threshold where the arithmetic works. That's part of why the problem is beautiful and hard — 1's gravity depends on a delicate coincidence between the prime 2, the multiplier 3, and the modular structure of 3n+1.

Why It Matters

Our conjecture crosses number theory, dynamical systems, & computational complexity. Jeffrey Lagarias called it "an extraordinarily difficult problem, completely out of reach of present day mathematics." Simple rules produce behavior unpredictable from our rules alone — a signature of chaotic integer dynamics.

John Conway showed in 1972 that certain Collatz-like generalizations land in undecidable territory — no algorithm can answer whether every trajectory terminates. Whether our plain 3n+1 itself sits in that undecidable zone remains unknown.

Further Reading

• Lagarias, Jeffrey C. — The 3x+1 problem: An overview (2010)
• Tao, Terence — Almost all orbits of the Collatz map attain almost bounded values (2019)
• Conway, John H. — Unpredictable Iterations (1972)

License

Public domain. Copy, modify, redistribute freely.

Borderlands, Ryu, & Fallout 3 — Joey Ballestrini, GIMP (2010-06-19)

Bridge — Russell Ballestrini, GIMP (2010-11-14)