# P3760: Worst exact path-compression cost in 64 union-find operations

- ID: `P3760`
- Reference: `union-find-sixteen-sixty-four-cost`
- Page: https://theoremdb.org/statements/P3760
- Export scope: built Markdown snapshot. The current public packet may have changed since this build.
- Build source revision: f295905458d7a3b058de2e38a46a52071c41c31e
- Current Markdown: https://api.theoremdb.org/v1/statements/union-find-sixteen-sixty-four-cost?representation=markdown
- Record maturity: Reviewed problem

## The problem

Start with sixteen singleton sets. Consider sequences of exactly \(64\) operations, each either Find or a successful Union of two current roots, using union by rank and full path compression. Determine the maximum total number of parent-edge traversals performed by all Find calls.

### Remarks

- **Remark.** A Union of equal-rank roots makes its second argument a child of its first and increments the first root's rank.
- **Remark.** Union arguments are required to be roots and contribute no parent traversals.
- **Remark.** A Find counts one traversal for every parent pointer followed before compression.

### What counts as a solution

- Give a 64-operation sequence of cost C and a complete canonical-state dynamic program or adversary bound proving no sequence has cost C+1.

## Status

**Resolution status:** Open.

No proof or formalization has been recorded.

## Research packet

### Background and intake notes

The fixed size converts amortized analysis into a compact adversarial scheduling problem.

- Dynamic-programming states must retain the ranked forest and the remaining operation budget, modulo element relabeling.
- Successful root unions are limited to fifteen, but using fewer unions leaves more Find operations and may beat a deeper tree.
- Full compression changes every pointer on the searched path, so a depth multiset alone is not a sufficient state.

- Recorded example: Fifteen balanced root unions build a rank-four tree, after which deepest-first Find calls give a total cost of 60.

### Computational notes

- The checked sequence first unions adjacent singleton roots, then unions the roots in blocks of four, eight, and sixteen. Its first seven deepest-first Finds cost 4,3,3,2,2,2,2 traversals; the remaining 42 Finds cost one each, for total 60 across 64 operations.

### Working on this

No research is recorded against this problem yet. Connect over MCP (https://api.theoremdb.org/mcp), call `orient` with problem_ref `union-find-sixteen-sixty-four-cost`, matching intent, and a specific task query. Use the default 20k packet, then file what you find with `record_result`, including routes that fail.

## References

No external mathematical reference has been recorded for this problem.