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

Contents

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)\)?

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

1Remarks

Remark 1. The initial tuple is counted as time 0.

Remark 2. All four-number integer Ducci sequences eventually reach zero.

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

1Status

Saved packet · July 24, 2026

What counts as a solution

Saved solution (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.^[1]

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.

1Packet records

Show recorded summaries

Record	Kind	Assessment
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.	Result	Evidence: Reproduced A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
claim · Computation 1 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] Relevance to this problem For Longest four-number Ducci trajectory in the 100 box, this successor supplies the direct answer and complete human-readable proof required by the Resolution presentation. Evidence ReproducedA replay is recorded for this computation. Inspect the replay record for its procedure and scope. Record state established Scope all ordered quadruples in {0,...,100}^4 under the four-number Ducci map Sources Reference 1 Details 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. Open full record →
All 2,816 maximizers come from twelve listed primitive representatives by scaling, translation, rotation, and reflection.	Result	Evidence: Reproduced A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
claim · Computation 2 All 2,816 maximizers come from twelve listed primitive representatives by scaling, translation, rotation, and reflection.^[1] Relevance to this problem For Longest four-number Ducci trajectory in the 100 box, record dfb100-claim-complete-extremal-classification (“Twelve primitive dihedral classes give every maximizer”) records a bound, answer, status fact, or structural consequence. The record states: All 2,816 maximizers come from twelve listed primitive representatives by scaling, translation, rotation, and reflection. Evidence ReproducedA replay is recorded for this computation. Inspect the replay record for its procedure and scope. Record state established Scope all ordered quadruples in {0,...,100}^4 with Ducci stopping time 13 Sources Reference 1 Details The primitive representatives, chosen lexicographically within their dihedral orbits, are \[ \begin{gathered} (0,7,20,44),(0,10,29,64),(0,12,34,75),(0,13,37,81),\\ (0,13,38,84),(0,15,43,95),(0,24,37,44),(0,35,54,64),\\ (0,41,63,75),(0,44,68,81),(0,46,71,84),(0,52,80,95). \end{gathered} \] Every ordered maximizer has the unique form \[ c\mathbf 1+g\sigma(p), \] where \(p\) is on this list, \(\sigma(p)\) is one of its eight distinct rotations and reflections, \(1\leq g\leq\lfloor100/\max(p)\rfloor\), and \(0\leq c\leq100-g\max(p)\). Conversely, every tuple of this form has stopping time 13. For a representative with maximum coordinate \(m\), the number contributed is \[ 8\sum_{g=1}^{\lfloor100/m\rfloor}(101-gm). \] The representative maxima are \(44,64,75,81,84,95\), each occurring twice. Their contributions sum to 2,816. Open full record →
A065677 is the same maximum; its inverse sequence places stopping time 13 at bound 44 and stopping time 14 at bound 105.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Proposition 1 A065677 is the same maximum; its inverse sequence places stopping time 13 at bound 44 and stopping time 14 at bound 105.^[1] Relevance to this problem For Longest four-number Ducci trajectory in the 100 box, record dfb100-claim-oeis-identification (“OEIS already records the bounded maximum sequence”) records a bound, answer, status fact, or structural consequence. The record states: A065677 is the same maximum; its inverse sequence places stopping time 13 at bound 44 and stopping time 14 at bound 105. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state established Scope the maximum four-number Ducci stopping time for coordinate bounds through 100 Sources Reference 1 Argument OEIS A065677 defines \(a(n)\) as the maximal Ducci length among nonnegative quadruples whose entries are at most \(n\). This is the present problem with \(n=100\). Its inverse, A065678, records the least bound at which a given length occurs. The two relevant values are \[ A065678(13)=44,\qquad A065678(14)=105. \] It follows that \(A065677(100)=13\). The independently computed values through bound 20 in the candidate record agree term for term with A065677. The literature also explains the quotient used in the certificate. Behn, Kribs-Zaleta, and Ponomarenko treat translation, positive scaling, rotation, and reflection as equivalences and classify four-number longevity in a canonical two-dimensional region. The exhaustive computation here supplies the finite-box multiplicities and complete list of maximizers. Open full record →
A C17 program checks 425,479 primitive canonical states and weights them to all 104,060,401 ordered tuples.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1 A C17 program checks 425,479 primitive canonical states and weights them to all 104,060,401 ordered tuples.^[1] Relevance to this problem For Longest four-number Ducci trajectory in the 100 box, record dfb100-artifact-symmetry-quotient-enumeration (“Symmetry-quotient exhaustive certificate”) supplies evidence or a replay used to check the packet. The record states: A C17 program checks 425,479 primitive canonical states and weights them to all 104,060,401 ordered tuples. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope all primitive minimum-zero dihedral representatives with coordinates at most 100, weighted back to {0,...,100}^4 Sources Reference 1 Entry point `join source_lines with newline, compile with cc -std=c17 -O3, and run` Runtime ISO C17 Details For each nonconstant tuple \(x\), subtract \(c=\min_i x_i\), divide by the positive coordinate gcd \(g\), and choose the lexicographically least rotation or reflection \(p\). Translation, positive scaling, rotation, and reflection preserve the stopping time. This gives a disjoint classification of every nonconstant box tuple. If \(m=\max(p)\) and the dihedral orbit of \(p\) has size \(o\), its full-box weight is \[ o\sum_{g=1}^{\lfloor100/m\rfloor}(101-gm). \] The program enumerates 425,479 primitive canonical representatives. It handles the 101 constant tuples separately. The weighted histogram sums to \(101^4\), the largest stopping time is 13, and exactly twelve canonical representatives attain it. The FNV-1a trace serializes each accepted representative in lexicographic loop order as the little-endian eight-byte word \[ a+(b\ll7)+(c\ll14)+(d\ll21)+(\tau\ll28). \] The trace is `05d8bd77b00e039b`. The stable three-line output has SHA-256 digest `651e1796aa233be72ada58e1affa3d8884162e266e3b4c82065d66c3e9e05ad6`. Related: Computation 2 Open full record →
No records match these filters.

Notes and companion material

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 1. The tuple \((57,81,37,44)\) takes 13 steps, so the maximum is at least 13.

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.

How the 4 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemLongest four-number Ducci trajectory in the 100 box

2 records outside this overview

All 1 recorded relations between these records and the problem

Symmetry-quotient exhaustive certificate is evidence for Twelve primitive dihedral classes give every maximizer

2See also

Merging of orbits under adding the product of nonzero digitsdiscrete dynamical systems
Maximum cycle length of cyclic Rule 30 on 24 cellsdiscrete dynamical systems
First recurrence of Langton's ant on the 7 by 7 torusdiscrete dynamical systems

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Longest four-number Ducci trajectory in the 100 box.” TheoremDB. P2532. Problem statement; statement text SHA-256 291a8043e2d4a2d575e381db8372e3bf386f99ad6ce945af050e2e07dfa18246. https://theoremdb.org/statement/?ref=P2532

BibTeX

@misc{theoremdb-problem-291a8043e2d4a2d575e381db8372e3bf386f99ad6ce945af050e2e07dfa18246,
  title = {{Longest four-number Ducci trajectory in the 100 box}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 291a8043e2d4a2d575e381db8372e3bf386f99ad6ce945af050e2e07dfa18246},
  url = {https://theoremdb.org/statement/?ref=P2532}
}

Plain text: Built Markdown snapshot

This problem includes 4 records joined by 5 typed links, sourced from oeis.org^[1], current as of July 24, 2026.

1Lean verification

Lean formalization needed

A solution has been submitted and awaits independent review.

Open TheoremDB Researcher

Upload a Lean project archive

Once Lean accepts the draft, you can submit it while target review is pending. Your submission request is saved and continues after approval. Private checks stay private until you choose to submit.

1References

Packet source. 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. ↗reference database · primary source · living entry checked 2026-08-01 · checked 2026-08-01Source 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.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.Source named by the research packet.

Fixed extremal stopping-time search on 104060401 initial tuples with strong symmetries.

Discussion

Loading discussion.

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

1Remarks

2What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Remarks

2What counts as a solution

1StatusSolution submittedNot Lean-verified

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance

1Status