P06 · Packing and covering · Classic

Packing circles of radius 1,2,…,n into a circle

18.002795494y0
0x18.002795494
VERIFIED CONSTRUCTIONr = 9.001397747
n = 5Current record · open

Fit n circles of radii 1, 2, …, n, none overlapping, inside one circle, making the container radius as small as possible.

Formal definition

  • ContainerA circle of radius radius centred at (radius, radius), where radius is yours to choose — it is the score; the unit is the smallest circle
  • Submissionradius and centers, the centres listed in order of radii 1, 2, …, n
  • ConstraintsCircle i has radius exactly i; no two overlap in their interiors; every circle lies wholly inside the container
  • ObjectiveMake the container radius as small as possible

Getting a feel for it

Where the room for improvement is

The big circles set the skeleton and the small ones caulk the seams: each new largest circle can upend the whole previous layout.

Where the frontier is

Radii 1..n into the smallest circle was the 2005 Al Zimmermann programming contest (n = 5..50), with every best result collected in Packomania's ccin table — and not one of them proven. The values are not yet recorded here.

Source
ONE LEADERBOARD PER n

Current best solutions by n

Each n is an independent record with a page of its own. Open any of them to inspect the current construction, then challenge it.

n2
CURRENT RECORD3
Optimal
Record holderReference answer
Solution method
View problem
n3
CURRENT RECORD5
Optimal
Record holderReference answer
Solution method
View problem
n4
CURRENT RECORD7
Optimal
Record holderReference answer
Solution method
View problem
n5
CURRENT RECORD9.001397747best known 9.001397747
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n6
CURRENT RECORD11.057040401best known 11.057040401
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n7
CURRENT RECORD13.462110679best known 13.462110679
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n8
CURRENT RECORD16.221746678best known 16.221746678
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n9
CURRENT RECORD19.233193909best known 19.233193909
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n10
CURRENT RECORD22.000193014best known 22.000193014
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n11
CURRENT RECORD24.96063429best known 24.96063429
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n12
CURRENT RECORD28.371389437best known 28.371389437
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n13
CURRENT RECORD31.545867019best known 31.545867019
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n14
CURRENT RECORD35.095647146best known 35.095647146
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n15
CURRENT RECORD38.83799551best known 38.83799551
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n16
CURRENT RECORD42.458116437best known 42.458116437
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n17
CURRENT RECORD46.291342119best known 46.291342119
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n18
CURRENT RECORD50.119762625best known 50.119762625
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n19
CURRENT RECORD54.240293593best known 54.240293593
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n20
CURRENT RECORD58.400567481best known 58.400567481
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n21
CURRENT RECORD62.558877096best known 62.558877096
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n22
CURRENT RECORD66.760286243best known 66.760286243
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n23
CURRENT RECORD71.19946161best known 71.19946161
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n24
CURRENT RECORD75.749142584best known 75.749142584
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n25
CURRENT RECORD80.285864442best known 80.285864442
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n26
CURRENT RECORD84.978191068best known 84.978191068
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n27
CURRENT RECORD89.750962684best known 89.750962684
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n28
CURRENT RECORD94.525877104best known 94.525877104
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n29
CURRENT RECORD99.483111566best known 99.483111566
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n30
CURRENT RECORD104.540363768best known 104.540363768
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem