# P2532: Longest four-number Ducci trajectory in the 100 box

- ID: `P2532`
- Reference: `ducci-four-box-100`
- Page: https://theoremdb.org/statements/P2532
- Record maturity: Reviewed problem with recorded work

## Problem

For \(x=(x_1,x_2,x_3,x_4)\in\{0,\ldots,100\}^4\), iterate \(D(x)=(|x_1-x_2|,|x_2-x_3|,|x_3-x_4|,|x_4-x_1|)\). What is the largest number of iterations needed to reach \((0,0,0,0)\)?

### Remarks

- **Remark.** The initial tuple is counted as time 0.
- **Remark.** All four-number integer Ducci sequences eventually reach zero.

### What counts as a solution

- Give a tuple attaining the maximum and a complete proof or exhaustive certificate that every tuple in the box reaches zero no later.

## The answer

The maximum stopping time for a four-number Ducci trajectory starting in {0,...,100}^4 is 13, and exactly 2,816 ordered quadruples attain it. [1](#reference-1)

**Review status:** Reproduced.

**Lean verification:** not Lean-verified.

### Verification

Write \(\tau(x)\) for the first time at which \(D^\tau(x)=0\). Exact enumeration gives
\[
\max_{x\in\{0,\ldots,100\}^4}\tau(x)=13.
\]
One witness is \((0,7,20,44)\). Its trajectory is
\[
\begin{aligned}
&(0,7,20,44),(7,13,24,44),(6,11,20,37),(5,9,17,31),\\
&(4,8,14,26),(4,6,12,22),(2,6,10,18),(4,4,8,16),\\
&(0,4,8,12),(4,4,4,12),(0,0,8,8),(0,8,0,8),\\
&(8,8,8,8),(0,0,0,0).
\end{aligned}
\]
The candidate witness \((57,81,37,44)\) belongs to the same class: subtracting 37 gives \((20,44,0,7)\), a rotation of the displayed witness.

The number of ordered starting tuples at each stopping time \(0,1,\ldots,13\) is
\[
(1,100,20100,1353400,53030200,17977176,22886192,5951312,2093072,540976,165040,31136,8880,2816).
\]
These counts sum to \(101^4=104060401\).

The displayed trajectory from (0,7,20,44) takes thirteen Ducci steps, which proves the lower bound. For the upper bound, normalize each nonconstant quadruple by subtracting its smallest coordinate, dividing by the positive greatest common divisor of its coordinates, and taking the least rotation or reflection. Translation, positive scaling, rotation, and reflection preserve the stopping time, so this assigns every nonconstant quadruple to one primitive canonical representative. If that representative has maximum coordinate m and dihedral orbit size o, the number of tuples in the box that it represents is o times the sum of 101-gm over positive integers g with gm at most 100. The companion C17 certificate enumerates all 425,479 primitive representatives, computes this weight for each one, and handles the 101 constant tuples separately. The weights sum to 101^4, so the classes exhaust the box without omission. The last nonzero stopping-time class is thirteen. Together with the displayed witness, this proves that the exact maximum is thirteen.

## Work

### Proof and evidence for the resolution

**Computation 1 (Direct answer and proof for Longest four-number Ducci trajectory in the 100 box).** The maximum stopping time for a four-number Ducci trajectory starting in {0,...,100}^4 is 13, and exactly 2,816 ordered quadruples attain it.

Write \(\tau(x)\) for the first time at which \(D^\tau(x)=0\). Exact enumeration gives
\[
\max_{x\in\{0,\ldots,100\}^4}\tau(x)=13.
\]
One witness is \((0,7,20,44)\). Its trajectory is
\[
\begin{aligned}
&(0,7,20,44),(7,13,24,44),(6,11,20,37),(5,9,17,31),\\
&(4,8,14,26),(4,6,12,22),(2,6,10,18),(4,4,8,16),\\
&(0,4,8,12),(4,4,4,12),(0,0,8,8),(0,8,0,8),\\
&(8,8,8,8),(0,0,0,0).
\end{aligned}
\]
The candidate witness \((57,81,37,44)\) belongs to the same class: subtracting 37 gives \((20,44,0,7)\), a rotation of the displayed witness.

The number of ordered starting tuples at each stopping time \(0,1,\ldots,13\) is
\[
(1,100,20100,1353400,53030200,17977176,22886192,5951312,2093072,540976,165040,31136,8880,2816).
\]
These counts sum to \(101^4=104060401\).

The displayed trajectory from (0,7,20,44) takes thirteen Ducci steps, which proves the lower bound. For the upper bound, normalize each nonconstant quadruple by subtracting its smallest coordinate, dividing by the positive greatest common divisor of its coordinates, and taking the least rotation or reflection. Translation, positive scaling, rotation, and reflection preserve the stopping time, so this assigns every nonconstant quadruple to one primitive canonical representative. If that representative has maximum coordinate m and dihedral orbit size o, the number of tuples in the box that it represents is o times the sum of 101-gm over positive integers g with gm at most 100. The companion C17 certificate enumerates all 425,479 primitive representatives, computes this weight for each one, and handles the 101 constant tuples separately. The weights sum to 101^4, so the classes exhaust the box without omission. The last nonzero stopping-time class is thirteen. Together with the displayed witness, this proves that the exact maximum is thirteen.

### Background and intake notes

The exact target is a finite stopping-time maximum. Canonical-state counts and the current record tuple are the useful shared state.

- Original intake status: Status not established. Ducci sequences are well studied, and this box maximum may be derivable from known classifications.
- Scaling preserves stopping time, so primitive tuples suffice. Dihedral coordinate symmetry and adding a common constant give further reductions when the normalized tuple stays in the box.
- Memoized stopping times should be stored after canonical normalization; otherwise most work is repeated along merged trajectories.

- Recorded example: The tuple \((57,81,37,44)\) takes 13 steps, so the maximum is at least 13.

### Supporting results

- **Computation 2** (reproduced): All 2,816 maximizers come from twelve listed primitive representatives by scaling, translation, rotation, and reflection. [1](#reference-1)
- **Proposition 1** (supported): A065677 is the same maximum; its inverse sequence places stopping time 13 at bound 44 and stopping time 14 at bound 105. [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): A C17 program checks 425,479 primitive canonical states and weights them to all 104,060,401 ordered tuples. [1](#reference-1)

### Computational notes

- Exhaustive memoized search gave maxima 4,4,6,7,7,7,7,7,8,8,9,9,10,10,10,10,10,10,10,10 for box limits 1 through 20. A seeded uniform random search of 2000000 tuples in the limit-100 box found the stated 13-step tuple. Random sampling gives no upper bound.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `ducci-four-box-100`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## Lean verification

An informal proof is recorded. A Lean formalization still needs to be attached.

[Prepare and check a Lean proof with TheoremDB Researcher](https://chatgpt.com/g/g-6a6c206c5acc8191b184bb55fb72c5b3-theoremdb-researcher?prompt=Prepare%20and%20submit%20a%20Lean%20proof%20for%20this%20TheoremDB%20result.%0A%0AExact%20problem_ref%3A%20ducci-four-box-100%0A%0AExact%20title%3A%20Longest%20four-number%20Ducci%20trajectory%20in%20the%20100%20box%0A%0ACanonical%20packet%3A%20https%3A%2F%2Ftheoremdb.org%2Fstatements%2Fducci-four-box-100%2F%23lean-verification%0A%0AStart%20with%20prepareLeanProof%20for%20this%20exact%20problem_ref.%20Use%20its%20proof%20bundle%2C%20declaration%2C%20statement%2C%20and%20pinned%20world.%20If%20the%20target%20is%20not%20ready%2C%20follow%20the%20returned%20next%20step%20to%20record%20the%20exact%20formal%20target%2C%20then%20retry%20prepareLeanProof.%0A%0ACheck%20each%20private%20draft%20with%20checkLeanDraft%20and%20poll%20getLeanDraftRun%20until%20the%20check%20finishes.%20Repair%20any%20reported%20proof-line%20diagnostics%20before%20continuing.%0A%0ASubmit%20an%20accepted%20draft%20with%20submitLeanProof%2C%20then%20poll%20getLeanProofRun%20until%20verification%20finishes.%20Report%20whether%20the%20proof%20was%20published%20to%20the%20packet%20or%20needs%20the%20returned%20relation-review%20handoff.).

## References

1. <a id="reference-1"></a>OEIS A065677, Maximal Diffy_length for quadruples of numbers <= n; inverse A065678; Behn, Kribs-Zaleta, and Ponomarenko, The Convergence of Difference Boxes, American Mathematical Monthly 112 (2005), 426-439, DOI 10.2307/30037493. OEIS A065677, Maximal Diffy_length for quadruples of numbers <= n; inverse A065678; Behn, Kribs-Zaleta, and Ponomarenko, The Convergence of Difference Boxes, American Mathematical Monthly 112 (2005), 426-439, DOI 10.2307/30037493 https://oeis.org/A065677
   - Also cited at Independent exhaustive artifact dfb100-artifact-symmetry-quotient-enumeration; OEIS A065677 gives the same bounded maximum sequence
   - Also cited at Complete classification emitted and checked by dfb100-artifact-symmetry-quotient-enumeration
   - Also cited at Inline ISO C17 computation compiled and executed on 2026-07-24
   - reference_database; primary source; living entry checked 2026-08-01; checked 2026-08-01
   - Source use: original_summary
   - For Longest four-number Ducci trajectory in the 100 box, the reviewed source scope is OEIS A065677, Maximal Diffy_length for quadruples of numbers <= n; inverse A065678; Behn, Kribs-Zaleta, and Ponomarenko, The Convergence of Difference Boxes, American Mathematical Monthly 112 (2005), 426-439, DOI 10.2307/30037493. The packet makes no inference beyond that cited scope.
   - Source named by the research packet.