Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

-- Packing unit circles in squares: new results

584 views

Skip to first unread message

David W. Cantrell

unread,

Sep 10, 2009, 7:02:16 PM9/10/09

This post continues the thread
-- Packing unit circles in squares: new results
<http://groups.google.com/group/sci.math/browse_thread/thread/b9c976696342e9f2>
which was begun at end of February.

One reason for resuming the thread is that Eckard Specht has recently begun
to make significant improvements to his page about packing circles in
squares: <http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html>.

A difference between the old and new parts of this thread:
Instead of giving the inradius of the square, we now give the side
length s of the square in which N unit circles are packed. This makes
our s equivalent to the quantity called ratio at Packomania.

For a few N < 100, some packings still need a little "tightening".
Here are two packings obtained in that way.

------------------------------------

N = 91
s = 18.69273484728086202046...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs91sq.gif>

The best packing previously known has s = 18.69273484745...

------------------------------------

N = 93
s = 18.8941505403268830126971455556157164717444...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs93sq.gif>

To all decimal places reported at Packomania, s for the best packing
previously known is the same as that above. However, the following
pairs of circles are tangent in the new packing, but not in the
previous one: (8, 17), (17, 22), (17, 26) and (69, 78). Based on the
distances between those circles in the previous packing, it can be
calculated that its s is larger by roughly 3 * 10^-31 than s for the
new packing.

------------------------------------

David W. Cantrell

unread,

Sep 17, 2009, 8:49:36 PM9/17/09

A packing for N = 400 is given, obtained by tightening the previously
known configuration.

David W. Cantrell <DWCan...@sigmaxi.net> wrote:
> This post continues the thread
> -- Packing unit circles in squares: new results
<http://groups.google.com/group/sci.math/browse_thread/thread/b9c976696342e9f2>

> which was begun at the end of February.

N = 400
s = 38.16458327390574737941...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs400sq.gif>

The best packing previously known has s = 38.16462...

------------------------------------

David W. Cantrell

Message has been deleted

David W. Cantrell

unread,

Sep 24, 2009, 1:47:16 AM9/24/09

Eckard Specht has recently improved his pages at Packomania which give
packings of circles in a 5x1 rectangle
<http://hydra.nat.uni-magdeburg.de/packing/crc_200/crc.html>
and in a 10x1 rectangle
<http://hydra.nat.uni-magdeburg.de/packing/crc_100/crc.html>.

Inspired by that, I'm going to take a detour, for a little while, to
present some improved packings of unit circles in rectangles with
length/width = 5 or 10. (My lengths will thus be equivalent to Eckard's
"ratios".)

------------------------------------

N = 41, length/width = 5
length = 27.97385735366980356288...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs41rect5x1.gif>

The best packing previously known has length = 27.97398...

------------------------------------

N = 63, length/width = 5
length = 35.15744953010041569837...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs63rect5x1.gif>

The best packing previously known has length = 35.16426...

------------------------------------

N = 75, length/width = 5
length = 37.96764511662484307381...
symmetry group D_1

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs75rect5x1.gif>

The best packing previously known has length = 37.96856...

------------------------------------

N = 76, length/width = 10
length = 54.09055697107672135781...
symmetry group D_1

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs76rect10x1.gif>

The best packing previously known has length = 54.09746...

------------------------------------

David W. Cantrell

unread,

Sep 24, 2009, 1:35:40 AM9/24/09

David W. Cantrell

unread,

Sep 24, 2009, 2:26:14 PM9/24/09

[I apologize for having posted the previous message more than once. Yes, my
first posting of it did eventually appear ... after about 20 hours!]

In this post, continuing the short detour, improved packings are given for
95 and 96 unit circles in a rectangle with length/width = 5 and for 64, 91
and 199 unit circles in a rectangle with length/width = 10. In three cases,
precise values for the length are given, as zeros of polynomials with
integer coefficients. (Of course, theoretically, that can always be done,
but it is normally impractical to do so.)

David W. Cantrell <DWCan...@sigmaxi.net> wrote:

N = 95, length/width = 5
length = 43.03084701407768740173...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs95rect5x1.gif>

The best packing previously known has length = 43.030907...

------------------------------------

N = 96, length/width = 5
length = 43.15790715065490558485...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs96rect5x1.gif>

The best packing previously known has length = 43.157920...

------------------------------------

N = 64, length/width = 10
length = 51.73494872088683933760...
Precisely, the length is the largest real zero of

596637064711080000000000 - 117677864485281600000000*x +
713096455309464000000*x^2 + 1716801562017093600000*x^3 -
175237172713338230000*x^4 + 2820050294387080000*x^5 +
749950781245288200*x^6 - 73665284858397440*x^7 +
3483071356372369*x^8 - 98231732555352*x^9 +
1678946741406*x^10 - 16056209160*x^11 + 65853225*x^12

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs64rect10x1.gif>

To all 30 reported decimal places, the length for the best packing
previously known agrees with the length for the new packing. But the new
packing has one more contact than the other. The length of the former
packing is larger than that of the new packing by roughly 1.5 * 10^-31.

------------------------------------
>
> N = 76, length/width = 10
> length = 54.09055697107672135781...

Precisely, the length is the larger real zero of
7635274240000 + 517712640000*x - 6161398400*x^2 - 506568480*x^3 + 7307809*x^4.

> symmetry group D_1
>
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs76rect10x1.gif>
>
> The best packing previously known has length = 54.09746...

-----------------------------------

N = 91, length/width = 10
length = 60.35529354450108396452...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs91rect10x1.gif>

The best packing previously known has length = 60.35529354559...

------------------------------------

N = 199, length/width = 10
length = 87.01450677363365783008...
Precisely, the length is the largest real zero of

85320473710599950400000000 + 13445117642796333120000000*x +
405896395408741504000000*x^2 - 25964350067115398400000*x^3 +
501633135345769960000*x^4 - 41208721986819752000*x^5 +
1570865320404961600*x^6 - 33099659200655360*x^7 +
831070217179444*x^8 - 19955082428612*x^9 +
278901973066*x^10 - 1943405430*x^11 + 5313025*x^12

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs199rect10x1.gif>

The best packing previously known has length = 87.014506773633824...

------------------------------------

David W. Cantrell

unread,

Sep 28, 2009, 1:08:20 AM9/28/09

This post will probably conclude the detour. Improved packings are given
for 93, 97, 139, 141, 142, 145-147, 149 and 198-200 unit circles in a
rectangle with length/width = 5. Also, although I didn't really search for
any more improved packings of unit circles in a rectangle with
length/width = 10, I found some anyway! As a first example, see the
previous entry for N = 41 in a rectangle with length/width = 5. I now
describe how that same packing can trivially be used to produce an improved
packing for N = 83 in a rectangle with length/width = 10. More examples are
given later.

David W. Cantrell <DWCan...@sigmaxi.net> wrote:
> Eckard Specht has recently improved his pages at Packomania which give
> packings of circles in a 5x1 rectangle
> <http://hydra.nat.uni-magdeburg.de/packing/crc_200/crc.html>
> and in a 10x1 rectangle
> <http://hydra.nat.uni-magdeburg.de/packing/crc_100/crc.html>.
>
> Inspired by that, I'm going to take a detour, for a little while,
> to present some improved packings of unit circles in rectangles
> with length/width = 5 or 10. (My lengths will thus be equivalent
> to Eckard's "ratios".)
>
> ------------------------------------
>
> N = 41, length/width = 5
> length = 27.97385735366980356288...
>
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs41rect5x1.gif>
>
> The best packing previously known has length = 27.97398...

The new packing above can also be used to produce an improved packing for
N = 83, length/width = 10, with length double that for N = 41. It will have
symmetry group D_1. The axis of symmetry will be the left side of the
rectangle shown in the link. Thus, there will be 41 unit circles on either
side of the axis. And _on_ the axis, there will be room for exactly one
more unit circle, giving a total of 83.

> ------------------------------------
>
> N = 63, length/width = 5
> length = 35.15744953010041569837...
>
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs63rect5x1.gif>
>
> The best packing previously known has length = 35.16426...
>
> ------------------------------------
>
> N = 75, length/width = 5
> length = 37.96764511662484307381...
> symmetry group D_1
>
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs75rect5x1.gif>
>
> The best packing previously known has length = 37.96856...

The new packing above can also be used to produce an improved packing for
N = 151, length/width = 10, with length double that for N = 75, in exactly
the same way, discussed above, that the packing for N = 41, length/width =
5 was used to produce an improved packing for N = 83, length/width = 10.

------------------------------------

N = 93, length/width = 5
length = 42.71020726727360215788...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs93rect5x1.gif>

The best packing previously known has length = 42.71394...

> ------------------------------------
>
> N = 95, length/width = 5
> length = 43.03084701407768740173...
>
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs95rect5x1.gif>
>
> The best packing previously known has length = 43.030907...
>
> ------------------------------------
>
> N = 96, length/width = 5
> length = 43.15790715065490558485...
>
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs96rect5x1.gif>
>
> The best packing previously known has length = 43.157920...

The new packing above can also be used to produce an improved packing for
N = 194, length/width = 10, with length double that for N = 96. It will
have symmetry group D_1. First, move the rattler, circle #3, so that it
touches the top of the rectangle and circles #5 and #8. The axis of
symmetry will be the left side of the rectangle shown in the link. Thus,
there will be 96 unit circles on either side of the axis. And _on_ the
axis, there will be room for exactly two more unit circles, giving a total
of 194.

> ------------------------------------

N = 97, length/width = 5
length = 43.28803838245523520265...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs97rect5x1.gif>

The best packing previously known has length = 43.2880390...

------------------------------------

N = 139, length/width = 5
length = 51.53915850016953680056...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs139rect5x1.gif>

The best packing previously known has length = 51.5391585014...

------------------------------------

N = 141, length/width = 5
length = 51.81383452558296160443...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs141rect5x1.gif>

The best packing previously known has length = 51.8138345255833...

------------------------------------

N = 142, length/width = 5
length = 51.93861693706907258413...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs142rect5x1.gif>
The best packing previously known has length = 51.938616939...

------------------------------------

N = 145, length/width = 5
length = 52.28814483190161607476...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs145rect5x1.gif>
The best packing previously known has length = 52.29538...

------------------------------------

N = 146, length/width = 5
length = 52.38594928817649268588...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs146rect5x1.gif>
The best packing previously known has length = 52.385949290...

------------------------------------

N = 147, length/width = 5
length = 52.46207064459078636225...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs147rect5x1.gif>
The best packing previously known has length = 52.46211...

------------------------------------

N = 149, length/width = 5
length = 52.68629210350792894119...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs149rect5x1.gif>
The best packing previously known has length = 52.6862921076...

------------------------------------

N = 198, length/width = 5
length = 60.78654138626860067031...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs198rect5x1.gif>
The best packing previously known has length = 60.78677...

------------------------------------

N = 199, length/width = 5
length = 60.83554894122289741670...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs199rect5x1.gif>
The best packing previously known has length = 60.8355493...

------------------------------------

N = 200, length/width = 5
length = 60.92952497734265149906...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs200rect5x1.gif>
The best packing previously known has length = 60.929577...

------------------------------------
------------------------------------

There are a few more packings in rectangles with length/width = 5 which can
be used to produce improved packings in rectangles with length/width = 10:

Just as my new packing for N = 41, length/width = 5 was used to produce an
improved packing for N = 83, length/width = 10, so too the old packing for
N = 31, length/width = 5 can be used to produce an improved packing for
N = 63, length/width = 10.

And just as my new packing for N = 96, length/width = 5 was used to produce
an improved packing for N = 194, length/width = 10, so too the old packings
for N = 76, 81, 86 and 91, length/width = 5 can be used, respectively, to
produce improved packings for N = 154, 164, 174 and 184, length/width = 10.

------------------------------------

David W. Cantrell

unread,

Oct 5, 2009, 12:19:56 AM10/5/09

Improved packings of N unit circles in squares of side length s are given
for N = 140, 147, 151 and 156. Then, packings for N = 200, 112 and 113 are
discussed.

------------------------------------

N = 140
s = 22.82852809418014194942...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs140sq.gif>

The best packing previously known has side length s = 22.82875...

------------------------------------

N = 147
s = 23.56271628226509108281...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs147sq.gif>

The best packing previously known has side length s = 23.562733...

------------------------------------

N = 151
s = 23.82251609152315461758...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs151sq.gif>

The best packing previously known has side length s = 23.82310...

------------------------------------

N = 156
s = 24.21392647106173550692...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs156sq.gif>

The best packing previously known has side length s = 24.213966...

------------------------------------
------------------------------------

N = 200
The packing which Eckard had shown prior to his recent update was an
extremum (perhaps not global, but at least local) and, for it, he noted
there were 520 contacts. The packing which he currently shows
<http://hydra.nat.uni-magdeburg.de/packing/csq/ctc/csq200.ctc.html> is not
optimal (although very close to the old extremum) and, for it, he notes
there are 501 contacts. What happened? Here's my best guess: In updating,
recomputing with 30 significant digits, very small inaccuracies seem to
have arisen, manifested in just the last digit or two, causing some circles
to be considered as not touching, when in fact, they should touch. Anyway,
I'm certainly not claiming that I've found an improved packing for N = 200.
The "improved" packing is just Eckard's old packing! But the only way I
know this is that, purely by chance, I happen to have saved a copy of
Eckard's old packing.

N = 112
The packing currently shown is not optimal. Looking at
<http://hydra.nat.uni-magdeburg.de/packing/csq/ctc/csq112.ctc.html>, note
that unit circles #111 and #102 do not touch. But they should touch. I have
computed the side length s for both cases, with them touching and with them
separated by the distance indicated by Eckard's current data. The side
length s is smaller by roughly 5 * 10^-33 when those unit circles touch.
Should I claim to have found an improved packing? I don't know. Perhaps
Eckard's old packing showed those circles touching, but I don't have a copy
of it (and unfortunately, AFAIK, the Wayback Machine does not archive
pictures of the configurations).

N = 113
s = 20.722129538935979011210266045177...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs113sq.gif>
The packing now shown at Packomania
<http://hydra.nat.uni-magdeburg.de/packing/csq/ctc/csq113.ctc.html>
has 9 fewer contacts and is reported as having side length
s = 20.7221295389359790112102660456, differing only in its last digit from
the side length of my packing. But, just as for N = 112, I don't know
whether to claim having found a new, improved packing or not.

------------------------------------
------------------------------------

David W. Cantrell

Phil Carmody

unread,

Oct 5, 2009, 3:10:20 AM10/5/09

David W. Cantrell <DWCan...@sigmaxi.net> writes:
> I don't know
> whether to claim having found a new, improved packing or not.

I'd say that you've corrected the prior packing. Your packing was
the one that was originally intended, it's just that the prior
calculations were not completely right.

Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1

David W. Cantrell

unread,

Oct 8, 2009, 11:26:02 PM10/8/09

Following a reply to Phil, improved packings of N unit circles in squares
are given for N = 164, 166, 169, 173, 175, 182 and 199.

Phil Carmody <thefatphi...@yahoo.co.uk> wrote:
> David W. Cantrell <DWCan...@sigmaxi.net> writes:

[concerning packings for N = 112 and 113]

> > I don't know
> > whether to claim having found a new, improved packing or not.
>
> I'd say that you've corrected the prior packing. Your packing was
> the one that was originally intended, it's just that the prior
> calculations were not completely right.

Thanks for your comment, Phil. I agree, now, that I very likely did not
find improved packings for N = 112 and 113. Here's why:

Shortly after my previous post, I realized that, although the Wayback
Machine doesn't archive pictures of Packomania's old configurations, it
does archive the large table, and that shows the number of contacts. For
N = 112 and 113, the number of contacts in Packomania's old configurations
exceed those in Packomania's current configurations by 1 and 9, resp. This
makes it seem very likely that the old configurations are the same ones I
had in mind.

Since the previous post, I have run across another instance of this. The
configuration currently shown for N = 174 is suboptimal and has 434
contacts. Tightening that configuration, I get 441 contacts and a side
length s which is smaller by roughly 4 * 10^-26. But the former table
indicated 441 contacts too, and thus the configuration formerly shown at
Packomania was quite likely the same as mine.

But let me be clear why I'm not claiming to have found improved packings
for N = 112, 113 and 174: My configurations were presumably found _before_.
That's the only reason. Neglecting rattlers, a packing is fully determined
by its specified tangencies. If the tangencies are different, the packings
are different. If two things don't quite touch in one packing but do touch
in another, the packings are different, regardless of how close the things
were to touching in the former case.

------------------------------------

N = 164
s = 24.67609396003322261776...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs164sq.gif>

The best packing previously known has side length s = 24.67610...

------------------------------------

N = 166
s = 24.85233861404521049713...
symmetry group C_2

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs166sq.gif>

The best packing previously known has side length s = 24.85242...

------------------------------------

N = 169
s = 25.12222402918429617133...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs169sq.gif>

The best packing previously known has side length s = 25.12784...

------------------------------------

N = 173
s = 25.48645582596552372232...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs173sq.gif>

The best packing previously known has side length s = 25.48650...

------------------------------------

N = 175
s = 25.61067784853072896419...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs175sq.gif>

The best packing previously known has side length s = 25.61071...

------------------------------------

N = 182
s = 26.03008795673289527496...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs182sq.gif>

The best packing previously known has side length s = 26.03015...

------------------------------------

N = 199
s = 27.27728916718908176933...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs199sq.gif>

The best packing previously known has side length s = 27.27734...

------------------------------------

David W. Cantrell

unread,

Oct 13, 2009, 1:18:24 AM10/13/09

Improved packings of N unit circles in squares are given

for N = 127, 139, 141, 187 and 196.

------------------------------------

N = 127
s = 21.8991514947500078507975203860310730489419...
[If the eleven leftmost circles were removed, the remaining configuration
of circles would have symmetry group C_2.]

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs127sq.gif>

To all 30 significant digits shown at Packomaia, the side length s for the
current packing there agrees with s for my improved packing. The packing
previously shown at Packomania had 252 contacts, the current one has 261,
and my improved packing has 276. Considering distances between circles
which do not touch, as indicated by Eckard's data for the currently shown
packing, the side length s of my improved packing can be computed to be
smaller by roughly 5 * 10^-33.

------------------------------------

N = 139
s = 22.7553329551620589174004959...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs139sq.gif>

The best packing previously known has side length

s = 22.7553329551620589174004968...
The packing previously shown at Packomania had 298 contacts, the current
one has 295, and my improved packing has 323.

------------------------------------

N = 141
s = 22.9050633023751825283650358015022354765035009106...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs141sq.gif>

To all 30 significant digits shown at Packomaia, the side length s for the
current packing there agrees with s for my packing. The packing previously
shown at Packomania had 313 contacts, the current one has 312, and my
packing has 321. (As I had done for N = 127, one could use distances
between circles which do not touch, as indicated by Eckard's data for the
currently shown packing, to compute the difference between the side lengths
of that packing and my packing. But I have not done that computation in
this case.)

------------------------------------

N = 187
s = 26.17736982806353485460...
symmetry group D_1

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs187sq.gif>

The best packing previously known has side length s = 26.177376...
The packing previously shown at Packomania had 387 contacts, the current
one has 350, and my packing has 412.

------------------------------------

N = 196
s = 26.99318285694563913046...

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs196sq.gif>

The best packing previously known has side length s = 26.99413...
The packing previously shown at Packomania had 379 contacts, as does the
current one, and my packing has 383.

------------------------------------

David W. Cantrell

unread,

Oct 18, 2009, 11:57:26 PM10/18/09

Improved packings of N unit circles in squares are given below for N = 67
and 86. With these packings, we have now reached a milestone: For N <= 100,
although we can not say that all packings are necessarily optimal, we can
at least say that no packings remain which are obviously suboptimal.
(For N = 43 and 75, the packings currently shown at Packomania are
suboptimal, but the packings _previously_ shown there had more contacts and
were presumably optimal.)

------------------------------------

N = 67
s = 15.97764930297533545113...
136 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs67sq.gif>

The best packing previously known has side length

s = 15.977649302975358... and 119 contacts.

------------------------------------

N = 86
s = 17.99434996455841799878...
191 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs86sq.gif>

The best packing previously known has side length

s = 17.99434996455872... and 155 contacts.

------------------------------------

David W. Cantrell

unread,

Oct 29, 2009, 8:39:22 PM10/29/09

Improved packings of N unit circles in squares are given

for N = 157, 193, 218, 225 and 231.

------------------------------------

N = 157
s = 24.26050006607243774413...
374 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs157sq.gif>

The best packing previously known has side length

s = 24.26050081... and 331 contacts.

------------------------------------

N = 193
s = 26.80227046727316860351...
492 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs193sq.gif>

The best packing previously known has side length

s = 26.80227098... and 428 contacts.

------------------------------------

N = 218
s = 28.39627519234245696142...
508 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs218sq.gif>

The best packing previously known has side length

s = 28.3962784... and 494 contacts.

------------------------------------

N = 225
s = 28.8926679822339964460...
560 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs225sq.gif>

The best packing previously known has side length

s = 28.89273... and 508 contacts.

------------------------------------

N = 231
s = 29.24853429039116800103...
603 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs231sq.gif>

The best packing previously known has side length

s = 29.24934... and 578 contacts.

------------------------------------

David W. Cantrell

unread,

Nov 11, 2009, 12:07:45 PM11/11/09

Improved packings of N unit circles in squares are given

for N = 107, 122-124, 130 and 150.

------------------------------------

N = 107
s = 20.19950368823260969444...
219 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs107sq.gif>

The best packing previously known has side length

s = 20.1995071... and 198 contacts.

------------------------------------

N = 122
s = 21.44694327460680064937...
282 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs122sq.gif>

The best packing previously known has side length

s = 21.4469432757... and 225 contacts.

------------------------------------

N = 123
s = 21.57553383271744854305935336736733388...
264 contacts

My packing has just one more contact than the packing currently shown at
Packomania. There hardly seemed to be any reason to produce a new figure of
my own. The only difference between my packing and
<http://hydra.nat.uni-magdeburg.de/packing/csq/ctc/csq123.ctc.html> is that
circle #8 (in cyan) also touches circle #5 in mine.

Based on the distance between circles #5 and #8 in the previous packing,
the side length s of my packing can be estimated to be smaller by 10^-29.

------------------------------------

N = 124
s = 21.69209059074471078155...
258 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs124sq.gif>

The best packing previously known has side length

s = 21.6920905910... and 236 contacts.

------------------------------------

N = 130
s = 22.20092807152355469873...
276 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs130sq.gif>

The best packing previously known has side length

s = 22.200928090... and 266 contacts.

------------------------------------

N = 150
s = 23.727349371979687515587273272397...
328 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs150sq.gif>

The best packing previously known has side length

s = 23.7273493719796875155872732783 and 313 contacts.

------------------------------------

David W. Cantrell

unread,

Nov 23, 2009, 3:47:07 PM11/23/09

Improved packings of N unit circles in squares are given

for N = 136, 144 and 178.

------------------------------------

N = 136
s = 22.546237136793276929412817019685246559...
270 contacts
symmetry group D_1
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs136sq.gif>

The side length s of the packing currently shown at Packomania, with 263
contacts, is larger by roughly 4 * 10^-31 than s of my symmetric packing.

------------------------------------

N = 144
s = 23.25432897623988588807...
300 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs144sq.gif>

The best packing previously known has side length

s = 23.2543289762403... and 282 contacts.

------------------------------------

N = 178
s = 25.81940298475352243466...
449 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs178sq.gif>

The best packing previously known has side length

s = 25.8207... and 419 contacts.

------------------------------------

David W. Cantrell

unread,

Dec 5, 2009, 9:17:02 AM12/5/09

Packings of N unit circles in squares are given

for N = 105, 197, 213, 226, 232, 248, 268 and 285.

------------------------------------

N = 105
s = 19.90329056184468799388537992678431503318621033878...
232 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs105sq.gif>

The packing currently shown at Packomania has 211 contacts and side
length s agreeing, to all 30 significant digits shown there, with s
of my packing. Although I certainly suppose that my packing is an
improvement, I cannot say with absolute confidence that it is.

------------------------------------

N = 197
s = 27.12118092700203863411...
468 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs197sq.gif>

The best packing previously known has side length

s = 27.121193... and 460 contacts.

------------------------------------

N = 213
s = 27.96730167758512201254...
512 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs213sq.gif>

The best packing previously known has side length

s = 27.9673053... and 499 contacts.

------------------------------------

N = 226
s = 28.98021768767236702071...
565 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs226sq.gif>

The best packing previously known has side length

s = 28.9818... and 529 contacts.

------------------------------------

N = 232
s = 29.33162909588731872528676377045248234452587425360...
563 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs232sq.gif>

The packing currently shown at Packomania has 545 contacts and side
length s agreeing, to all 30 significant digits shown there, with s
of my packing. Although I certainly suppose that my packing is an
improvement, I cannot say with absolute confidence that it is.

------------------------------------

N = 248
s = 30.18346610619051817070...
589 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs248sq.gif>

The best packing previously known has side length

s = 30.183476... and 319 contacts.

------------------------------------

N = 268
s = 31.30461402253764262339...
707 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs268sq.gif>

The best packing previously known has side length

s = 31.304694... and 707 contacts.

------------------------------------

N = 285
s = 32.44279571656905022563...
760 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs285sq.gif>

The best packing previously known has side length

s = 32.44291... and 747 contacts.

------------------------------------

David W. Cantrell

unread,

Dec 17, 2009, 8:43:49 AM12/17/09

Improved packings of N unit circles in squares are given
for N = 75, 101, 170 and 249.

------------------------------------

N = 75
s = 17.0956140636363263363384238858817567736367026...
148 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs75sq.gif>

That side length s is approximately 1.7 * 10 ^-29 smaller than that of
the packing currently shown at Packomania, which has 134 contacts.

Earlier in this thread, concerning N = 75, I had said that the packing
previously shown at Packomania, which had 145 contacts, was
"presumably optimal". I now doubt that presumption.

------------------------------------

N = 101
s = 19.5777638848267854447349965465484611783553433...
211 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs101sq.gif>

That side length s is approximately 7.8 * 10 ^-30 smaller than that of
the packing currently shown at Packomania, which has 207 contacts.

------------------------------------

N = 170
s = 25.25800123750814881699...
370 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs170sq.gif>

The best packing previously known has side length

s = 25.258044... and 364 contacts.

------------------------------------

N = 249
s = 30.33900312966831336856...
616 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs249sq.gif>

The best packing previously known has side length

s = 30.33931... and 619 contacts.

------------------------------------

David W. Cantrell

unread,

Dec 28, 2009, 11:22:17 PM12/28/09

Improved packings of N unit circles in squares are given for N = 179, 184,
186, 211, 214, 216 and 220. The packings for N = 186 and 216 are density
records. (A packing of N circles is a _density record_ if its density is
higher than that of any packing of fewer circles.)

------------------------------------

N = 179
s = 25.85158101920251900296325589708342135275...
symmetry group D_1
357 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs179sq.gif>

That side length s is approximately 1.7 * 10 ^-29 smaller than that of

the packing, with 342 contacts, currently shown at Packomania.
(The packing formerly shown there had 353 contacts.)

------------------------------------

N = 184
s = 26.12550568150655606263...
468 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs184sq.gif>

The best packing previously known has side length

s = 26.12569... and 255 contacts.

------------------------------------

N = 186
s = 26.15940091022376482679...
398 contacts
symmetry group C_2
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs186sq.gif>

The best packing previously known has side length

s = 26.1594009102241... and 380 contacts.
(The packing formerly shown there had 396 contacts.)

------------------------------------

N = 211
s = 27.89519515232358919775...
514 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs211sq.gif>

The best packing previously known has side length

s = 27.89522... and 441 contacts.

------------------------------------

N = 214
s = 27.98073035084493648454...
520 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs214sq.gif>

The best packing previously known has side length

s = 27.9807303520... and 485 contacts.

------------------------------------

N = 216
s = 27.99989520823455423889...
589 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs216sq.gif>

The best packing previously known has side length

s = 27.999903... and 91 contacts.

------------------------------------

N = 220
s = 28.58219850153106198529...
568 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs220sq.gif>

The best packing previously known has side length

s = 28.58219889... and 502 contacts.

------------------------------------

David W. Cantrell

spudnik

unread,

Dec 29, 2009, 2:51:46 PM12/29/09

I await the theory!

> N = 220
> s = 28.58219850153106198529...
> 568 contacts

> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs22...>

>
> The best packing previously known has side length
> s = 28.58219889... and 502 contacts.

thus:
garbage up; garbage back down. like I said,
Minkowski couldn't take-back his spiel
about phase-space.

thus:
in California, primarily the gangs constitute the only militia,
per the second amendment (you can look-up the case-law on that,
a digest re the Constitution on Lexis-Nexis, where
it is pretty clear that the "right to bear arms" includes
the wearing of long-sleeved shirts; likewise,
it exposes the liberal-media-owned-by-consWervatives silliness,
where they always confuse "separation of church & state"
with the foundational dysestablishmentarianism in A#1 -- yeah,
they really, always do that, cuz TJ said the six words !-)

so, what is this remarkable Madison/Marx patrimony,
that we exist under?... of course,
they were contemporaries, and Marx actually supported Henry Clay,
for a while, til he was subverted by The Veiled Librarian
at the British Library, in London. and, here,
you can look-up the past publications where this stuff was put,
in *The Campaigner* magazine (it is no-longer called that,
since the goment forced a bogus ch.13 bankruptcy on it, and
several other Larouchiac pubs.: http://www.wlym.com/drupal/campaigners
)).
> I told her about the nutter web pages that keep posting bogus gun
> quotes attributed to the founders. All it takes is five seconds to

thus:
I didn't know that Zeeman made such an experiment, although
I had read of Fizeau's (using high-pressure & -velocity water
in a tube of some sort; did Z verify that?) I woulnd't put
in the terms of either SR or mpc, because it's really more akin
to general relativity viz-a-vu the "curvature of space"
-- not of time, the big PLONK from Minkowski-THEN-he-died --
and that is what surfer's cited essay & figures dyscuss.

read it & sleep on the un-nullities of Michelson & Morley et al
(small, but quite regular; and, you can say "entrainment," if
you must, iff only to evoke Eisntein's gedankenspiel ... and,
we'll just ignore, that "eq. (B)" was derived by Lorentz,
firstly, if also from "the" theory .-)

> > > > problem of Section VI again before us. The tube plays the part of the
> > > > railway embankment or of the co-ordinate system K, the liquid plays
> > > > the part of the carriage or of the co-ordinate system K', and finally,
> > > > the light plays the part of the man walking along the carriage, or of
> > > > the moving point in the present section. If we denote the velocity of
> > > > the light relative to the tube by W, then this is given by the
> > > > equation (A) or (B), according as the Galilei transformation or the
> > > > Lorentz transformation corresponds to the facts. Experiment 1 decides
> > > > in favour of equation (B) derived from the theory of relativity, and
> > > > the agreement is, indeed, very exact. According to recent and most
> > > > excellent measurements by Zeeman, the influence of the velocity of
> > > > flow v on the propagation of light is represented by formula (B) to
> > > > within one per cent..."

> neither M&M or their successors incurred this nullity,
> that proven by Einstein's say-so on DCMiller's article, at Caltech;
> fig. 3, belowsville, puts these results together in one picture. now,
> surfer's language may be peculiar but, so, is yours....
> http://arxiv.org/abs/0804.0039

--l'OEuvre, http://wlym.com
http://www.21stcenturysciencetech.com/Articles_2009/Relativistic_Moon.pdf
FCUK Copenhagen free carbon-credit trade rip-off;
put a tariff on imported energy!

David W. Cantrell

unread,

Jan 10, 2010, 10:30:47 PM1/10/10

Improved packings of N unit circles in squares are given

for N = 106, 125, 145, 160, 162, 201, 217, 305 and 369.

------------------------------------

N = 106
s = 19.99392168113699117860...
246 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs106sq.gif>

The best packing previously known has side length

s = 19.993921681146... and 192 contacts.

------------------------------------

N = 125
s = 21.74937318710201484469...
313 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs125sq.gif>

The best packing previously known has side length

s = 21.74937318754... and 88 contacts.

------------------------------------

N = 145
s = 23.32560351967494525834...
342 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs145sq.gif>

The best packing previously known has side length

s = 23.3256042... and 152 contacts.

------------------------------------

N = 160
s = 24.36374338103095092841...
366 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs160sq.gif>

The best packing previously known has side length

s = 24.363743381030973... and 282 contacts.

------------------------------------

N = 162
s = 24.51108212900761614617...
359 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs162sq.gif>

The best packing previously known has side length

s = 24.511096... and 300 contacts.

------------------------------------

N = 201
s = 27.34511902281446749953...
516 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs201sq.gif>

The best packing previously known has side length

s = 27.34520... and 183 contacts.

------------------------------------

N = 217
s = 28.18722319066969003557...
433 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs217sq.gif>

The best packing previously known has side length

s = 28.1872243... and 335 contacts.

------------------------------------

N = 305
s = 33.37432925564673306133...
798 contacts
symmetry group D_1
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs305sq.gif>

The best packing previously known has side length

s = 33.37448... and 788 contacts.

------------------------------------

N = 369
s = 36.57519035514512653662...
902 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs369sq.gif>

The best packing previously known has side length

s = 36.57526... and 860 contacts.

------------------------------------

David W. Cantrell

unread,

Jan 26, 2010, 10:58:32 AM1/26/10

New packings of N unit circles in squares are given for N = 104, 108, 109,
111, 119 and 121. Considering those new packings and ones which have
previously been given here, together with packings shown at Packomania now
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html> or previously, no
"best known" packings remain for N <= 125 which are obviously suboptimal.

[The reason I mentioned packings _previously_ shown at Packomania is that a
few of them are superior to the packings currently shown there. An example
is the packing for N = 112. Although the WayBack Machine does not archive
most figures, it does happen to show the former packing for N = 112:
<http://web.archive.org/web/20061002214626/hydra.nat.uni-magdeburg.de/packing/csq/csq112.html>
That packing has one more contact than the packing currently shown at
Packomania.]

Also, at the end of this post, I give a small correction concerning my
packing for N = 125.

------------------------------------

N = 104
s = 19.86144938456094210729486891404857016472...
213 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs104sq.gif>

The packing currently shown at Packomania has 193 contacts and side

length s agreeing, to all 30 significant digits shown there, with s
of my packing. Although I certainly suppose that my packing is an
improvement, I cannot say with absolute confidence that it is.

------------------------------------

N = 108
s = 20.30724010016632631294...
221 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs108sq.gif>

The best packing previously known has side length

s = 20.3072401024... and 183 contacts.

------------------------------------

N = 109
s = 20.38318078436717043300...
238 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs109sq.gif>

The best packing previously known has side length

s = 20.3831823... and 174 contacts.

------------------------------------

N = 111
s = 20.557546842294050860412503145517...
226 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs111sq.gif>

The best packing previously known has side length

s = 20.5575468422940508604125053... and 207 contacts.

------------------------------------

N = 119
s = 21.03286236289425250506...
284 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs119sq.gif>
a density record (that is, the packing's density is higher than that of any
packing for N < 119)

The best packing previously known has side length

s = 21.03286236297... and 181 contacts.

------------------------------------

N = 121
s = 21.32559941984783464179...
259 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs121sq.gif>

The best packing previously known has side length

s = 21.3255994198481... and 220 contacts.

------------------------------------

A small correction to my previous post:

>
> N = 125
> s = 21.74937318710201484469...

Correction:
309 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs125sq-1.gif>

My previously prepared figure failed to show a circle (#76 in
the corrected figure above) as being a rattler. Accordingly, the
number of required contacts had been incorrectly stated as 313.

> The best packing previously known has side length
> s = 21.74937318754... and 88 contacts.
>
> ------------------------------------

David W. Cantrell

unread,

Feb 5, 2010, 10:56:57 AM2/5/10

Improved packings of N unit circles in squares are given
for N = 215, 228 and 284.

------------------------------------

N = 215
s = 27.99955106210540550243...
558 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs215sq.gif>
A density record (that is, the packing's density is higher than that
of any packing for N < 215)

The best packing previously known has side length

s = 27.99961... and 178 contacts.

------------------------------------

N = 228
s = 29.12997818830754656951...
565 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs228sq.gif>

The best packing previously known has side length

s = 29.12997818881... and 557 contacts.

------------------------------------

N = 284
s = 32.40439359243483573552...
755 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs284sq.gif>

The best packing previously known has side length

s = 32.4050... and 707 contacts.

------------------------------------

David W. Cantrell

unread,

Feb 12, 2010, 10:53:26 PM2/12/10

Density records, regular packings and exact values are discussed. Also, an
improved packing is given for N = 408 and two small errors from previous
posts are corrected.

Eckard Specht shows packings that have been presented here, now through
N = 150, at Packomania:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html>
Updates for larger N will probably appear soon.

----------------------------------------------------------------

Density records, regular packings and exact values

A packing of N unit circles is a _density record_ if its density is higher
than that of any packing of fewer unit circles. In the following list of
density records, asterisks indicate packings which have appeared in this
thread or its predecessor:

N = 1, 30, 38, 39, 52, 67*, 68*, 99, 119*, 120, 186*, 187*, 188, 215, 216*,
303, 304, 339, 340, 407

I plan to extend <http://www.research.att.com/~njas/sequences/A051657>
accordingly in the near future.

In that list, the appearance of several pairs, such as (38, 39) and
(339, 340), as well as the triplet (186, 187, 188), is rather striking, but
it has a simple explanation. In each such group, the packing for the
largest N is very close to a hexagonal lattice packing, and thus has high
density. So high, in fact, that removing one circle (or two, when going
from 188 to 186) and then readjusting the packing for the smaller N, we
_still_ obtain a density record. Of course, it doesn't always happen that
way (e.g., N = 29, 51, 98 and 406 are not density records), but the
phenomenon occurs often enough to be notable.

By the way, the readjusting, mentioned above, may not be obvious. That is,
it may not be easy to optimize packings obtained in this way. For example,
if one looks at the current packings for N = 303 and 339 at Packomania,
it's obvious that they are not optimal. But it's not clear to me how those
packings should be structured for optimality.

Several of the density records are given by packings which, in a sense, are
"regular". And in these cases, we can give precise expressions for the side
length s of the square. In "The packing of equal circles in a square",
Math. Mag. 43:1 (1970) pp. 24-30, Michael Goldberg mentions the two most
prominent families of regular packings.

One family is obtained from a hexagonal lattice by the "shift method",
exemplified by packings for N = 30 and 340. A glance at
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq340.html> will make the
structure evident. There are also best known, but not density record,
packings in this family for N = 20, 42 and 143. Members of this family are
engendered by integer ratios which slightly overestimate sqrt(3) and have
odd numerators. Suppose that p/q is such an approximation. Then the side
length s of the square in which N = (p + 1)(q + 1)/2 unit circles may be
packed by the "shift method" is

s = (2 + q (q + p q + sqrt(4 q^2 + (3 - p)(1 + p))))/(1 + q^2)

Example: Since 9/5 is a bit larger than sqrt(3) and has an odd numerator,
by the "shift method", we can get a packing of N = (9 + 1)(5 + 1)/2 = 30
unit circles in a square of side length s = (126 + 5 sqrt(10))/13.

The other members of this family, N = 20, 42, 143 and 340, have the
associated fractions 7/4, 11/6, 21/12 and 33/19, resp. Note that the
fractions are not necessarily convergents of the continued fraction for
sqrt(3) and are not necessarily in lowest terms.

Another family is obtained from a hexagonal lattice by "compression",
exemplified by packings for N = 39, 52, 99, 120, 188 and 304. A glance at
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq188.html> will make the
structure evident. Members of this family are engendered by integer ratios
which slightly underestimate sqrt(3). Suppose that p/q is such an
approximation. Then the side length s of the square in which N unit circles
may be packed by "compression" is

s = 2 ( 1 + p / sqrt(1 + (p/q)^2) )

where,

if p or q is odd, N = (p + 1)(q + 1)/2
if p and q are both even, N = ((p + 1)(q + 1) + 1)/2.

Example: Since 24/14 is a bit smaller than sqrt(3), by "compression", we
can get a packing of N = ((24 + 1)(14 + 1) + 1)/2 = 188 unit circles in a
square of side length s = 2 + 336/sqrt(193).

The other members of this family, N = 39, 52, 99, 120 and 304, have the
associated fractions 10/6, 12/7, 17/10, 19/11 and 31/18, resp.

[I do not know if the general formulae above have appeared in the
literature, but they are not given by Goldberg.]

There are somewhat less regular packings, not considered by Goldberg, for
which exact values can also be given. For example, one of my favorite
packings, visually speaking, is that for N = 407:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq407.html>,
which has side length precisely

s = 2/193 * (487 + 504 sqrt(3) + 42 sqrt(2797 + 168 sqrt(3)))

By the way, N = 407 would seem to be a good candidate for a simpler
packing, just using "compression", since 36/21 is a bit smaller than
sqrt(3). But the side length obtained that way is 2 + 504/sqrt(193), about
0.00047% larger than that of the presumably optimal packing.

A similar example, but having larger hexagonal lattice clumps, is the
packing for N = 80:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq80.html>, which has side
length precisely s = 1/17 * (79 + 75 sqrt(3) + 15 sqrt(30 sqrt(3) - 18)).
Goldberg suggested the packing obtained by uniform compression for N = 80,
but the side length obtained that way is 2 + 45/sqrt(2/17), about 0.025%
larger than that of the presumably optimal packing.

Question: Is there a way to predict when some sort of hexagonal lattice
clumping will give a packing which is superior to that obtained by
uniform compression?

----------------------------------------------------------------

Closely related to the packing for N = 407 is an improved packing for
N = 408. It is also visually appealing and has hexagonal lattice groupings.

N = 408
s = 38.46859362531026410351...
909 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs408sq.gif>

The best packing previously known has side length

s = 38.4691... and 663 contacts.

----------------------------------------------------------------

Two errata for previously posted packings:

For N = 104, the number of contacts should be 207, instead of 213.

For N = 136, the number of contacts should be 272, instead of 270.

----------------------------------------------------------------

David W. Cantrell

Phil Carmody

unread,

Feb 13, 2010, 7:13:35 PM2/13/10

David W. Cantrell <DWCan...@sigmaxi.net> writes:

> Density records, regular packings and exact values are discussed.

David,

Has anyone ever looked at packing unit circles in their convex hull?
(Which of course makes the idea of density records rather silly!)

David W. Cantrell

unread,

Feb 13, 2010, 9:37:08 PM2/13/10

Phil Carmody <thefatphi...@yahoo.co.uk> wrote:
> David W. Cantrell <DWCan...@sigmaxi.net> writes:
> > Density records, regular packings and exact values are discussed.
>
> David,
>
> Has anyone ever looked at packing unit circles in their convex hull?

Yes. You might use "penny packing problem" and "sausage conjecture" as
search terms.

> (Which of course makes the idea of density records rather silly!)

Indeed, because, for N = 1, the density is 1!

BTW, Eckard has now updated Packomania through N = 200 with packings which
have appeared in this thread.

David

Phil Carmody

unread,

Feb 16, 2010, 3:54:27 AM2/16/10

David W. Cantrell <DWCan...@sigmaxi.net> writes:
> Phil Carmody <thefatphi...@yahoo.co.uk> wrote:
>> David W. Cantrell <DWCan...@sigmaxi.net> writes:
>> > Density records, regular packings and exact values are discussed.
>>
>> David,
>>
>> Has anyone ever looked at packing unit circles in their convex hull?
>
> Yes. You might use "penny packing problem" and "sausage conjecture" as
> search terms.

Now "sausage conjecture" indeed does ring a bell. I'll go and see
what teh internets provide - cheers!

Phil
(Hmmm, higher dimensions, woh...)

David W. Cantrell

unread,

Feb 23, 2010, 1:06:10 AM2/23/10

Eckard Specht has recently made several updates to
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html>.
Several of the improved packings are from Simon Gravel's dissertation,
Jan. 2009: <https://wiki.uni-koeln.de/q-bio/images/b/b6/Thesis_red.pdf>.

Two of his packings are of special interest here.
1. The packing for N = 136 (with symmetry group D_1), which I presented in
this thread, had been found earlier by Gravel.
2. He gives, as a new and improved packing, a regular packing for N = 161,
a member of the family of packings obtained by the compression method,
discussed here previously. I was initially shocked to think that a regular
packing had somehow been overlooked! But then I consulted Goldberg's paper
again, and found that Goldberg had not overlooked it. Thus, Goldberg (or
maybe someone before him), rather than Gravel, gets credit for that
packing. But that made me think that we should make sure that no regular
packings in the shift or compression families had been overlooked, and so I
wrote two short programs in Mathematica. They are given below, along with
their outputs showing all members of the families for N < 1000. (Curiously,
Goldberg himself seems to have overlooked a member of the shift family, the
presumably optimal packing for N = 56.)

David W. Cantrell <DWCan...@sigmaxi.net> wrote:

...

> Several of the density records are given by packings which, in a sense,
> are "regular". And in these cases, we can give precise expressions for
> the side length s of the square. In "The packing of equal circles in a
> square", Math. Mag. 43:1 (1970) pp. 24-30, Michael Goldberg mentions the
> two most prominent families of regular packings.
>
> One family is obtained from a hexagonal lattice by the "shift method",
> exemplified by packings for N = 30 and 340. A glance at
> <http://hydra.nat.uni-magdeburg.de/packing/csq/csq340.html> will make the
> structure evident. There are also best known, but not density record,
> packings in this family for N = 20, 42 and 143.

And also N = 56.

And there are other members for smaller N; see program output below.

> [I do not know if the general formulae above have appeared in the
> literature, but they are not given by Goldberg.]

Each line of output has the form {N, s}, where N is the number of unit
circles packed in a square of side length s. If a packing for N is known
which is better than the packing obtained by the shift or compression
method, I have added # at the beginning of the appropriate line.
(For N > 420, I have no information about better packings.)

--------------------------------------

Shift method:

Do[p = Ceiling[q*Sqrt[3]]; If[OddQ[p], Print[{((p + 1)*(q + 1))/2,
(2 + q*(q + p*q + Sqrt[4*q^2 + (3 - p)*(1 + p)]))/(1 + q^2)}]], {q, 1, 33}]

{20, (1/17)*(2 + 4*(32 + 4*Sqrt[2]))}
{30, (1/26)*(2 + 5*(50 + 2*Sqrt[10]))}
{42, (1/37)*(2 + 6*(72 + 4*Sqrt[3]))}
{56, (1/50)*(2 + 7*(98 + 2*Sqrt[14]))}
{143, (1/145)*(2 + 12*(264 + 6*Sqrt[5]))}
# {168, 424/17}
# {195, (1/197)*(2 + 14*(364 + 2*Sqrt[53]))}
{340, (1/362)*(2 + 19*(646 + 2*Sqrt[106]))}
# {378, (1/401)*(2 + 20*(720 + 8*Sqrt[7]))}
# {418, (1/442)*(2 + 21*(798 + 2*Sqrt[118]))}
{460, (1/485)*(2 + 22*(880 + 4*Sqrt[31]))}
{672, (1/730)*(2 + 27*(1296 + 2*Sqrt[201]))}
{725, (1/785)*(2 + 28*(1400 + 2*Sqrt[209]))}
{780, (1/842)*(2 + 29*(1508 + 2*Sqrt[217]))}

--------------------------------------

Compression method:

Do[p = Floor[q*Sqrt[3]]; Print[{Ceiling[((p + 1)*(q + 1))/2],
2 + (2*p*q)/Sqrt[p^2 + q^2]}], {q, 1, 33}]

{2, 2 + Sqrt[2]}
{6, 2 + 12/Sqrt[13]}
{12, 2 + 15*Sqrt[2/17]}
{18, 2 + 24/Sqrt[13]}
{27, 2 + 80/Sqrt[89]}
{39, 2 + 30*Sqrt[2/17]}
{52, 2 + 168/Sqrt[193]}
# {63, 2 + 208/Sqrt[233]}
# {80, 2 + 45*Sqrt[2/17]}
{99, 2 + 340/Sqrt[389]}
{120, 2 + 209*Sqrt[2/241]}
# {137, 2 + 60*Sqrt[2/17]}
{161, 2 + 572/Sqrt[653]}
{188, 2 + 336/Sqrt[193]}
# {208, 2 + 75*Sqrt[2/17]}
# {238, 2 + 864/Sqrt[985]}
# {270, 2 + 493*Sqrt[2/565]}
{304, 2 + 1116/Sqrt[1285]}
# {330, 2 + 1216/Sqrt[1385]}
# {368, 2 + 680/Sqrt[389]}
# {407, 2 + 504/Sqrt[193]}
{449, 2 + 418*Sqrt[2/241]}
{480, 2 + (897*Sqrt[2/41])/5}
{525, 2 + 1968/Sqrt[2257]}
{572, 2 + 1075*Sqrt[2/1237]}
{621, 2 + 2340/Sqrt[2701]}
{658, 2 + 2484/Sqrt[2845]}
{711, 2 + 672/Sqrt[193]}
{765, 2 + 2900/Sqrt[3341]}
{806, 2 + 1020/Sqrt[389]}
{864, 2 + 1643*Sqrt[2/1885]}
{924, 2 + 3520/Sqrt[4049]}
{986, 2 + 627*Sqrt[2/241]}

--------------------------------------

David W. Cantrell

unread,

Feb 25, 2010, 4:37:20 PM2/25/10

Improved packings of N unit circles in squares are given

for N = 129, 134, 135, 145, 146 and 147.

David W. Cantrell <DWCan...@sigmaxi.net> wrote:
> Eckard Specht has recently made several updates to
> <http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html>.
> Several of the improved packings are from Simon Gravel's dissertation,
> Jan. 2009: <https://wiki.uni-koeln.de/q-bio/images/b/b6/Thesis_red.pdf>.

------------------------------------

N = 129
s = 22.12372197365219569195...
272 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs129sq.gif>

The best packing previously known has side length

s = 22.123721973660... and 271 contacts.

------------------------------------

N = 134
s = 22.43953124014779172782...
316 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs134sq.gif>

The best packing previously known has side length

s = 22.439531250... and 180 contacts.

------------------------------------

N = 135
s = 22.50670793898583824805...
271 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs135sq.gif>

The best packing previously known has side length

s = 22.5067086... and 245 contacts.

------------------------------------

N = 145
s = 23.32559772340654025757...
310 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs145sq-1.gif>

The best packing previously known has side length

s = 23.325597723492... and 271 contacts.

------------------------------------

N = 146
s = 23.44720899809523608137...
337 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs146sq.gif>

The best packing previously known has side length

s = 23.44736... and 284 contacts.

------------------------------------

N = 147
s = 23.55886093645637737384...
327 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs147sq-1.gif>

The best packing previously known has side length

s = 23.5588612... and 291 contacts.

------------------------------------

David W. Cantrell

unread,

Mar 6, 2010, 3:52:05 PM3/6/10

Improved packings of N unit circles in squares are given for N = 126, 134,
136, 144, 146, 147, 148, 150, 162, 182, 184, 186 and 200.

[For some N, the new packings improve on packings which have previously
appeared in this thread. In those cases, images of the former packings have
been removed from Photobucket.]

------------------------------------

N = 126
s = 21.82038057977262291707...
253 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs126sq.gif>

The best packing previously known has side length

s = 21.8203805797747... and 211 contacts.

------------------------------------

N = 134
s = 22.43951440859127651379...
305 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs134sq.gif>

The best packing previously known has side length

s = 22.439514410... and 288 contacts.

------------------------------------

N = 136
s = 22.54623538447418850987...
274 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs136sq.gif>

The best packing previously known has side length

s = 22.5462353876... and 254 contacts.

------------------------------------

N = 144
s = 23.25377764729427359117...
328 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs144sq.gif>

The best packing previously known has side length

s = 23.25377764744... and 327 contacts.

------------------------------------

N = 146
s = 23.44595183416430866615...
332 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs146sq.gif>

The best packing previously known has side length

s = 23.44595183432... and 313 contacts.

------------------------------------

N = 147
s = 23.55879573345756349149...
330 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs147sq.gif>

The best packing previously known has side length

s = 23.55879573379... and 313 contacts.

------------------------------------

N = 148
s = 23.62378419382255757394...
366 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs148sq.gif>

The best packing previously known has side length

s = 23.62378419396... and 324 contacts.

------------------------------------

N = 150
s = 23.72734477154064696804...
328 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs150sq.gif>

The best packing previously known has side length

s = 23.72734477165... and 325 contacts.

------------------------------------

N = 162
s = 24.51033700919874299136...
371 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs162sq.gif>

The best packing previously known has side length

s = 24.510337009202... and 370 contacts.

------------------------------------

N = 182
s = 26.02968150743656940075...
445 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs182sq.gif>

The best packing previously known has side length

s = 26.029681510... and 441 contacts.

------------------------------------

N = 184
s = 26.12216048097550810888...
471 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs184sq.gif>

The best packing previously known has side length

s = 26.1221604809770... and 454 contacts.

------------------------------------

N = 186
s = 26.15480637842980606382...
374 contacts

symmetry group C_2
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs186sq.gif>

The best packing previously known has side length
s = 26.1548063784298060685... and 365 contacts.

------------------------------------

N = 200
s = 27.31285315351670207687...
477 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs200sq.gif>

The best packing previously known has side length

s = 27.312853153534... and 468 contacts.

------------------------------------

David W. Cantrell

unread,

Mar 9, 2010, 1:10:31 PM3/9/10

Improved packings of N unit circles in squares are given for N = 152, 154,
166 and 173.

(And a small erratum: For my previously shown packing for N = 160,
the number of contacts is 365, rather than 366.)

------------------------------------

N = 152
s = 23.935009864033880512699314789048...
376 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs152sq.gif>

The best packing previously known has side length

s = 23.93500986403388051269931480... and 372 contacts.

------------------------------------

N = 154
s = 24.06627089498421638775...
381 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs154sq.gif>

The best packing previously known has side length

s = 24.0662708957... and 371 contacts.

------------------------------------

N = 166
s = 24.85229804804314606396...
358 contacts
symmetry group C_2
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs166sq.gif>

The best packing previously known has side length

s = 24.852298048043160... and 350 contacts.

------------------------------------

N = 173
s = 25.47671165946821729156...
370 contacts
symmetry group D_1
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs173sq.gif>

The best packing previously known has side length

s = 25.476711659476... and 349 contacts.

------------------------------------

David W. Cantrell

unread,

Apr 25, 2010, 10:43:05 AM4/25/10

Improved packings of N unit circles in squares are given for N = 67,
135 and 149. With those improvements: For N <= 150, no packings

remain which are obviously suboptimal.

We also discuss, following the new packing for N = 67, a problem
which arises when only numerics are used to determine whether
circles touch.

------------------------------------

N = 67
s = 15.97764930297533545113885511637259843819916521187...
136 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/
circs67sq.gif>

The best packing previously known is one which was posted earlier
in this thread. Its side length is larger than that of the new packing
by 7.7 * 10^-47. It has the same number of contacts as the new
packing.

------------------------------------

A problem with numerically determining whether circles touch

Example 1 (N = 160):

Consider the second figure at
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq160.html>,
showing a packing of 160 unit circles in a square. Circles #114,
120, 121, 129 and 135 are all depicted as being part of
a hexagonal lattice. Yet circle #128 is shown as touching both
circles #120 and 135, but _not_ touching circles #114 and 121.
This is a geometric impossibility! No such packing can exist.
If circles #114, 120, 121, 129 and 135 were all truly in a
hexagonal lattice and circle #128 touches both circles #120
and 135, then circle #128 would necessarily also touch circles
#114 and 121.

The cause of the problem:
In fact, circle #135 is not actually part of the hexagonal lattice
which includes circles #114, 120, 121 and 129. Rather, circle #135 is
very slightly separated from circle #129 (and thus the total number
of contacts is 365, instead of 366). Eckard's program, which I believe
currently uses 30 significant digits, considered unit circles #129
and 135 as touching because the distance between them is so small:
roughly 2 * 10^-36.

To solve this problem for this packing with N = 160, one could, of
course, use more significant digits. But presumably, for general N,
using any fixed number of significant digits will be inadequate to
determine precisely which circles touch or not.

Example 2 (N = 67):

<http://hydra.nat.uni-magdeburg.de/packing/csq/csq67.html>
currently shows my previous packing for N = 67. Note that
circle #40, shown in cyan, is indicated as having only two
contacts. But of course, any circle having only two contacts could be
repositioned so that it has no contacts, that is, it must actually be
a "rattler". And since, when counting the total number of contacts in
a packing, it is desirable and customary that only _necessary_
contacts be counted, the number of contacts in my previous packing is
actually 136, rather than 138. Of course, the source of the problem is
the same as in example 1. But here the consequence of the problem is
less severe, merely incorrectly inflating the number of contacts,
rather than producing a geometric impossibility.

My new packing for N = 67, which has a different circle as a rattler,
will again have its number of contacts incorrectly inflated if 30
significant digits are used. If the rattler near the right side of the
square (circle #55 in my figure at the Photobucket link above) were
positioned to maximize its distance from the three nearest unit
circles, that distance would be only about 2 * 10^-44. Using 30
significant digits, not only would the number of contacts be inflated
by three, but the rattler would be shown as being fixed (having three
spurious contacts) and thus lead to another geometric impossibility.
Instead, in the data which I will send to Eckard, I will position that
rattler so that, just as for my previous packing for N = 67 as shown
at Packomania, using 30 significant digits will cause only two
unnecessary contacts to be indicated.

The moral:
For my packings, the figures given in the links in this thread
(together with the number of contacts reported here) should be
considered definitive. Of course I hope that, eventually, the
information at Packomania will be in complete agreement with the
information in this thread. But that may not be achieved easily or
soon.

------------------------------------

N = 135
s = 22.50670793867788263154...
261 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/
circs135sq.gif>

The best packing previously known has side length

s = 22.506707938691... and 241 contacts.

------------------------------------

N = 149
s = 23.66759560234166323610...
328 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/
circs149sq.gif>

The best packing previously known has side length

s = 23.66759582... and 282 contacts.

------------------------------------

David W. Cantrell

unread,

Apr 25, 2010, 5:44:31 PM4/25/10

Improved packings of N unit circles in squares are given for N = 151,
153 and 155-158.

Earlier today, I had written:

> Improved packings of N unit circles in squares are given for N = 67,
> 135 and 149. With those improvements: For N <= 150, no packings
> remain which are obviously suboptimal.
>
> We also discuss, following the new packing for N = 67, a problem
> which arises when only numerics are used to determine whether
> circles touch.
>
> ------------------------------------
>
> N = 67
> s = 15.97764930297533545113885511637259843819916521187...
> 136 contacts
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs67sq.gif>
>
> The best packing previously known is one which was posted earlier

> in this thread. Its side length s is larger than that of the new packing

> by 7.7 * 10^-47. It has the same number of contacts as the new
> packing.
>
> ------------------------------------
>
> A problem with numerically determining whether circles touch

More examples of this problem are noted below, when discussing the new
packings for N = 155 and 157.

N = 151
s = 23.82251439160247719965...
359 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs151sq.gif>

The best packing previously known has side length

s = 23.8225143937... and 319 contacts.

------------------------------------

N = 153
s = 24.01021876668148648296...
353 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs153sq.gif>

The best packing previously known has side length

s = 24.01021876673... and 319 contacts.

------------------------------------

N = 155
s = 24.13241594484677182538...
358 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs155sq.gif>
(Note: In the figure above, the distance between unit circles #106 and
118 is sufficiently small, only about 2 * 10^-29, that, when this packing
appears at Packomania, those circles might be shown as touching, with the
total number of contacts being given as 359.)

The best packing previously known has side length

s = 24.1324159487... and 295 contacts.

------------------------------------

N = 156
s = 24.21344528296218157944...
369 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs156sq.gif>

The best packing previously known has side length

s = 24.2134452832... and 368 contacts.

------------------------------------

N = 157
s = 24.25986239435024781231...
365 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs157sq.gif>
(Note: In the figure above, circle #128 is a rattler. But, regardless
of how it is positioned, the distances between it and five nearby circles
are so small that, using 30 significant digits, it will seem to touch the
five nearby circles. Thus it can be expected that, when this packing
appears at Packomania, that rattler will be shown as fixed and the total
number of contacts will be given as 370.)

The best packing previously known has side length

s = 24.25986239455... and 313 contacts.

------------------------------------

N = 158
s = 24.295613378688153058231782520700...
315 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs158sq.gif>

The best packing previously known has side length

s = 24.29561337868815305823178270... and 292 contacts.

------------------------------------

David W. Cantrell

christian.bau

unread,

Apr 25, 2010, 5:45:52 PM4/25/10

On Apr 25, 10:44 pm, David W. Cantrell <DWCantr...@sigmaxi.net> wrote:

Out of curiosity: These packings are obviously quite hard to find. Has
anyone tried, either for real or using some simulation, how close to
these results one would get with purely mechanical models? For
example, you mention N = 158, s = 24.295613378688153058231782520700...
If I took 158 very smooth coins with a radius of 1 cm, and built a box
of side s = 24.3, height 50 cm, and a moveable lid, and then I pressed
the lid down, would I have a decent chance to fit all the coins into a
box of 24.3 x 24.3? What if I press the lid down and simultaneously
shake the box? Or if I build a square box with two moveable sides that
move simultaneously, so that the box is always square. Would I come
close to your best result, or would I have to be very lucky to come
anywhere near?

Say I build a square box of size 50 x 50, put 158 coins inside at
random positions, and slowly move the left and top side
simultaneously, so that the coins move according to the laws of
physics, until nothing moves. What size would I end up with?

ThomasCR

unread,

Apr 26, 2010, 11:52:52 AM4/26/10

On Apr 25, 11:44 pm, David W. Cantrell <DWCantr...@sigmaxi.net> wrote:
> Improved packings of N unitcirclesin squares are given for N = 151,

> 153 and 155-158.
>
> Earlier today, I had written:
>
>
>

> > Improved packings of N unitcirclesin squares are given for N = 67,

> > 135 and 149. With those improvements: For N <= 150, no packings
> > remain which are obviously suboptimal.
>

> > We also discuss, following the newpackingfor N = 67, a problem

> > which arises when only numerics are used to determine whether
> >circlestouch.
>
> > ------------------------------------
>
> > N = 67
> > s = 15.97764930297533545113885511637259843819916521187...
> > 136 contacts

> > <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs67...>
>
> > The bestpackingpreviously known is one which was posted earlier

> > in this thread. Its side length s is larger than that of the newpacking
> > by 7.7 * 10^-47. It has the same number of contacts as the new
> >packing.
>
> > ------------------------------------
>
> > A problem with numerically determining whethercirclestouch
>
> More examples of this problem are noted below, when discussing the new
> packings for N = 155 and 157.
>
>
>
> > Example 1 (N = 160):
>
> > Consider the second figure at
> > <http://hydra.nat.uni-magdeburg.de/packing/csq/csq160.html>,
> > showing apackingof 160 unitcirclesin a square.Circles#114,
> > 120, 121, 129 and 135 are all depicted as being part of
> > a hexagonal lattice. Yet circle #128 is shown as touching both

> >circles#120 and 135, but _not_ touchingcircles#114 and 121.

> > This is a geometric impossibility! No suchpackingcan exist.

> > Ifcircles#114, 120, 121, 129 and 135 were all truly in a

> > hexagonal lattice and circle #128 touches bothcircles#120
> > and 135, then circle #128 would necessarily also touchcircles
> > #114 and 121.
>
> > The cause of the problem:
> > In fact, circle #135 is not actually part of the hexagonal lattice

> > which includescircles#114, 120, 121 and 129. Rather, circle #135 is

> > very slightly separated from circle #129 (and thus the total number
> > of contacts is 365, instead of 366). Eckard's program, which I believe
> > currently uses 30 significant digits, considered unitcircles#129
> > and 135 as touching because the distance between them is so small:
> > roughly 2 * 10^-36.
>

> > To solve this problem for thispackingwith N = 160, one could, of

> > course, use more significant digits. But presumably, for general N,
> > using any fixed number of significant digits will be inadequate to

> > determine precisely whichcirclestouch or not.

>
> > Example 2 (N = 67):
>
> > <http://hydra.nat.uni-magdeburg.de/packing/csq/csq67.html>

> > currently shows my previouspackingfor N = 67. Note that

> > circle #40, shown in cyan, is indicated as having only two
> > contacts. But of course, any circle having only two contacts could be
> > repositioned so that it has no contacts, that is, it must actually be
> > a "rattler". And since, when counting the total number of contacts in

> > apacking, it is desirable and customary that only _necessary_

> > contacts be counted, the number of contacts in my previouspackingis
> > actually 136, rather than 138. Of course, the source of the problem is
> > the same as in example 1. But here the consequence of the problem is
> > less severe, merely incorrectly inflating the number of contacts,
> > rather than producing a geometric impossibility.
>

> > My newpackingfor N = 67, which has a different circle as a rattler,

> > will again have its number of contacts incorrectly inflated if 30
> > significant digits are used. If the rattler near the right side of the
> > square (circle #55 in my figure at the Photobucket link above) were
> > positioned to maximize its distance from the three nearest unit
> >circles, that distance would be only about 2 * 10^-44. Using 30
> > significant digits, not only would the number of contacts be inflated
> > by three, but the rattler would be shown as being fixed (having three
> > spurious contacts) and thus lead to another geometric impossibility.
> > Instead, in the data which I will send to Eckard, I will position that

> > rattler so that, just as for my previouspackingfor N = 67 as shown

> > at Packomania, using 30 significant digits will cause only two
> > unnecessary contacts to be indicated.
>
> > The moral:
> > For my packings, the figures given in the links in this thread
> > (together with the number of contacts reported here) should be
> > considered definitive. Of course I hope that, eventually, the
> > information at Packomania will be in complete agreement with the
> > information in this thread. But that may not be achieved easily or
> > soon.
>
> > ------------------------------------
>
> > N = 135
> > s = 22.50670793867788263154...
> > 261 contacts

> > <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs13...>
>
> > The bestpackingpreviously known has side length

> > s = 22.506707938691... and 241 contacts.
>
> > ------------------------------------
>
> > N = 149
> > s = 23.66759560234166323610...
> > 328 contacts

> > <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs14...>
>
> > The bestpackingpreviously known has side length

> > s = 23.66759582... and 282 contacts.
>
> > ------------------------------------
>
> N = 151
> s = 23.82251439160247719965...
> 359 contacts

> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs15...>
>
> The bestpackingpreviously known has side length

> s = 23.8225143937... and 319 contacts.
>
> ------------------------------------
>
> N = 153
> s = 24.01021876668148648296...
> 353 contacts

> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs15...>
>
> The bestpackingpreviously known has side length

> s = 24.01021876673... and 319 contacts.
>
> ------------------------------------
>
> N = 155
> s = 24.13241594484677182538...
> 358 contacts

> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs15...>
> (Note: In the figure above, the distance between unitcircles#106 and

> 118 is sufficiently small, only about 2 * 10^-29, that, when thispacking

> appears at Packomania, thosecirclesmight be shown as touching, with the

> total number of contacts being given as 359.)
>

> The bestpackingpreviously known has side length

> s = 24.1324159487... and 295 contacts.
>
> ------------------------------------
>
> N = 156
> s = 24.21344528296218157944...
> 369 contacts

> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs15...>
>
> The bestpackingpreviously known has side length

> s = 24.2134452832... and 368 contacts.
>
> ------------------------------------
>
> N = 157
> s = 24.25986239435024781231...
> 365 contacts

> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs15...>

> (Note: In the figure above, circle #128 is a rattler. But, regardless
> of how it is positioned, the distances between it and five nearbycircles
> are so small that, using 30 significant digits, it will seem to touch the

> five nearbycircles. Thus it can be expected that, when thispacking

> appears at Packomania, that rattler will be shown as fixed and the total
> number of contacts will be given as 370.)
>

> The bestpackingpreviously known has side length

> s = 24.25986239455... and 313 contacts.
>
> ------------------------------------
>
> N = 158
> s = 24.295613378688153058231782520700...
> 315 contacts

> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs15...>
>
> The bestpackingpreviously known has side length

> s = 24.29561337868815305823178270... and 292 contacts.
>
> ------------------------------------
>
> David W. Cantrell

Some new results with a new packing program at http://critticall.com/SQU_cir.html

David W. Cantrell

unread,

Apr 27, 2010, 11:24:41 AM4/27/10

"christian.bau" <christ...@cbau.wanadoo.co.uk> wrote:

> On Apr 25, 10:44=A0pm, David W. Cantrell <DWCantr...@sigmaxi.net> wrote:
>
> Out of curiosity: These packings are obviously quite hard to find. Has
> anyone tried, either for real or using some simulation, how close to
> these results one would get with purely mechanical models?

Hello, Christian,

Yes, such simulations have certainly been used.

> For example, you mention N = 158,
> s = 24.295613378688153058231782520700... If I took 158 very smooth coins
> with a radius of 1 cm, and built a box of side s = 24.3, height 50 cm,
> and a moveable lid, and then I pressed the lid down, would I have a
> decent chance to fit all the coins into a box of 24.3 x 24.3?

That depends on what you consider to be a "decent chance". But even if you
specified that, I don't know the answer. My guess is that the chance would
be indecent. :-)

> What if I press the lid down and simultaneously shake the box?

Of course, that would improve your chance considerably. There are computer
programs which simulate that.

Only a few days ago did I finally get a copy of _New Approaches to Circle
Packing in a Square_, P.G. Szabo et al. (Springer, 2007). Once I've had a
chance to digest certain parts of it, I'll be making comments about it in
this thread. But now concerning your question:

p. 44
5.3 Billiard simulation
This method was used by Graham and Lubachevsky, for example.

p. 45
5.4 Pulsating Disk Shaking (PDS) algorithm
"... it is well known that good packings were achieved in 3D by real
physical shaking of balls. Thus the PDS algorithm itself is based on a more
physically motivated 'shake-and-rattle' concept." (BTW, the book includes a
CD containing code for this algorithm.)

> Or if I build a
> square box with two moveable sides that move simultaneously, so that the
> box is always square. Would I come close to your best result, or would I
> have to be very lucky to come anywhere near?

Again, I don't really know the answer. But I'd guess that, with many
trials, you might have a good chance.

> Say I build a square box of size 50 x 50, put 158 coins inside at
> random positions, and slowly move the left and top side
> simultaneously, so that the coins move according to the laws of
> physics, until nothing moves. What size would I end up with?

Again, I don't really know.

Cheers,
David

David W. Cantrell

unread,

Apr 28, 2010, 5:01:30 PM4/28/10

ThomasCR <protok...@gmail.com> wrote:
> Some new results with a new packing program at
> <http://critticall.com/SQU_cir.html>

Many thanks, Thomas, for that link!

(I don't know if you are associated with that web page or not. But in any
event, I am also sending a copy of this to Nevenka Kristan.)

There is a particular reason that I'm delighted with some of the new
results on that web page:

On Mar. 7, 2009, in this newsgroup, I conjectured an upper bound for the
inradius r of the smallest square into which N unit circles could be
packed. Recast in terms of the side length s, my conjectured upper bound is

(#) s <= (c1 + sqrt(4 sqrt(3) N (9 + 4 sqrt(2)) + c2))/(4 + sqrt(2))

where constants c1 = 5 + 3 sqrt(2) - 2 sqrt(3) and
c2 = 55 + 30 sqrt(2) - 52 sqrt(3) - 20 sqrt(6).

At that time, Packomania gave packings continuously up to N = 300. Of those
packings, only N = 251, 253, 257 and 258 violated (#).

In the meantime, although I did look for packings for those four N values
which would satisfy (#), I didn't consider finding such packings to be a
high priority because I felt confident that such packings would eventually
be found. However, I did happen to find packings for N = 253 and 258 which
satisfied (#) but hadn't gotten around to posting them here yet. But
anyway, the above link now shows that Critticall has found packings for
N = 257 and 258 which satisfy (#), and its packing for N = 258 is better
than mine. Below, I now give my packing for N = 253, and so that leaves
N = 251 as the only case for N <= 300 for which a packing satisfying (#)
has yet to be found.

------------------------------------

N = 253
s = 30.59239739099812868316...
669 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs253sq.gif>

According to (#), we needed to have
s <= 30.6476... But the best packing previously known had side length
s = 30.6534... and 637 contacts.

------------------------------------

Packomania has also been extended in the meantime, now giving packings
continuously up to N = 420. The only packings there for 300 < N <= 420
which do not satisfy (#) are N = 354, 355, 390, 391, 392 and 420.

Of course I would be particularly interested to see if Critticall (or some
other program or person) could find packings for N = 251, 354, 355, 390,
391, 392 and 420 which satisfy (#).

[In the interest of "full disclosure", perhaps I should note that I
actually already have packings which satisfy (#) for a few of those N. But
none of those packings are optimized yet. As an example, for N = 390,
according to (#), we should have s <= 37.803... The packing currently shown
at Packomania has s = 37.818... My figure
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs390sq.gif>
has s = 37.738, using three large hexagonal lattice groupings.]

Recently, responding here to Christian Bau, I said that

> Only a few days ago did I finally get a copy of _New Approaches to Circle
> Packing in a Square_, P.G. Szabo et al. (Springer, 2007). Once I've had a
> chance to digest certain parts of it, I'll be making comments about it in
> this thread.

Well, it happens that they give some proven bounds. I will be quite
interested to see how those relate to my conjectured bounds. I hope to post
a comparison here soon!

Best regards,
David W. Cantrell

ThomasCR

unread,

Apr 29, 2010, 10:06:18 AM4/29/10

Hi David!

Yes I am associateed with that site, as Nevenka Kristan is also. Check
www.algit.eu also. In 24 hours you will see the new (better) result
for the 251 circles in a square. We will let it calculate some more,
despite the fact, that we already have a new result.

Best regards, Tomaž Kristan

(hum ... I have ThomasCR Google account but also much better Thomas
Google account but I have to retrieve the password somehow ... never
mind ...)

ThomasCR

unread,

Apr 30, 2010, 11:34:03 AM4/30/10

The result of 251 circles is up.

http://critticall.com/SQU_cir.html

at the bottom.

Check it out.

Besides, you can download, install and run the software Packntile.exe.

Every (new best) result is scrambled, but we can unscramble it, if you
send it to my mail. We will publish it along with your name.

Another option is, if you register the version. This way you can
IMPROVE any old result further.

In any case, the tool is powerful.

Best regards,

Thomas

David W. Cantrell

unread,

May 1, 2010, 11:44:56 AM5/1/10

ThomasCR <protok...@gmail.com> wrote:
> The result of 251 circles is up.
>
> <http://critticall.com/SQU_cir.html>
>
> at the bottom.
>
> Check it out.

Congratulations! And many thanks!
Now, for all N < 354, we know packings which obey my conjectured upper
bound

(#) s <= (c1 + sqrt(4 sqrt(3) N (9 + 4 sqrt(2)) + c2))/(4 + sqrt(2))

where constants c1 = 5 + 3 sqrt(2) - 2 sqrt(3) and
c2 = 55 + 30 sqrt(2) - 52 sqrt(3) - 20 sqrt(6).

In a previous response to you, I said

> Recently, responding here to Christian Bau, I said that
>> Only a few days ago did I finally get a copy of _New Approaches
>> to Circle Packing in a Square_, P.G. Szabo et al. (Springer, 2007).
>> Once I've had a chance to digest certain parts of it, I'll be
>> making comments about it in this thread.
>
> Well, it happens that they give some proven bounds. I will be quite
> interested to see how those relate to my conjectured bounds. I hope
> to post a comparison here soon!

That comparison of bounds will be posted in a few days. However, since one
of their bounds is based on certain families of packings, it makes sense to
mention those families first, relating them to the two packing families,
compression and shift, which I had discussed previously in this thread.
This will probably appear here later today or tomorrow.

David W. Cantrell

unread,

May 2, 2010, 12:47:03 PM5/2/10

We discuss how the two families of packings, mentioned here earlier,
are related to patterns discussed in _New Approaches to Circle Packing
in a Square_. An existing conjecture concerning an infinite subfamily
of optimal packings in the compression family is broadened, and
another conjecture, perhaps new, concerning an infinite subfamily of
optimal packings in the shift family is presented. (For readers'
convenience, previous comments about the compression and shift families
are copied below my signature.)

-------------------------------------------------

In _New Approaches to Circle Packing in a Square_ (NACPS), P.G. Szabo et
al. (Springer, 2007), several more packing families are discussed than the
two I had mentioned here. Those two families interested me because they
seemed to have the potential to contain infinitely many optimal packings. I
had not considered other families because I assumed that each of them would
contain only finitely many optimal packings. Although that assumption
appears to be correct, I had not noticed that considering such families
could still be useful in obtaining a bound for the packings. (Readers
interested in specifics of those other families may refer to section 10.1,
Finite pattern classes, pp. 113-130 in NACPS.)

-------------------------------------------------

The Compression Family and a Broadened Conjecture

The family of packings obtained by compressing a hexagonal lattice
packing, as discussed here previously, includes some members of
two pattern classes, PAT_1(k(k + 1)) and PAT(k^2 + floor(k/2)),
discussed in section 10.1 of NACPS. But more significantly, the
compression family is closely related to the discussion in their
section 10.2, A conjectured infinite pattern class. Due to my lack of
familiarity with the literature, it is hardly surprising that what I had
presented here about the compression family is very similar to previously
published work; see the 1999 paper <http://cms.math.ca/cmb/a149060> by
Nurmela et al. They relate the packings in this family, much as I had
done, to rational approximations of sqrt(3). And they conjecture that,
by using every second convergent obtained from the continued fraction,
we always obtain optimal packings. Significantly, they say that "From
elementary Diophantine approximation theory it is known that a 'good
approximation' to an irrational number is necessarily a partial
fraction in the continued fraction expansion of this number..." Using
denominators q through 100, for example, their procedure would yield
four packings -- for N = 2, 12, 120 and 1512.

But the compression family, as noted here previously, contains many
more packings in that range which are optimal or presumably so. Since
it seems a pity to exclude more packings than necessary from the
conjectured subfamily of optimal packings, I propose that the
"usefulness" of a fractional approximation be defined differently here,
thereby allowing the conjecture to be broadened:

For a given power r, if p'/q' is a previous used fractional approximation
to sqrt(3), then p/q (not necessarily in lowest terms) will also be used if

q^r |p/q - sqrt(3)| < q'^r |p'/q' - sqrt(3)|

We now examine how this definition of usefulness of an approximation
works, using various values of r, in relation to the compression
family. A short program in Mathematica will be used for illustration.
Since we are dealing with the compression family, only fractions which
_under_estimate sqrt(3) are considered. [Notes: s denotes, as before in
this thread, the side length of the smallest square into which N unit
circles can be packed, while m denotes the maximal pairwise distance
between N points in the unit square. And in Mathematica,
the function N[.], which gives a numerical approximation, is not to be
confused with N denoting the number of circles or points.]

r = 2; Print[{"N", {p, q}, delta, m, s}]; delta = 1;
Do[p = Floor[q Sqrt[3]]; d = q^r (Sqrt[3] - p/q);
If[d < delta, delta = d; m = Sqrt[p^-2 + q^-2];
Print[{Ceiling[(p + 1)(q + 1)/2], {p, q}, N[delta], m, N[2(1 + 1/m)]}]],
{q, 1, 100}]

{N, {p, q}, delta, m, s }
{2, {1, 1}, 0.732051, Sqrt[2], 3.41421}
{12, {5, 3}, 0.588457, Sqrt[34]/15, 7.14496}
{120, {19, 11}, 0.578148, Sqrt[482]/209, 21.0394}
{1512, {71, 41}, 0.577408, Sqrt[6722]/2911, 73.0106}

Notice above that, with power r = 2, our definition of usefulness gives
exactly the fractional approximations to sqrt(3) and the associated
packings given by the conjecture of Nurmela et al. If we decrease the
power, now using r = 1, we get four more packings in the same range,
all of which are again at least presumably optimal: N = 6, 52, 621 and
8281.

Of course the power r may not be decreased with impunity. If we
decrease it too much, we eventually get packings which are known to be
suboptimal. The first case of this occurs when r is about -3.9 with
the introduction of the compression packing for N = 407. [Although
that packing is known to be suboptimal, it is interesting that its
side length is only a mere 0.00047% larger than
s = 2 (487 + 504 Sqrt[3] + 42 Sqrt[2797 + 168 Sqrt[3]])/193
for the presumably optimal packing for N = 407.]

Conjecture 1:
Using some power r <= 1, the packings generated by the above procedure will
always be optimal.

I do not feel comfortable guessing specifically the smallest possible
power r which would generate only optimal packings. But it would be
nice if we could use r = -5/3. This would give, using denominators q
through 100 again, for example, fifteen compression packings, all at least
conjecturally optimal:

r = -5/3; Print[{"N", {p, q}, delta, m, s}]; delta = 1;
Do[p = Floor[q Sqrt[3]]; d = q^r (Sqrt[3] - p/q);
If[d < delta, delta = d; m = Sqrt[p^-2 + q^-2];
Print[{Ceiling[(p + 1)(q + 1)/2], {p, q}, N[delta], m, N[2(1 + 1/m)]}]],
{q, 1, 100}]

{N, {p, q}, delta, m, s }
{2, {1, 1}, 0.732051, Sqrt[2], 3.41421}
{6, {3, 2}, 0.0730914, Sqrt[13]/6, 5.32820}
{12, {5, 3}, 0.0104778, Sqrt[34]/15, 7.14496}
{27, {8, 5}, 0.00903215, Sqrt[89]/40, 10.48}
{39, {10, 6}, 0.0033003, Sqrt[17/2]/15, 12.2899}
{52, {12, 7}, 0.000693539, Sqrt[193]/84, 14.0929}
{99, {17, 10}, 0.000690514, Sqrt[389]/170, 19.2387}
{120, {19, 11}, 0.0000878211, Sqrt[482]/209, 21.0394}
{304, {31, 18}, 0.0000795006, Sqrt[1285]/558, 33.1324}
{449, {38, 22}, 0.0000276619, Sqrt[241/2]/209, 40.0788}
{621, {45, 26}, 5.61637*10^-6, Sqrt[2701]/1170, 47.025}
{1512, {71, 41}, 7.04598*10^-7, Sqrt[6722]/2911, 73.0106}
{3978, {116, 67}, 6.40152*10^-7, Sqrt[17945]/7772, 118.035}
{5935, {142, 82}, 2.21935*10^-7, Sqrt[3361/2]/2911, 144.021}
{8281, {168, 97}, 4.49482*10^-8, Sqrt[37633]/16296, 170.007}

Regrettably, the list above still omits the compression packings for
N = 18, 161 and 188, all thought to be optimal, but r cannot be reduced
enough to include those packings without also including other packings
known to be suboptimal.

In conclusion of this section, if our new Conjecture 1 is true,
the infinite class of optimal packings conjectured by Nurmela et al.
can be significantly broadened, including many more packings from the
compression family.

--------------------------------------------------------------

The Shift Family and an Infinite Conjecturally Optimal Subfamily

The family of packings obtained by shifting rows in a hexagonal
lattice packing, as discussed here previously, includes the four presumably
optimal packings in the PAT_2(k(k + 1)) pattern class discussed in section
10.1 of NACPS. But the shift family and that pattern class are different;
most members of the shift family do not have N = k(k + 1), as required for
that pattern class.

As noted here previously, just as for the compression family, not all
members of the shift family are optimal packings. But we conjecture
that it has an infinite subfamily in which all members are optimal.

It will again be convenient to illustrate how members of such a
subfamily can be generated using a short Mathematica program. Please
recall that, for the shift family, we will always use fractions which
_over_estimate sqrt(3) and which have _odd_ numerators. To obtain such
fractions, we could simply use every fourth convergent from the continued
fraction; doing so would give us a fairly "safe" conjecture. But then our
procedure would fail to include many optimal or conjecturally optimal shift
packings. Therefore, we shall define the usefulness of a fractional
approximation just as we did when dealing with the compression family,
providing flexibility by allowing us to choose the power r.

If we choose r = 1, then the fractions used are just every fourth
convergent. Using denominators q through 100, for example, the procedure
generates just two packings:

r = 1; Print[{"N", {p, q}, delta, m, s}]; delta = 1;
Do[p = Ceiling[q Sqrt[3]]; d = q^r (p/q - Sqrt[3]);
If[OddQ[p] && d < delta, delta = d;
m = Simplify[(2(q(p - 1) - Sqrt[4(q^2 + 1)-(p - 1)^2]))/(q(p + 1)(p - 3))];
Print[{((p + 1)(q + 1))/2, {p, q}, N[delta], m, N[2(1 + 1/m)]}]],
{q, 1, 100}]

{N, {p, q}, delta, m, s }
{20, {7, 4}, 0.0717968, (6 - Sqrt[2])/16, 8.97808}
{2793, {97, 56}, 0.00515478, (384 - Sqrt[17])/18424, 98.9998}

Continuing to use just denominators q through 100 in all of our examples:
If we choose r = 0, the procedure generates five packings.
If we choose r = -4, it generates ten packings.

Conjecture 2:
Using some power r < 0, packings generated by the above procedure will
always be optimal.

Just as for the compression packings, I do not feel comfortable guessing
specifically the smallest possible power r which would generate only
optimal packings. But it would be particularly nice if we could use a power
at least as small as r = -5.966 approximately. This would give thirteen
shift packings, all at least conjecturally optimal:

r = -5.966; Print[{"N", {p, q}, delta, m, s}]; delta = 1;
Do[p = Ceiling[q Sqrt[3]]; d = q^r (p/q - Sqrt[3]);
If[OddQ[p] && d < delta, delta = d;
m = Simplify[(2(q(p - 1) - Sqrt[4(q^2 + 1)-(p - 1)^2]))/(q(p + 1)(p - 3))];
Print[{((p + 1)(q + 1))/2, {p, q}, N[delta], m, N[2(1 + 1/m)]}]],
{q, 1, 100}]

{N, {p, q}, delta, m, s }
{20, {7, 4}, 4.594*10^-6, (6 - Sqrt[2])/16, 8.97808}
{30, {9, 5}, 4.593*10^-6, (20 - Sqrt[10])/75, 10.9086}
{42, {11, 6}, 2.307*10^-6, (15 - Sqrt[3])/72, 12.8532}
{56, {13, 7}, 1.136*10^-6, (42 - Sqrt[14])/245, 14.8077}
{143, {21, 12}, 6.541*10^-9, (40 - Sqrt[5])/396, 22.9724}
{340, {33, 19}, 1.126*10^-10, (304 - Sqrt[106])/4845, 34.99236}
{672, {47, 27}, 2.509*10^-11, (621 - Sqrt[201])/14256, 48.9857}
{1050, {59, 34}, 2.367*10^-12, (493 - Sqrt[79])/14280, 60.9946}
{1591, {73, 42}, 1.25*10^-12, (1512 - Sqrt[469])/54390, 74.98988}
{2150, {85, 49}, 2.18*10^-13, (2058 - Sqrt[638])/86387, 86.9956}
{2793, {97, 56}, 3.422*10^-15, (384 - Sqrt[17])/18424, 98.9998}
{4464, {123, 71}, 3.100*10^-15, (4331 - Sqrt[1321])/264120, 124.9994}
{6525, {149, 86}, 1.459*10^-15, (6364 - Sqrt[1921])/470850, 150.9991}

Remarkably, using r = -5.966 generates _all_ shift packings which are
optimal or currently thought to be so.

But of course r can not be decreased with impunity. If we tried to use,
say, r = -7.2, the procedure would generate its first packing known to be
suboptimal, the shift packing for N = 195.

--------------------------------------------------

In a day or two, I expect to post a comparison between my previously
conjectured bounds and the proven bounds given in NACPS.

David W. Cantrell

///////////////////////////////////////////////////////////////////

My previous comments about the compression and shift families of packings:

--------------------------------------------------

ThomasCR

unread,

May 7, 2010, 2:51:49 AM5/7/10

I am glad that David's conjecture has been proven right to 353. We
will put some computer effort now to 354, to include it, but may take
a while to get the result.

In fact, anybody can try with downloading and running the Packntile
software from www.algit.eu

- Regards

Thomas

David W. Cantrell

unread,

May 8, 2010, 10:03:20 AM5/8/10

Two weak conjectures are stated and then the compression and shift families
of packings are expanded, after my response to Thomas.

(One of the bound comparisons which I had promised should be posted in a
day or two. Sorry for the delay.)

ThomasCR <protok...@gmail.com> wrote:
> I am glad that David's conjecture has been proven right to 353. We
> will put some computer effort now to 354, to include it, but may
> take a while to get the result.

I look forward to your result!

> In fact, anybody can try with downloading and running the Packntile
> software from www.algit.eu

Yes, it would be great to get more people involved.

------------------------------------------------------------------

Two weak conjectures

In my most recent post about the compression and shift families of
packings, I mentioned three conjectures -- one by Nurmela et al. and two by
me. But I forgot to mention two significant conjectures which are much more
likely to be true:

1. There are infinitely many optimal packings in the compression family.
2. There are infinitely many optimal packings in the shift family.

These two conjectures are weaker because, unlike the three previously
mentioned conjectures, they do not attempt to identify specific members of
the families as being optimal.

------------------------------------------------------------------

Expanding the compression family of packings

In _New Approaches to Circle Packing in a Square_ (NACPS), P.G. Szabo

et al. (Springer, 2007), they use the term "grid packing" for the type of
packing discussed in their section 10.2. They relate grid packings to
fractional approximations of sqrt(3), much as I had done for
compression packings. And yet, the program which I had originally
presented here

Do[p = Floor[q Sqrt[3]]; Print[{Ceiling[(p + 1)(q + 1)/2],
2 + (2 p q)/Sqrt[p^2 + q^2]}], {q, 1, 33}]

to generate compression packings does not generate the grid packing
for N = 5, an optimal packing! Why the discrepancy?

The explanation is easy. I was interested in generating compression
packings which had a good chance of being optimal and hence, for each
denominator q, I considered only p = floor(q sqrt(3)) as a possible
numerator. After all, using any numerator p' < floor(q sqrt(3)) gives an
approximation p'/q of sqrt(3) which is poorer than p/q. In particular, for
q = 2, we have p = floor(2 sqrt(3)) = 3 and so we use 3/2 as an
underestimate of sqrt(3), giving the compression packing for N = 6, which
is optimal. But for q = 2, if we had _also_ used p = 2, then we would have
had 2/2 as another underestimate of sqrt(3), and this approximation, poor
though it is, happens to lead to the optimal packing for N = 5. This is a
grid packing, and it should also be considered a compression packing. The
grid and compression families should be identical. The compression family
should not have been limited as my little program above seemed to imply. If
we wish to generate _all_ members of the family, then for each denominator
q, instead of using just p = floor(q sqrt(3)), we should use all integers p
such that q <= p <= floor(q sqrt(3)). Below is a program revised so as to
generate all members of the family, using denominators q through some
maximum, qmax. For each member of the family, it prints the number N of
unit circles, the numerator p and denominator q of the associated fraction
which underestimates sqrt(3), and the side length s of the square:

| Do[
| s = 2 + (2 p q)/Sqrt[p^2 + q^2];
| Print[{Ceiling[(p + 1)(q + 1)/2], {p, q}, s}],
| {q, 1, qmax}, {p, q, Floor[q Sqrt[3]]}]

Expanded in this way, the compression family has many more members. For
comparison, if we choose to stop at qmax = 10, the program above generates
45 compression packings, whereas, if only p = floor(q sqrt(3)) had been
used, only 10 packings would have been generated. In the expanded family,
we have more than one packing for certain values of N. For example, the
fractions 6/4 and 5/5 both generate compression packings for N = 18, the
former being optimal, the latter not. And it appears that, in the expanded
family, the _only optimal_ packing with p < floor(q sqrt(3)) is the packing
for N = 5. Since the expansion has introduced many more packings to the
family and yet only one of those is optimal, it may seem that the expansion
has "watered down" the family. Nonetheless, it seems that expanding the
compression family, so that it is identical to the family of grid packings,
is the "correct" thing to do. (And of course, with hindsight, it's what I
should have done initially.)

------------------------------------------------------------------

Expanding the shift family of packings

Expansion of the shift family is very similar to expansion of the
compression family. The shift family is generated by fractions which
overestimate sqrt(3). For a given denominator q, instead of using just
p = ceiling(q sqrt(3)) when p is odd, we should now use all odd numerators
p such that ceiling(q sqrt(3)) <= p <= 2q + 1. Below is a program revised
so as to generate all members of the family, using denominators q through
qmax:

| Do[
| If[OddQ[p],
| s = (2 + q (q + p q + Sqrt[4 q^2 + (3 - p)(1 + p)]))/(1 + q^2);
| Print[{(p + 1)(q + 1)/2, {p, q}, s}]],
| {q, 1, qmax}, {p, Ceiling[q Sqrt[3]], 2 q + 1}]

Expanded in this way, the shift family has many more members. For
comparison, if we choose to stop at qmax = 10, the program above generates
17 shift packings, whereas, if only p = ceiling(q sqrt(3)) when p is odd
had been used, only 4 packings would have been generated. In the expanded
family, we have more than one packing for certain values of N. For example,
the fractions 383/194 and 359/207 both generate shift packings for
N = 37440, the latter perhaps being optimal.

The shift family now includes the square lattice packings (called the
PAT(k^2) pattern class in section 10.1 of NACPS). It appears that, in the
expanding the family, perhaps the only newly introduced optimal packings
are the square lattice packings for N = 4, 9, 16, 25 and 36.

------------------------------------------------------------------

David W. Cantrell

unread,

May 9, 2010, 10:06:26 AM5/9/10

A bound proven in NACPS is compared with a bound previously conjectured in
this thread.

------------------------------------------------------------------

A Comparison of Two Bounds

It is well known that the problem of packing N unit circles in a square of
minimum side length s is equivalent to the problem of maximizing the
minimum-pairwise-distance m between N >= 2 points in a unit square. Much of
the literature deals with the latter problem. It's trivial to convert
between the two problems using s = 2(1 + 1/m) and m = 2/(s - 2). Using the
latter equation, the lower bound for s, previously conjectured in this
thread to be valid except at N = 4 and 9, is now converted to an upper
bound for m:

m <= 4/(sqrt(2 sqrt(3) (4N - 3) + 4) - 1 - sqrt(3))

In _New Approaches to Circle Packing in a Square_ (NACPS), P.G. Szabo et

al. (Springer, 2007), their Theorem 3.2 can be used to give an upper bound
for m:

m <= min(m1, m2)

where m1 = (sqrt(2 (N - 1)/sqrt(3) + 1) + 1)/(N - 1) and

m2 = 1/(sqrt(sqrt(3) N/2 + (2 - sqrt(3))(floor(sqrt(N)) - 1/2)) - 1)

The figures at
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/ubcomp20.gif>
(for N = 2..20) and
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/ubcomp185to345.gif>
(for N = 185..345) show both upper bounds, together with distances m
for configurations for N points in the unit square. The second figure
makes particularly clear how much tighter my conjectured upper bound is
than the proven bound from NACPS.

Distances m in the first figure are based on configurations which have been
proved optimal. But distances m in the second figure are based merely on
the best configurations currently known; as such, it is, of course,
conceivable that my conjectured upper bound could be disproven simply by
finding a configuration which is so extraordinarily good that its m exceeds
my conjectured bound. (Based on the current data at Packomania
<http://hydra.nat.uni-magdeburg.de/packing/csq/>: For 9 < N <= 500, the
smallest difference between my conjectured upper bound and m is
0.000036..., occuring at N = 449. And at N = 986 (the only configuration
currently shown beyond 500) the difference is 0.000033...)

Some may wonder why I was satisfied to conjecture a bound which is not
valid at N = 4 and 9. The reason is that I wanted a bound which (1) was
fairly tight for large N and (2) had a simple algebraic form. (More
complicated and tighter bounds could be designed, no doubt.) To satisfy
those two requirements. I thought it best to sacrifice validity at N = 4
and 9, preferring to think of those square lattice configurations as being
too exceptional, "freakishly good".

------------------------------------------------------------------

I'm working on a similar comparison of lower bounds for m. That is much
more complicated, but also much more interesting. It may be a week or two
until that comparison is finished.

David W. Cantrell

Phil Carmody

unread,

May 10, 2010, 3:45:55 AM5/10/10

David W. Cantrell <DWCan...@sigmaxi.net> writes:

> A bound proven in NACPS is compared with a bound previously conjectured in

I've heard of NAACP, but what's NACPS? National Association for
Colored Peoples' Segregation?

Phil
--
I find the easiest thing to do is to k/f myself and just troll away
-- David Melville on r.a.s.f1

David W. Cantrell

unread,

May 10, 2010, 5:14:11 AM5/10/10

Phil Carmody <thefatphi...@yahoo.co.uk> wrote:
> David W. Cantrell <DWCan...@sigmaxi.net> writes:
> > A bound proven in NACPS is compared with a bound previously conjectured
> > in
>
> I've heard of NAACP, but what's NACPS? National Association for
> Colored Peoples' Segregation?

I had used the abbreviation earlier in the thread. Furthermore, in the same
post you responded to, I repeated what it stood for, right before I stated
their bound:

> > In _New Approaches to Circle Packing in a Square_ (NACPS), P.G. Szabo
> > et al. (Springer, 2007), their Theorem 3.2 can be used to give an upper
> > bound for m

David

David W. Cantrell

unread,

May 20, 2010, 1:16:07 PM5/20/10

Very recently, Eckard Specht extended Packomania
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html> by giving
584 "strict regular lattice packings" for 500 < N <= 5000, and
commented that "many of them can be improved." Here we discuss a
specific way that several of them can be improved trivially, using
packings for smaller N already shown at Packomania.

-------------------------------------------------------------------
Terminological note: Earlier in this thread, being unfamiliar with
the pertinent literature then, I had coined the term "compression"
packing to describe what Eckard called a "strict regular lattice"
packing and what is called a "grid" packing in _New Approaches to
Circle Packing in a Square_. Now preferring the latter term, such
packings will henceforth be called "grid packings" in this thread.
--------------------------------------------------------------------

As discussed earlier in this thread, some grid packings are not
optimal because clumping certain groups of circles into hexagonal
lattice substructures can give a more efficient packing. As an
example, please take a glance at the packing
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq407.html> for
N = 407. That presumably optimal packing, with hexagonal lattice clumps,
is very closely approximated by the grid packing having 36/21 as the
associated fractional underestimate for sqrt(3). Therefore, if there is a
larger grid packing having an associated fractional underestimate p/q for
sqrt(3) such that p/q can be reduced (by dividing numerator and denominator
by k) to 36/21, that larger grid packing is also not optimal and can be
improved merely by combining k^2 copies of the packing for N = 407:

The grid packing for N' = 1570 has side length 74.55742... and 72/42 as its
associated fractional underestimate for sqrt(3). Dividing numerator and
denominator of that fraction by k = 2 gives 36/21 [which, of course, is
still not in "lowest terms" -- but that's a different matter...] Therefore,
combining k^2 = 4 copies of the packing for N = 407, we get an improved
packing for N' = 1570, with side length s' = 74.55706...:
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs1570sq.gif>
(The two dashed lines divide the figure into quadrants. For each
quadrant, circles having their centers in it or on its boundary
constitute one copy of the packing for N = 407.)

[In words: Take the packing for N = 407. Draw an axis through the
centers of the circles touching, say, the right side of the square
(and discard the semicircles between the axis and the right side).
Adjoin to that figure a copy obtained by flipping about the axis; the
composite rectangular figure is now symmetric about the axis. Draw an
axis through the centers of the circles touching, say, the top side of
the rectangle (and discard the semicircles between that axis and the
top side). Adjoin to that rectangular figure a copy obtained by
flipping about that axis. The resulting figure is the desired packing
in a square for N' = 1570.]

Another example: The grid packing for N' = 2288 has side length 89.9951...
and 87/51 as its associated fractional underestimate for sqrt(3). Dividing
numerator and denominator of that fraction by k = 3 gives 29/17. Therefore,
combining k^2 = 9 copies of the packing for N = 270, we get an improved
packing for N' = 2288, with s' = 89.9937...:
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs2288sq.gif>
(The dashed lines divide the figure into nine regions. For each
region, circles having their centers in it or on its boundary
constitute one copy of the packing for N = 270.)

The following (incomplete) table gives N' for a grid packing which can be
improved by using k^2 copies of a known non-grid packing for N.
The symbol # at the end of a row indicates that the non-grid packing
for N is irregular (see below).

N' k N
513 2 137
581 2 154 #
644 3 80
682 2 180 #
791 2 208
875 4 63
998 2 261 #
1033 2 270
1129 2 295 #
1268 2 330 #
1353 5 63
1415 2 368 #
1570 2 407
1748 3 208
1936 6 63
1985 4 137
2288 3 270
2503 6 80
2622 7 63
3081 4 208
3392 7 80
3413 8 63
3488 3 407
4037 4 270
4307 9 63
4417 8 80
4788 5 208

Knowing the side length s of the packing for N, of course it's trivial to
calculate the side length s' of the improved packing for N':

s' = k (s - 2) + 2

It seems unnecessary to show other figures of those improved packings
since their method of construction has been explained. However, when a
packing for N is irregular (that is, it fails to exhibit regularity as
seen, for example, in the packings for 407 and 270), caution is needed. For
example, consider the packing for N = 180
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq180.html> from which we
wish to get a packing for N' = 682. If we unthinkingly follow the described
procedure, flipping about an axis one unit from the right side and then
flipping about an axis one unit from the bottom side, the resulting figure
has 681 circles, rather than 682. Furthermore, that figure isn't even a
packing because two circles overlap (namely, circle #9 and its image after
the second flip). But if our second flip is about an axis one unit from the
top side, all is well -- we have N' = 682 and no circles overlap.

An unusual case, not included in the table above:
It seemed reasonable to try to improve the grid packing for N' = 760 by
combining four copies of my irregular packing for N = 200
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq200.html>, flipping about
an axis one unit from the left side and then flipping about an axis one
unit from the bottom side. But the resulting packing contains a "bonus"
circle: We get a packing for N' = 761 which has a side length
substantially smaller than that of the grid packing for 760.

David W. Cantrell

unread,

May 21, 2010, 2:20:02 PM5/21/10

A bound given in NACPS is first corrected and then trivially (but
significantly) improved.

--------------------------------------------------

A Correction

Theorem 10.1 on pp. 138-139 of NACPS [_New Approaches to Circle Packing in
a Square_, P.G. Szabo et al. (Springer, 2007)] is intended to give a lower
bound for m, the maximal minimum-pairwise-distance between n >= 2 points in
a unit square. It states that

m >= max(L1(n), L2(n), L3a(n), L3b(n), L4(n), L5(n), L6(n), L7(n), L8(n), L9(n))

where

L9(n) = sqrt(2/(sqrt(3) n)), a default value,
L8(n) is obtained from grid packings, and
L7(n) through L1(n) are based on knowledge about pattern and structure
classes, discussed previously in their chapter 10.

For example, they state that

L2(n) = 1/(ceiling(sqrt(n + 1)) - 3 + sqrt(2 + sqrt(3)))

Significantly, that statement is made _without any explicit restriction_ on
n. Taking n = 3, we have

L2(3) = 1/( -1 + sqrt(2 + sqrt(3))) = 1.073...

That happens to be the largest of their L values when n = 3, and thus they
would have L2(3) as their lower bound. But in fact, for n = 3, the proven
value for m is

m = sqrt(6) - sqrt(2) = 1.035...

which is _smaller_ than their supposed lower bound!

When I noticed this problem, I naturally assumed that I had made a mistake.
Looking earlier in chapter 10, I found that L2 is based on their pattern
class PAT(k^2 - 1). On p. 118, they say

Assertion 5
In the point arrangement problems defined by PAT(k^2 - 1), k >= 3 ...

Ah ha! If we must have k >= 3, then their formula for L2 is valid only for
n >= 3^2 - 1 = 8. No wonder we had found a contradiction using n = 3. And
so then I thought that they must have _intended_ to state appropriate
restrictions on n when defining L1 through L7. When such restrictions are
applied, their bound for m, when n = 3, becomes their default

L9(3) = sqrt(2/(3 sqrt(3))) = 0.620...

But when I then looked at their graph (p. 140, fig. 10.12) of the lower
bound, I was surprised to see that it had been produced using exactly the
definitions which had been stated incorrectly (due to lack of restrictions)
on the previous page! So clearly there was an oversight. But it wasn't just
a typographical error since they used the incorrect definition of the bound
when generating its graph.

In the figure at
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/1owerbnd.gif>,
the blue curve is a proven lower bound, obtained using necessary
restrictions on n, as it presumably should have been shown in NACPS.
Erroneous portions of the graph shown in their fig. 10.12 are indicated in
red. Points in black show values of m, proven optimal. The dashed curve is
an improved lower bound, which we now discuss.

------------------------------------------------------------------

A (Trivially) Improved Lower Bound

If we can pack n unit circles in a square of side length s, then obviously
we can also pack any smaller number of unit circles in a square of that
same size. Equivalently, if n points can be placed in a unit square such
that they are separated from one another by at least distance m, then
obviously any smaller number of points can also be placed in a unit square
such that they are separated from one another by at least that same
distance.

This shows, of course, that, in the packing problem, s must be a (not
necessarily strictly) increasing function of n, and equivalently, in the
point arrangement problem, m must be a (not necessarily strictly)
decreasing function of n.

Quite surprisingly, this trivial fact was overlooked in deriving the lower
bound in NACPS.

For n points in the unit square, an improved lower bound for m is therefore

max ( max(L1(i), L2(i), L3a(i), L3b(i), L4(i), L5(i), L6(i), L7(i), L8(i), L9(i)) )
i >= n

where the L's are defined as in NACPS, except, of course, that necessary
restrictions on n are to be applied for L1 through L7. (When a formula
given on p. 139 of NACPS for some L function is not applicable, we take it
to be 0.) The graph of the improved lower bound is shown as the dashed
curve in the figure at the above link.

--------------------------------------------------------------------------

The comparison between my previously conjectured lower bound for m and a
proven lower bound is still being prepared.

David W. Cantrell

unread,

May 22, 2010, 8:06:33 AM5/22/10

David W. Cantrell <DWCan...@sigmaxi.net> wrote:

> Very recently, Eckard Specht extended Packomania
> <http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html> by giving
> 584 "strict regular lattice packings" for 500 < N <= 5000, and
> commented that "many of them can be improved."

Indeed, the great majority of those lattice packings are suboptimal.

1) In my recent post concerning a correction and an improvement to a bound
given in NACPS, I made the trivial observation that "If we can pack n unit

circles in a square of side length s, then obviously we can also pack any

smaller number of unit circles in a square of that same size." With that in
mind, consider the first two grid packings shown at Packomania for N > 500:

N side length s
507 43.7708541...
513 43.1596604...

Obviously, the grid packing for N = 507 is not optimal. We could take the
grid packing for N = 513, remove any six unit circles, and thereby get a
packing for N = 507 having s = 43.1596604... There are many instances of
this phenomenon among the newly added grid packings. In fact, if we remove
packings which are thereby known to be suboptimal, based on data at
Packomania, only 195 packings remain. The last two of those are

N side length s
4992 133.686...
5000 135.254...

But if we calculate grid packings a little beyond N = 5000, we find that
s = 132.961... for N = 5005. Therefore, we may also eliminate those last
two packings, leaving 193 grid packings as possibly being optimal.

2) Using information copied below from my previous post, of those
remaining 193, we know that 18 are suboptimal. Thus, 175 (of the original
584) grid packings remain which might be optimal.

3) Of those remaining 175, only 82 satisfy my conjectured upper bound for
side length s. Thus, I suspect that, for 500 < N <= 5000, at most 82 grid
packings are optimal.

4) Nurmela et al. stated a conjecture which implies that the grid packing
for N = 1512 is optimal. In my post on May 2, I broadened their conjecture.
If we use power r = -5/3, as I did in that post, to decide which fractional
underestimates of sqrt(3) are to be used, it seems reasonable to guess
that, in the range 500 < N <= 5000, at least three grid packings are
optimal: N = 621, 1512 and 3978. (My next two picks for grid packings in
that range which might be optimal would be N = 1235 and 3520.)

In conclusion, for 500 < N <= 5000, my guess is that the number of grid
packings which are optimal lies somewhere between 3 and 82, and is probably
much closer to 3 than to 82.

(Please see below the table for an additional comment.)

Of the above improved packings, the only ones which might be optimal are
N' = 513, 644, 1033, 1415, 1570, 2288 and 3488. And of those, N' = 1415 is
the only one which happens to use an irregular packing, N = 368. A slightly
improved packing is now given for it, along with the resulting packing for
N' = 1415.

------------------------------------------------------------------

N = 368
s = 36.47646514982270891408...
894 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs368sq.gif>

The best packing previously known has side length
s = 36.47646522... and 893 contacts.

------------------------------------------------------------------

N' = 1415
s' = 70.95293029964541782816...
3448 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs1415sq.gif>

The best packing previously known has side length
s = 70.9547... and 2832 contacts.

------------------------------------------------------------------

David W. Cantrell

unread,

May 31, 2010, 2:18:15 AM5/31/10

A family of packings, closely related to grid packings having p/q = 5/3, is
presented. This family improves on the grid packings by using rhombic
hexagonal-lattice groups of unit circles.

-------------------------------------------------------------------------

For this family, the following simple program prints the number n of unit
circles, the precise side length s of the square and a decimal
approximation of s. (Eckard Specht has recently extended Packomania with
some select packings up to n = 10000, and so members of the new family were
generated that far.) Please see comments and links added after various
lines of the output.

Do[
n = 30*k^2 + 68*k + 39;
s = 2 + (15/17)*((3 + 5*Sqrt[3])*k + Sqrt[(30*Sqrt[3] - 52)*k^2 + 136]);
Print[{n, FullSimplify[s], N[s, 12]}],
{k, -1, 17}]

{1, 2, 2.00000000000}
Obviously!

{39, 2 + 30*Sqrt[2/17], 12.2899151086}
This is just the known grid packing.

{137, (2*(62 + 75*Sqrt[3]))/17, 22.5769188903}
This packing is already known:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq137.html>

{295, (2*(62 + 75*Sqrt[3] + 15*Sqrt[6*(-3 + 5*Sqrt[3])]))/17, 32.8610101090}
This is the only member of the family which is known to be suboptimal.

{513, (169 + 225*Sqrt[3] + 15*Sqrt[-332 + 270*Sqrt[3]])/17, 43.1421850507}
This is new. See
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs513sq.gif>

{791, (2*(107 + 150*Sqrt[3] + 15*Sqrt[6*(-29 + 20*Sqrt[3])]))/17, 53.4204375077}
This packing was recently found by Eckard:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq791.html>

All of the following packings are new. But since they all look much like
either n = 513 or n = 1527, those are the only new figures presented here.

{1129, (259 + 375*Sqrt[3] + 15*Sqrt[-1164 + 750*Sqrt[3]])/17, 63.6957587524}

{1527, (2*(152 + 225*Sqrt[3] + 15*Sqrt[-434 + 270*Sqrt[3]]))/17, 73.9681374993}
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs1527sq.gif>

{1985, (349 + 525*Sqrt[3] + 15*Sqrt[6*(-402 + 245*Sqrt[3])])/17, 84.2375598567}

{2503, (2*(197 + 300*Sqrt[3] + 15*Sqrt[-798 + 480*Sqrt[3]]))/17, 94.5040092652}

{3081, (439 + 675*Sqrt[3] + 15*Sqrt[-4076 + 2430*Sqrt[3]])/17, 104.767466425}

{3719, (2*(242 + 375*Sqrt[3] + 15*Sqrt[-1266 + 750*Sqrt[3]]))/17, 115.027909210}

{4417, (529 + 825*Sqrt[3] + 15*Sqrt[-6156 + 3630*Sqrt[3]])/17, 125.285312565}

{5175, (2*(287 + 450*Sqrt[3] + 15*Sqrt[2*(-919 + 540*Sqrt[3])]))/17, 135.539648392}

{5993, (619 + 975*Sqrt[3] + 15*Sqrt[-8652 + 5070*Sqrt[3]])/17, 145.790885416}

{6871, (2*(332 + 525*Sqrt[3] + 15*Sqrt[6*(-419 + 245*Sqrt[3])]))/17, 156.038989036}

{7809, (709 + 1125*Sqrt[3] + 15*Sqrt[-11564 + 6750*Sqrt[3]])/17, 166.283921153}

{8807, (2*(377 + 600*Sqrt[3] + 15*Sqrt[6*(-549 + 320*Sqrt[3])]))/17, 176.525639977}

{9865, 47 + 75*Sqrt[3] + 15*Sqrt[-876/17 + 30*Sqrt[3]], 186.764099814}

--------------------------------------------------------------------------

David W. Cantrell

unread,

May 31, 2010, 11:13:07 AM5/31/10

***************************************************************************
*** This thread is dedicated to Martin Gardner, whose wonderful columns ***
*** in Scientific American first piqued my interest in packing problems.***
***************************************************************************

David W. Cantrell <DWCan...@sigmaxi.net> wrote:

> A family of packings, closely related to grid packings having p/q = 5/3,
> is presented. This family improves on the grid packings by using rhombic
> hexagonal-lattice groups of unit circles.

Another part of the same family is presented below.

Conjecture: This family contains infinitely many optimal packings.
(Indeed, it might contain only finitely many suboptimal ones.)

Note that the differences between the previously presented part of the
family and the new part are small: The number of circles packed is now n =
2*(3*k + 2)*(5*k + 3) = 30*k^2 + 38*k + 12, rather than 30*k^2 + 68*k + 39.
And in the formula for side length s, the only change is that the constant
term under the radical is now 34, rather than 136.

Again: Some comments and links have been added after various lines of the
output. Since members of this family look so much alike, only two new
figures (n = 644 and 952) are presented.

Do[
n = 2*(3*k + 2)*(5*k + 3);
s = 2 + (15/17)*((5*Sqrt[3] + 3)*k + Sqrt[(30*Sqrt[3] - 52)*k^2 + 34]);

Print[{n, FullSimplify[s], N[s, 12]}],

{k, 0, 17}]

{12, 2 + 15 Sqrt[2/17], 7.14495755428}

This is just the known grid packing.

{80, 2 + 15/17 (3 + 5 Sqrt[3] + Sqrt[6 (-3 + 5 Sqrt[3])]), 17.4305050545}
This packing is known:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq80.html>

{208, 1/17 (124 + 150 Sqrt[3] + 15 Sqrt[6 (-29 + 20 Sqrt[3])]), 27.7102187539}
This packing is known:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq208.html>

{396, 1/17 (169 + 225 Sqrt[3] + 15 Sqrt[-434 + 270 Sqrt[3]]), 37.9840687497}
This is the only member of the new subfamily which is known to be suboptimal.

All of the following packings are new.

{644, 1/17 (214 + 300 Sqrt[3] + 15 Sqrt[-798 + 480 Sqrt[3]]), 48.2520046326}
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs644sq.gif>
[The best packing previously known had also used parallelogramic
hexagonal-lattice groups:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq644.html>, but those
parallelograms were not all equilateral.]

{952, 1/17 (259 + 375 Sqrt[3] + 15 Sqrt[-1266 + 750 Sqrt[3]]), 58.5139546050}
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs952sq.gif>

{1320, 1/17 (304 + 450 Sqrt[3] + 15 Sqrt[2 (-919 + 540 Sqrt[3])]), 68.7698241958}

{1748, 1/17 (349 + 525 Sqrt[3] + 15 Sqrt[6 (-419 + 245 Sqrt[3])]), 79.0194945178}

{2236, 1/17 (394 + 600 Sqrt[3] + 15 Sqrt[6 (-549 + 320 Sqrt[3])]), 89.2628199887}

{2784, 2 + 15/17 (27 + 45 Sqrt[3] + Sqrt[-4178 + 2430 Sqrt[3]]), 99.4996254087}

{3392, 1/17 (484 + 750 Sqrt[3] + 15 Sqrt[6 (-861 + 500 Sqrt[3])]), 109.729702250}

{4060, 1/17 (529 + 825 Sqrt[3] + 15 Sqrt[-6258 + 3630 Sqrt[3]]), 119.952803960}

{4788, 1/17 (574 + 900 Sqrt[3] + 15 Sqrt[-7454 + 4320 Sqrt[3]]), 130.168640000}

{5576, 1/17 (619 + 975 Sqrt[3] + 15 Sqrt[-8754 + 5070 Sqrt[3]]), 140.376868259}

{6424, 1/17 (664 + 1050 Sqrt[3] + 15 Sqrt[6 (-1693 + 980 Sqrt[3])]), 150.577085300}

{7332, 1/17 (709 + 1125 Sqrt[3] + 15 Sqrt[-11666 + 6750 Sqrt[3]]), 160.768813701}

{8300, 1/17 (754 + 1200 Sqrt[3] + 15 Sqrt[-13278 + 7680 Sqrt[3]]), 170.951485401}

{9328, 47 + 75 Sqrt[3] + 15 Sqrt[-(882/17) + 30 Sqrt[3]], 181.124419449}

-------------------------------------------------------------------------

David W. Cantrell

unread,

Jun 3, 2010, 12:40:56 AM6/3/10

The grid family of packings is generalized and improved by using rhombic
hexagonal-lattice groups of unit circles. The two most recent posts here
dealt with the specific case when p/q = 5/3 is the associated fraction
underestimating sqrt(3); we now deal with general p/q.

-------------------------------------------------------------------------

Grid packings are associated with fractions p/q which underestimate
sqrt(3). [For example, in the grid packing for n = 39
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq39.html>, the distance
between the centers of the unit circles in the lower left and lower right
corners is slightly less than 6 sqrt(3) and thus q = 6, while the distance
between the centers of the unit circles in the lower left and upper left
corners is slightly more than 10 and thus p = 10. That packing's associated
fractional underestimate for sqrt(3) is then p/q = 10/6 = 5/3.]

But grid packings can often be improved by forming rhombic
hexagonal-lattice groups. Examples include
n = 137 (p = 20, q = 12)
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq137.html> and
n = 208 (p = 25, q = 15)
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq208.html>.
These are actually slightly different types of packings. In the latter,
there are rhombic groups containing 25 unit circles. (And of course, those
groups are cut into halves at the sides of the square, and into fourths at
two corners.) In the former, in addition to rhombic groups containing 9
unit circles (shown in orange), there are "diagonal single-file buffers"
(in yellow) between those groups. Despite the difference between these two
types of packings, we can conveniently provide a unified treatment for all
such packings. They form a family which, for want of a better name, will be
called, at least temporarily,

the rhombic family

of packings of unit circles in squares. (Suggestions for better names are
welcome.)

Most important things about the family can be encapsulated in a short
program, in Mathematica, which generates the necessary data for members of
the family. [The program should be mostly self-explanatory. But anyway...
It begins with the list of rhombic packings being empty. GCD means greatest
common divisor. n is the number of unit circles packed; d depends upon
whether index j is even or odd; r is to be used as a radicand; x and y are
coordinates of a point, to be explained later; and s is the precise side
length of the square. The condition n <= 10^4 is merely due to the fact
that no packings beyond n = 10^4 are currently shown at Packomania; the two
following conditions make sure that the packing is valid. When those
conditions are passed, the list of packings is appended with data for the
packing:
{n, {p, q}, j, s approx. to 32 decimal places, {x, y} approx. similarly}.
The denominatorial index q goes up to 120 (and correspondingly, index j to
120/q) in order to get rhombic packings up to n = 10^4.]

| listRhombic = {};

| Do[
| p = Floor[q*Sqrt[3]];

| If[GCD[p, q] == 1,
| Do[
| n = Ceiling[(1/2)*(1 + j*p)*(1 + j*q)]; d = (3 + (-1)^j)/2;
| m = (j - d)/2; r = d^2*(p^2 + q^2) - m^2*(p - Sqrt[3]*q)^2;
| x = 1 + ((3 - d)/(p^2 + q^2))*(m*q*(p - Sqrt[3]*q) + p*Sqrt[r]);
| y = 1 + (d - 1)*m + (((3 - d)*q)/(p^2 + q^2))*(m*(Sqrt[3]*p + q) + Sqrt[r]);
| s = 2 + ((2*p*q)/(p^2 + q^2))*(m*(Sqrt[3]*p + q) + Sqrt[r]);
| If[n <= 10^4 && FullSimplify[r] >= 0 && FullSimplify[x] >= 2,
| listRhombic = Append[listRhombic, {n, {p, q}, j, N[s, 32], N[{x, y}, 32]}]],
| {j, 1, 120/q}]],
| {q, 1, 120}]

An example item from listRhombic, giving a new packing for n = 407, is

{407, {12, 7}, 3, 38.277987109269550230616036940070,
{2.7184679719007525887473983084269, 4.0231655924391291858846697450059}}

See the packing at
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs407sq.gif>.

-------------------------------------------------------------------------

The point {x, y}:

Each of these packings has a right-triangular hexagonal-lattice group of
circles near the square's lower right corner, which is taken to be the
origin of our coordinate system. The point {x, y} is the center of the only
circle outside that group which is tangent to the uppermost circle of the
group. [For example, in the figure above for n = 407, the right-triangular
group consists of circles #1, 2, 26 and 50, of which #2 is the uppermost;
{x, y} is the center of circle #20, the only circle, outside the group,
which is tangent to #2. For another example, now using the type of packing
with "diagonal single-file buffers", in the contact diagram for the packing
for n = 137 at <http://hydra.nat.uni-magdeburg.de/packing/csq/csq137.html>,
{x, y} is the center of circle #21.]

For any rhombic packing, just knowing {x, y} and using a little thought,
all coordinates of unit circle centers can be obtained by adding integers
and integer multiples of sqrt(3), x and y.

-------------------------------------------------------------------------

listRhombic, generated by the Mathematica program as shown above (for n <=
10^4), consists of 225 packings. Several of those were known prior to this
thread, but 111 of those packings are improvements over packings currently
shown at Packomania. A list of those 111 packings is given below my
signature, each item shows n, {p, q} and then the amount of reduction in
side length. (1) For some, the improvement may seem quite large. As an
extreme example, {7130, {22, 13}, 3.786078123540279861959129122},
meaning that the rhombic packing for n = 7130 has a side length which is
smaller by 3.786... than that of the grid packing now shown at Packomania.
That might seem exciting at first glance. But 22/13 is not a good
approximation to sqrt(3), and so that rhombic packing is almost certainly
not optimal, despite its large improvement over the grid packing. (2) On
the other hand, for some, the improvement is small. As an extreme example,
{9503, {45, 26}, 0.0000092541165770106766076},
but this might well be an optimal packing since 45/26 is a fairly good
approximation to sqrt(3).

-------------------------------------------------------------------------

The program which produced listRhombic was designed to generate, for each
denominator q, only the "best" packing in the rhombic family. And that
means that the program, as shown above, does not generate all members of
the family. But there are times when it may be desirable to generate all
members. To do so, only two small changes are needed:
(1) Remove the condition that GCD[p, q] be 1.
(2) Allow p to take values smaller than Floor[q*Sqrt[3]] also.

Example: It was claimed that the rhombic family generalizes the grid
family. That means that every grid packing must also be a rhombic
packing. Now consider that, for the grid packing for n = 513, we must use
p = 40, q = 24. But since 40/24 is not in lowest terms, we must remove
the condition that GCD[p, q] == 1 if we want our program to generate that
grid packing. And that is not enough. For q = 24, taking p = 41 gives the
best underestimate to sqrt(3). But since we need p = 40, we must also
allow p to be smaller than Floor[q*Sqrt[3]].

-------------------------------------------------------------------------

Examining the entire rhombic family, one finds that, for certain n, there
are several different packings. In most such cases, just one of those is
the best. But there are cases in which there is a tie for best rhombic
packing. For example, the rhombic family contains two different packings
for n = 1570 having the same side length s, approx.
74.555974218539100461232073880141. One of those packings can be obtained by
putting together four copies of the rhombic packing for n = 407, mentioned
above. The other, which uses larger rhombi and "diagonal single-file
buffers", is shown at
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs1570sq-1.gif>.

-------------------------------------------------------------------------

In this post, only two new links to figures of rhombic packings have been
given. But all rhombic packings look like one or the other of those. (For
anyone who wants to see more, from my two previous posts, here are four
rhombic packings, with p/q = 5/3:
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs513sq.gif>
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs1527sq.gif>
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs644sq.gif>
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs952sq.gif>)

-------------------------------------------------------------------------

Conjecture: The rhombic family contains infinitely many optimal packings.

David W. Cantrell

-------------------------------------------------------------------------

Each item in the following list of 111 rhombic packings has the form
{n, {p, q}, reduction in side length compared to the best packing
previously known}:

{407, {12, 7}, 0.000545048395698306462480650}
{513, {5, 3}, 0.017475383484262134278915633}
{644, {5, 3}, 0.029672443220312005037587602}
{760, {8, 5}, 0.062361699110191562375034023}
{806, {17, 10}, 0.003414406603371245068536665}
{952, {5, 3}, 0.046636422191274840015519836}
{986, {19, 11}, 0.000061379181472810074885877}
{1026, {8, 5}, 0.220181400689181945733126656}
{1098, {12, 7}, 0.002422549549526739390711319}
{1129, {5, 3}, 0.043731898908956810388646687}
{1320, {5, 3}, 0.114624009802070141725961989}
{1333, {8, 5}, 0.124877163155133850151485227}
{1340, {22, 13}, 0.006863273882455117402937806}
{1353, {13, 8}, 0.107509187720911575000875242}
{1415, {17, 10}, 0.002276195921762579408120937}
{1527, {5, 3}, 0.061268260510775002098516259}
{1570, {12, 7}, 0.001453456929308577628068179}
{1679, {8, 5}, 0.380617581532579893052527493}
{1733, {19, 11}, 0.000054559218676591001605132}
{1748, {5, 3}, 0.154868796298946135519826558}
{1936, {13, 8}, 0.064377958568124346276936050}
{1985, {5, 3}, 0.081761011723482687662960030}
{2009, {27, 16}, 0.010651574272658028263945232}
{2066, {8, 5}, 0.208515763419859278293258957}
{2125, {12, 7}, 0.005087812838741301682528721}
{2193, {17, 10}, 0.011383234916991263487239361}
{2236, {5, 3}, 0.201458433991029658324286017}
{2288, {29, 17}, 0.003852909167358042219000139}
{2359, {22, 13}, 0.004575282078245002351111992}
{2492, {8, 5}, 0.588088387968483818356870100}
{2503, {5, 3}, 0.105226711735288854026552788}
{2585, {31, 18}, 0.000568721683174820586635047}
{2622, {13, 8}, 0.226582862058285371314002505}
{2688, {19, 11}, 0.000272797265982613760494485}
{2765, {12, 7}, 0.002906972094917553916618181}
{2784, {5, 3}, 0.254568122508456496529281367}
{2813, {32, 19}, 0.014620540093911700645565031}
{2959, {8, 5}, 0.313555482920121484159228392}
{3081, {5, 3}, 0.131684660276137665921961245}
{3142, {17, 10}, 0.006828813206742490137073332}
{3392, {5, 3}, 0.314406389485183267495005106}
{3413, {13, 8}, 0.128857681548125967974049642}
{3465, {8, 5}, 0.846206393866013858655120124}
{3488, {12, 7}, 0.008723101439791132144487271}
{3543, {27, 16}, 0.007100591536195495291178651}
{3663, {22, 13}, 0.022883429999302540280360157}
{3719, {5, 3}, 0.161156984127403072253049795}
{3853, {19, 11}, 0.000163677773288730813706897}
{4012, {8, 5}, 0.440362801378363891466253312}
{4037, {29, 17}, 0.002568549875321790227209016}
{4060, {5, 3}, 0.381219788690069588414973231}
{4130, {39, 23}, 0.010160301319105200018494441}
{4260, {17, 10}, 0.023911905376056099589503064}
{4296, {12, 7}, 0.004845099099053478781422636}
{4307, {13, 8}, 0.390480964667547627047649969}
{4417, {5, 3}, 0.193668737817765802623441217}
{4526, {41, 24}, 0.004460258893261527330190829}
{4563, {31, 18}, 0.000379146634407776061483360}
{4788, {5, 3}, 0.455298857098593984171464093}
{4940, {43, 25}, 0.001189365915051788657621745}
{4967, {32, 19}, 0.009746299719222121742055505}
{5175, {5, 3}, 0.229248019604140283451923979}
{5187, {12, 7}, 0.013329232685846621843073119}
{5225, {8, 5}, 0.589400062769716565164691997}
{5226, {19, 11}, 0.000572877952340622301131414}
{5254, {22, 13}, 0.013726547764910234805875615}
{5306, {13, 8}, 0.215018375441823150001750480}
{5372, {45, 26}, 0.000013881175578775776311042}
{5508, {27, 16}, 0.035516707693831445626480639}
{5549, {17, 10}, 0.013658528402647138726281180}
{5576, {5, 3}, 0.536985706262922605666796173}
{5699, {46, 27}, 0.007192024117514228831628431}
{5993, {5, 3}, 0.267926104032679517081104481}
{6163, {12, 7}, 0.007267939908855120178893227}
{6278, {29, 17}, 0.012844436907527138767853171}
{6364, {147, 85}, 2.433600812282536814503039434}
{6408, {13, 8}, 0.600778217676580214505342054}
{6424, {5, 3}, 0.626683773591682855650603337}
{6598, {8, 5}, 0.761235163065159786105054980}
{6644, {50, 29}, 0.000593076349777420762818170}
{6809, {19, 11}, 0.000327356015615813013070433}
{6871, {5, 3}, 0.309737592597892271039653116}
{6975, {154, 89}, 2.446297895357108412913461673}
{7007, {17, 10}, 0.041009475970243853661217332}
{7098, {31, 18}, 0.001895767804567362905121889}
{7130, {22, 13}, 3.786078123540279861959129122}
{7222, {12, 7}, 0.018907259121750145205533419}
{7268, {157, 91}, 2.432881189729809200184409355}
{7301, {39, 23}, 0.006773244703595670041763694}
{7520, {53, 31}, 0.005121699482653326427642309}
{7615, {13, 8}, 0.323041873039045984543986475}
{7728, {32, 19}, 0.048753328444974056912168739}
{7809, {5, 3}, 0.354720584273350262587813774}
{7906, {27, 16}, 0.021303148545316056527890465}
{7920, {164, 95}, 2.444816795580871662839937352}
{8003, {41, 24}, 0.002973452566619792308921979}
{8051, {55, 32}, 0.001856273147509600673034783}
{8131, {8, 5}, 0.956554057551702355505395052}
{8366, {12, 7}, 0.010175625677482603365057437}
{8600, {19, 11}, 0.000982085636530362061381338}
{8636, {17, 10}, 0.022766469833982526974478728}
{8737, {43, 25}, 0.000792906973783655720936264}
{8807, {5, 3}, 0.402916867982059316648572037}
{8925, {13, 8}, 0.859639457228574451467913101}
{8925, {174, 101}, 2.443500088223450248384694127}
{9013, {29, 17}, 0.007705818334716084438000283}
{9293, {22, 13}, 0.027455902726620954230196597}
{9503, {45, 26}, 0.0000092541165770106766076}
{9593, {12, 7}, 0.025458469776477833441886157}
{9824, {8, 5}, 1.176176775936967636713740200}
{9865, {5, 3}, 0.454372139416441330455322243}

David W. Cantrell

unread,

Jun 10, 2010, 6:40:57 AM6/10/10

A few comments have been added to the discussion of the rhombic family.

David W. Cantrell <DWCan...@sigmaxi.net> wrote:

Whether the factor j is even or odd determines, respectively, whether
the packing does or does not have "single-file buffers" between its
rhombic groups.

The paragraph above is correct. However, after posting that list of
111 packings, I realized that many of those packings do not satisfy my
conjectured upper bound for side length. A more selective list, now
replacing the original list below my signature, consists of 40 rhombic
packings which both (a) improved on packings which had been shown at
Packomania and (b) satisfy my conjectured bound.

To explain more fully, we reconsider this example.

Removing the condition GCD[p, q] == 1 from the program, we see that
four lines are printed for rhombic packings with n = 1570. From those
lines, we get {p, q}, j and side length s as shown below:

{12, 7}, 6, 74.555974218539100461232073880141;
{24, 14}, 3, 74.555974218539100461232073880141;
{36, 21}, 2, 74.557427675468409038860142058843;
{72, 42}, 1, 74.557427675468409038860142058843.

The last two lines actually give the same packing. It is the grid
packing, which is suboptimal. In general, whenever j is 1 or 2, the
rhombic packing degenerates to the grid packing (because the "rhombic
group" then consists of just one unit circle).

The first two lines give the distinct equally-good packings discussed
in my original post. For j = 6, since j is even, we get a packing with
"single-file buffers", shown at the above link. For j = 3, since j is
odd, we get a packing without such "single-file buffers" between the
rhombi.

-------------------------------------------------------------------------

A triviality

As noted above, when j = 1 or 2, the rhombic packing degenerates to
the grid packing. But there is an even more degenerate case; it was
not included in our program: If we allow j = 0, then we always get the
packing of one unit circle in a square of side length s = 2. Therefore,
that simple packing may also be considered to be in the rhombic family.

-------------------------------------------------------------------------

> Conjecture: The rhombic family contains infinitely many optimal packings.

David W. Cantrell

-------------------------------------------------------------------------

Each item in the following list of 40 rhombic packings has the form
{n, {p, q}, j, {reduction in side length s compared to the best
packing previously known, difference between my conjectured upper bound
and s}}. All of these packings are now shown at Packomania:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html>.

{407, {12, 7}, 3, {0.000545048396, 0.318881150}}
{513, {5, 3}, 8, {0.0174753835, 0.0637335554}}
{644, {5, 3}, 9, {0.0296724432, 0.0324574360}}
{806, {17, 10}, 3, {0.00341440660, 0.181214950}}
{986, {19, 11}, 3, {0.0000613791815, 0.380257040}}
{1098, {12, 7}, 5, {0.00242254955, 0.266875223}}
{1340, {22, 13}, 3, {0.00686327388, 0.0429240393}}
{1415, {17, 10}, 4, {0.00227619592, 0.116855449}}
{1570, {12, 7}, 6, {0.00145345693, 0.248819563}}
{1733, {19, 11}, 4, {0.0000545592187, 0.381555514}}
{2125, {12, 7}, 7, {0.00508781284, 0.211298197}}
{2193, {17, 10}, 5, {0.0113832349, 0.0365843850}}
{2288, {29, 17}, 3, {0.00385290917, 0.0952986481}}
{2585, {31, 18}, 3, {0.000568721683, 0.292439762}}
{2688, {19, 11}, 5, {0.000272797266, 0.359453621}}
{2765, {12, 7}, 8, {0.00290697209, 0.188193057}}
{3488, {12, 7}, 9, {0.00872310144, 0.155140786}}
{3853, {19, 11}, 6, {0.000163677773, 0.355049489}}
{4296, {12, 7}, 10, {0.00484509910, 0.128172167}}
{4526, {41, 24}, 3, {0.00446025889, 0.00590880112}}
{4563, {31, 18}, 4, {0.000379146634, 0.257095421}}
{4940, {43, 25}, 3, {0.00118936592, 0.202347361}}
{5187, {12, 7}, 11, {0.0133292327, 0.0992409882}}
{5226, {19, 11}, 7, {0.000572877952, 0.335795355}}
{5372, {45, 26}, 3, {0.0000138811756, 0.402520243}}
{6163, {12, 7}, 12, {0.00726793991, 0.0686970574}}
{6364, {147, 85}, 1, {2.43360081, 0.371780083}}
{6644, {50, 29}, 3, {0.000593076350, 0.256349133}}
{6809, {19, 11}, 8, {0.000327356016, 0.328786912}}
{6975, {154, 89}, 1, {2.44629790, 0.390030558}}
{7098, {31, 18}, 5, {0.00189576780, 0.208875901}}
{7222, {12, 7}, 13, {0.0189072591, 0.0439262264}}
{7268, {157, 91}, 1, {2.43288119, 0.273932931}}
{7920, {164, 95}, 1, {2.44481680, 0.292100797}}
{8051, {55, 32}, 3, {0.00185627315, 0.111457438}}
{8366, {12, 7}, 14, {0.0101756257, 0.00974189879}}
{8600, {19, 11}, 9, {0.000982085637, 0.311242774}}
{8737, {43, 25}, 4, {0.000792906974, 0.133412091}}
{8925, {174, 101}, 1, {2.44350009, 0.194432862}}
{9503, {45, 26}, 4, {9.25411658*10^-6, 0.400375622}}

David W. Cantrell

unread,

Jun 13, 2010, 1:33:22 PM6/13/10

We discuss a family of packings which are hybrids of rhombic and
columnar-shift packings.

------------------------------------------------------------------------
Terminological note: Packings previously called "shift" packings in this
thread will henceforth, more descriptively, be called "columnar-shift"
packings.
------------------------------------------------------------------------

Two important packing families, the rhombic and the columnar-shift, were
developed earlier in this thread. Each of these families contains many
highly dense packings and, conjecturally, infinitely many optimal packings.

Some good packings can also be obtained by "hybridization" between those
families, thereby giving a new family: (rhombic, columnar-shift) hybrids.
It's helpful to look at an example of such a hybrid which is already known.

Consider the packing for N = 87 shown at
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq87.html>. After a casual
glance, one might think the following: At the right, there are three
columns of unit circles, the middle column being shifted slightly above the
other two. The other unit circles, to the left of those three columns, are
arranged in a grid packing. But that description is not precisely correct.
Each circle which looks as though it might be at the bottom of a column is
actually slightly to the left of the circles above it. And the arrangement
of the other circles only approximates a grid packing.

As this example indicates, packings in the (rhombic, columnar-shift) hybrid
family cannot be specified in a way which is both precise and simple. But
we can specify, precisely and simply, an "archetype" hybrid packing which
_approximates_ optimized packings. For n = 87, the archetype has three
columns at the right, the circle at the top of the middle column touching
the top of the square and circles at the bottoms of the other columns
touching the bottom of the square. The other circles are grid-packed in a
rectangle, the right side of which touches the circles in the leftmost of
the three columns. The archetype approximates the optimized packing fairly
well: Side length s for the optimized packing is 18.2831..., while side
length s_a for the archetype is 18.2876... [A general algebraic expression
for s_a, in terms of p and q for the rhombic part and n for the number of
columns, could be given. But Mathematica's result for s_a is huge,
occupying many pages. Perhaps there is liitle reason to be interested in a
precise expression for s_a since it is, after all, itself just an
approximation for s.]

The (rhombic, columnar-shift) hybrid family is like a "structure class" as
the term is used in _New Approaches to Circle Packing in a Square_,
P.G. Szabo et al. (Springer, 2007). Their term "pattern class" describes a
family of packings whose members are precisely characterized, in general.
Then concerning "structure class", they say (p. 123) "The modified notation
(from pattern class to structure class) is based on the argument that this
time the coordinates of the optimal, and the best known packings are not
given, just a well approximating structure is defined."

Since the hybrid family's archetypal and optimized packings differ
somewhat, we endeavor to present here all good packings in the family
for N < 1000, putatively optimized.

----------------------------------------------------------------
----------------------------------------------------------------

Rhombic + One Column

Most good hybrid packings have just one column appended to a rhombic
packing. And when there is just one column and the rhombic packing is just
a grid packing, the algebraic expression for the side length s_a of the
archetypal packing is simple. If p/q is the associated fractional
overestimate for sqrt(3), then

s_a = 2(1 + p (p + q sqrt(p^2 + q^2 - 1))/(p^2 + q^2)).

N = 28 and 53:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq28.html> and
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq53.html>
These known packings are both approximated by a (non-grid) rhombic part
plus one column. (Where are the rhombic groups? Well, there are no whole
rhombi in these two packings. Rather, each has a half rhombus at the left
and two quarter rhombi at top and bottom, next to the column.)

N = 217:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq217.html>
This presumably optimized packing has s = 28.1872... It is approximated
well by the archetype, having a grid part plus one column, with
s_a = 28.1895... (Note the rattler in the upper left corner. Having a
rattler in one of the corners is often seen in these hybrid packings.)

N = 408:
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs408sq.gif>
This new, presumably optimized packing has s = 38.46859362531026410351...
Note that there are many (whole) rhombic groups, as well as several half
rhombi and two quarter rhombi. The packing currently shown at Packomania
has side length 38.4691...

N = 493:
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs493sq.gif>
This new, presumably optimized packing has s = 42.07935786113438806132...
The packing currently shown at Packomania has side length 42.079357890...,
while that of the archetype is s_a = 42.079757629...

N = 659:
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs659sq.gif>
This new, presumably optimized packing has s = 48.73889807193830467232...
The packing currently shown at Packomania is the archetype, with
s_a = 48.7769...

N = 766:
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs766sq.gif>
This new, presumably optimized packing has s = 52.36670958083337373750...
The packing currently shown at Packomania is the archetype, with
s_a = 52.3754...

----------------------------------------------------------------
----------------------------------------------------------------

Rhombic + Two Columns

N = 69:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq69.html>
This known packing has s = 16.2910... and is approximated well by the
archetype, a grid part plus two columns, having s_a = 16.2959...

N= 248:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq248.html>
This known packing has s = 30.18346610619051817070... The archetype has a
(non-grid) rhombic part but, just like the packings for N = 28 and 53, no
whole rhombic groups appear.

N = 539:
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs539sq.gif>
This new, presumably optimized packing has s = 44.07907689044332029600...
For comparison, the archetype has s_a = 44.07947...

----------------------------------------------------------------
----------------------------------------------------------------

Rhombic + Three Columns

N = 87:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq87.html>.
This was the example discussed in the introduction.

N = 281:
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs281sq.gif>
This new, presumably optimized packing has s = 32.18078157808499508358...
For comparison, the archetype has s_a = 32.18260...

It is particularly interesting to compare the new packing with the one
currently shown at Packomania,
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq281.html>, having side
length 32.18222... It is reasonable to think of that former packing as also
being in the hybrid family, even though its three columns are not next to
each other.

N = 587:
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs587sq.gif>
This new, presumably optimized packing has s = 46.07863725422414128830...
The archetype has a (non-grid) rhombic part but, just like the packings
for N = 28, 53 and 248, no whole rhombic groups appear.

----------------------------------------------------------------
----------------------------------------------------------------

Most good hybrid packings consist of a rhombic (often, just a grid) part
with only a single appended column. As the number of appended columns
increases, the packings tend to get worse. There may not be any good hybrid
packings (having a nonempty rhombic part) with four or more appended
columns.

There might be infinitely many packings in the (rhombic, columnar-shift)
hybrid family which are optimal. But hybrid packings are presumably never
density records.

All of the new hybrid packings above will be submitted to Packomania soon,
and a few other good ones for 1000 < N < 10000 will be submitted in the
next few days.

David W. Cantrell

James Waldby

unread,

Jun 13, 2010, 2:47:52 PM6/13/10

On Sun, 13 Jun 2010 17:33:22 +0000, David W. Cantrell wrote:
> We discuss a family of packings which are hybrids of rhombic and
> columnar-shift packings.

...

> Terminological note: Packings previously called "shift" packings in this
> thread will henceforth, more descriptively, be called "columnar-shift"
> packings.

...

> Two important packing families, the rhombic and the columnar-shift, were
> developed earlier in this thread. Each of these families contains many
> highly dense packings and, conjecturally, infinitely many optimal
> packings.
>
> Some good packings can also be obtained by "hybridization" between those
> families, thereby giving a new family: (rhombic, columnar-shift) hybrids.

...

> As this example indicates, packings in the (rhombic, columnar-shift)

...

> The (rhombic, columnar-shift) hybrid family is like a "structure class"
> as the term is used in _New Approaches to Circle Packing in a Square_,

...

Re terminology, "columnar-shift" grates badly each time I read it.
I think "column-shift" would be better; it's adequately grammatically
correct and expresses the same thing.

> Most good hybrid packings consist of a rhombic (often, just a grid) part
> with only a single appended column. As the number of appended columns
> increases, the packings tend to get worse. There may not be any good
> hybrid packings (having a nonempty rhombic part) with four or more
> appended columns.

1. Can you make a sort of 'periodic table' that characterizes best-
packing type vs index? Or at least a summary table?

2. Do you think that for all N > some large number, all optimal
packings fall into specific families? Or will there be occasional
singletons with patterns that fall into no previously-recognized
family?

> There might be infinitely many packings in the (rhombic, columnar-shift)
> hybrid family which are optimal. But hybrid packings are presumably
> never density records.

...

When I first read that last sentence, it seemed intuitively correct,
but after a little thought I don't see a reason why there shouldn't
be an occasional exception. Is there an obvious reason?

Do density record patterns have no (or quite few) rattlers?
Do they always exhibit symmetry on several axes?

--
jiw

David W. Cantrell

unread,

Jun 14, 2010, 9:34:57 AM6/14/10

Thanks for that observation. I'll think about it, and will probably take
your suggestion.

> > Most good hybrid packings consist of a rhombic (often, just a grid)
> > part with only a single appended column. As the number of appended
> > columns increases, the packings tend to get worse. There may not be any
> > good hybrid packings (having a nonempty rhombic part) with four or more
> > appended columns.
>
> 1. Can you make a sort of 'periodic table' that characterizes best-
> packing type vs index? Or at least a summary table?

For those packings which do happen to fall into one of the recognized
families, something like that could be done. But such packings are actually
rather sparse. I do plan, however, to eventually give something like a
'periodic table' for the (even sparser) density record packings.

> 2. Do you think that for all N > some large number, all optimal
> packings fall into specific families?

No. (Of course, one might get that incorrect impression by looking at the
packings _currently_ shown at Packomania for 500 < N < 10000. But that's
just because, when N is large, good packings are very difficult to find
_unless_ there happens to be a recognized pattern for that N.)

But perhaps if the number of recognized families were greatly increased and
if membership in a family were rather loosely defined, then we could get
much closer to answering "Yes" to your question. Browsing through the
Overview section at Packomania might be useful. Look, for example, at
<http://hydra.nat.uni-magdeburg.de/packing/csq/d35.html>, which shows
packings for N = 409-420. The packings from N = 409 through 415 are alike
in some sense. Should they all be in the same family? Maybe, but I'm not
sure how that family should be defined or how useful it would be. But take
a look at N = 418. It does fit a family which I recognize (but haven't
mentioned before) and note that, between 415 and 418, there were two other
packings. Now look at
<http://hydra.nat.uni-magdeburg.de/packing/csq/d32.html>. Packings for
N = 373-375 (as well as for N = 372, shown on the previous page) are of the
same sort as 409-415, then there are two other packings, and N = 378 is in
the same family as N = 418. Is that just coincidence?

> Or will there be occasional
> singletons with patterns that fall into no previously-recognized
> family?

Not just occasional singletons; rather, frequent groups (unless, as I said
above, the number of recognized families were greatly increased and
membership in a family were rather loosely defined).

> > There might be infinitely many packings in the (rhombic,
> > columnar-shift) hybrid family which are optimal. But hybrid packings
> > are presumably never density records.
> ...
>
> When I first read that last sentence, it seemed intuitively correct,
> but after a little thought I don't see a reason why there shouldn't
> be an occasional exception. Is there an obvious reason?

Whether the reason is obvious depends on how much one has thought about
such things. Having density greater than that for any smaller N is clearly
a very stingent requirement. To achieve such density, the packing needs to
be very close to a single hexagonal lattice. But in a (rhombic,
column-shift) hybrid packing, assuming rhombic and columnar parts are both
nonempty, the rhombic part and its nearby column will never be very close
to being in a hexagonal lattice. Rather, that column and the circles which
touch it from the rhombic part tend, more or less, to be in a _square_
lattice.

> Do density record patterns have no (or quite few) rattlers?

Good question.

This is premature... but to help answer your question, let's look at part
of the density record table:

{N, density} family
{407, 0.872662} rhombic
{447, 0.874373} none?
{448, 0.876254} none?
{449, 0.878148} grid
{572, 0.878581} grid

and then look at <http://hydra.nat.uni-magdeburg.de/packing/csq/d38.html>.

N = 449 is an excellent grid packing. Its density is so high that we can
remove one or two circles from it, readjust the remaining circles somewhat,
and we _still_ get density records for N = 448 and 447. (A la Reagan's
"trickle-down" economics, this might be called trickle-down density.) The
_current_ packings for N = 447 and 448 have very many rattlers. But that
should be a temporary situation. I suspect that the optimal packings for
those would have few rattlers.

So to answer your question:
It seems likely that density record packings, once optimized, should have
few rattlers.

(By the way, also notice at the above link that packings for N = 450-454
are of the same sort as previously mentioned for N = 372-375 and 409-415.)

> Do they always exhibit symmetry on several axes?

No.

David W. Cantrell

unread,

Jun 20, 2010, 2:27:20 PM6/20/10

A small update about (rhombic, column-shift) hybrid packings is given. And
a slightly improved packing for N = 250 is presented.

--------------------------------------------------------------------------

Packomania now shows all hybrid packings previously mentioned here. And it
also shows my presumably optimized hybrid packings (with just one column
appended to the rhombic part) for N = 1818, 1236, 2126 and 2512; see
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html> if interested.

Another presumably optimized packing with one appended column is N = 6091,
with side length 146.021168628... (The packing currently shown at
Packomania has s = 146.021196...) But I don't know if my packing for N =
6091 will appear at Packomania because my data was computed using only
machine precision. (Why didn't I use higher precision? Well, there was a
system of 11882 quadratic equations to be solved...) In any event, my
packing is shown at
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs6091sq.gif>.
Since there are so many circles in that image, it may be hard to see
exactly what's going on. But this packing is of _exactly_ the same sort as

N = 493
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs493sq.gif>

and it's easy to see what's going on there. (Note in particular that,
in each of these packings, the unit circle near the lower right corner of
the square does not touch its right side.)

Some hybrid packings having two or three appended columns will be sent to
Packomania soon and will probably appear there in a day or so:
N = 1308, 2614, 2718 and 9899.

---------------------------------------------------------------------

N = 250
s = 30.41703105674489872839...
572 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs250sq.gif>
(N.B. Some of the circles are very close together without touching.
This makes me suspect that, when this new packing is eventually shown at
Packomania, the number of contacts indicated there might not be correct,
being higher than 572.)

The best packing previously known has side length

s = 30.417031056761... and 564 contacts.

---------------------------------------------------------------------

David W. Cantrell

unread,

Jun 22, 2010, 9:28:05 PM6/22/10

The Triangle-Shift Family
Part 1

--------------------------------------------------------------------------

A new family of packings is presented. Importantly, it fills a conspicuous
void in families containing highly dense packings.

--------------------------------------------------------------------------

Rhombic packings (including grid packings), such as the optimal packings
for N = 18 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq18.html> and
N = 137 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq137.html>, are
associated with fractions p/q which underestimate sqrt(3). Column-shift
packings, such as the optimal packing for N = 20
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq20.html>, are associated
with fractions p/q, having p _odd_, which overestimate sqrt(3). In both of
those families, packings tend to be denser the closer that p/q is to
sqrt(3).

Surely something special must also happen when p/q slightly overestimates
sqrt(3) and p is _even_. But what, exactly? Part of the problem in
answering that question lies in the fact that the archetype for the new
family is more complicated than the archetypes for the rhombic and
column-shift families.

The name of the new family is

the triangle-shift family

for reasons that will become evident soon. One could choose to think of the
column- and triangle-shift families as being two subfamilies comprising a
larger "shift" family, associated with fractions p/q which overestimate
sqrt(3).

--------------------------------------------------------------------------

As an example, we now show, in three stages, how to produce an archetypal
triangle-shift packing for N = 68.

Stage 1: Single hexagonal lattice

Notice that, taking p = 14 and q = 8, p/q overestimates sqrt(3). We will
therefore be able to pack N = ceiling((p + 1)(q + 1)/2) = 68 unit circles
in a square of side length s_shl = p + 2 = 16 by simply having all the
circles in a single hexagonal lattice, as shown in the left figure at
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circs68sqSimple.gif>.

Of course, this means that s_shl = 16 is an upper bound for the side length
s of the optimal packing for N = 68. Surprisingly, calculating the upper
bound for s based on Theorem 10.1 in NACPS [_New Approaches to Circle
Packing in a Square_, P.G. Szabo et al. (Springer, 2007)], we obtain
3 (4 + sqrt(3)) = 17.196... and, using a trivial method mentioned
previously in this thread, that bound can be improved to 218/13 = 16.769...
But obviously, compared to either of those, the single-hexagonal-lattice
packing for N = 68, although utterly trivial, provides a substantially
tighter upper bound!

Stage 2: Triangle & trapezoid

We can always do better than a single-hexagonal-lattice packing. Referring
again to the left figure at the above link, note that extra space is
available to the right of the hexagonal lattice. One way to take advantage
of that extra space is to shift a large trapezoidal hexagonal-lattice group
down and to the right, as shown in the right figure. In general, we will
then have a packing consisting of a large right-triangular
hexagonal-lattice group, labelled A, which touches the left and bottom
sides of the square, and a large trapezoidal hexagonal-lattice group, which
touches A and the right side of the square. Adjusting the side length s_t&t
so that the trapezoidal group also touches the top side of the square, we
obtain

s_t&t = (p + sqrt(3)q + 2 + sqrt(8 - (p - sqrt(3)q - 2)^2))/2

in general. With p = 14 and q = 8, this gives

s_t&t = 8 + 4 sqrt(3) + sqrt(48 sqrt(3) - 82) = 15.99517...

as an upper bound for the side length s of the optimal packing for N = 68.
Of course, this upper bound is tighter than that obtained from the
single-hexagonal-lattice packing.

Stage 3: Triangle-shift

And we can always do better still than a triangle-&-trapezoid packing.
Referring to the right figure at the above link, note that extra space is
available to the left of the trapezoidal group. One way to take advantage
of that extra space is to break the trapezoidal group into triangular
groups so that, as we shrink the side length of the square, those
triangular groups are shifted to the positions shown in the left figure at
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circs68sqCompare.gif>.
Those hexagonal-lattice groups are a large equilateral-triangular one,
labelled B, touching A and the right side of the square; a large
right-triangular one, labelled C, touching B and the top side of the
square; a small equilateral-triangular one, labelled D_1, touching A and C;
and a small right-triangular one, labelled X, touching D_1 and the left
side of the square. The side length s_ts is then determined so that X also
touches the top side of the square. (This fully describes the structure
when N = 68. In general however, the structure may, as shown later, have
more small equilateral-triangular groups D_i. And the group X of circles
which remain after forming the last of those small equilateral-triangular
groups will not necessarily be right-triangular; rather, in general, X is
trapezoidal.)

Side length s_ts for the triangle-shift archetype cannot, in general, be
expressed in closed form, as we did for s_t&t, unless we were allowed to
use "root objects" (as in some computer algebra systems). For our example
with N = 68, s_ts can be determined by solving a system of five quadratic
equations, dictated by the ways in which the hexagonal-lattice groups touch
each other. Solving that system, we obtain s_ts = 15.994879..., a better
upper bound than s_t&t for the side length s of the optimal packing.

--------------------------------------------------------------------------

The triangle-shift archetype itself does not give the optimal packing in
this case. For comparison, at the above link, the archetype is shown at the
left and my packing for N = 68, having side length 15.994861..., is shown
at the right. Note that circles in group C and some circles in group B had
to be repositioned to get a better packing than the archetype. Of course,
my packing might not be optimal, but at least we can say that the optimal
packing's side length s <= 15.994861...

Since the optimal packings in the triangle-shift family do not necessarily
fit the archetype exactly, the family should be thought of as a "pattern
class", as the term is used in NACPS (p. 123), meaning that the archetype
provides a reasonable _approximation_ of the optimal packings in the
family. But there are cases in which the archetype gives exactly the
presumably optimal packing. One such case is already known, N = 247
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq247.html>, and others,
N = 1817 and 4106, will be newly presented below.

--------------------------------------------------------------------------

For another example, notice that, taking p = 26 and q = 15, p/q
overestimates sqrt(3) We will therefore be able to pack
N = ceiling((p + 1)(q + 1)/2) = 216 unit circles in a square using the
triangle-shift method. But whenever q is odd, as in this example, there
will be two different archetypal packings, depending on whether a unit
circle is centered at the vertex of A's right angle or not:

(1) The left figure at
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circs216sq.gif>
shows one of those archetypal packings. Presented earlier in this thread,
it is the best packing for N = 216 previously known, with
s_ts = 27.999895208... Note that it has two small equilateral-triangular
groups, D_1 and D_2, and that the remaining circles form a right-triangular
group X which is part of the same hexagonal lattice as C. Except for circle
#12, a rattler, the packing is rigid.

(2) The right figure at the above link shows a new packing, with side
length 27.99989448830799697857..., a modification of the other archetypal
packing. For that archetype, the circles near its upper left corner would
have been in a trapezoidal group X, part of the same hexagonal lattice as
C. But since there would have been extra space between X and the left side
of the square, the packing would not have been rigid. Adjusting circles to
take advantage of that extra space, we obtain the new, improved packing.

--------------------------------------------------------------------------

There is more to be said about general characteristics of this family.
In particular, it will be interesting to see what happens for large N.
But that will be covered in part 2. To conclude part 1, we give
various packings in the family, with comments. Several of these are
density record packings. And a few are noted as being suboptimal.

--------------------------------------------------------------------------
--------------------------------------------------------------------------

N = 418
p = 37, q = 21, p/q - sqrt(3) = 0.02985...
s = 38.913303138863028028609... suboptimal
(s = 38.913316... for the archetype)
1141 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ418sq.gif>

The best packing previously known has side length

s = 38.91369... and 1084 contacts.

The new packing is better than the archetype but is still suboptimal. Note
that circle #160 is a rattler. That implies that circle #184 is also loose,
and that implies that circles #183 and 202 are loose, etc... Looseness, in
this case, is a contagion which spreads throughout the whole packing. I
choose not to show all of the circles as rattlers simply because doing so
would have obscured the triangle-shift structure.

Also note that p is _odd_ here. The triangle-shift family was found by
searching for packings associated with fractions p/q which overestimate
sqrt(3) and have p even. But there is nothing which mandates, for this
family, that p must be even. Indeed, there are many good triangle-shift
packings with p odd.

--------------------------------------------------------------------------

N = 492
p = 40, q = 23, p/q - sqrt(3) = 0.0070796...
s = 41.99273551503355601001...
1371 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circs492sq.gif>

The best packing previously known has side length

s = 41.9951... and 567 contacts.

--------------------------------------------------------------------------

N = 780
p = 51, q = 29, p/q - sqrt(3) = 0.026569...
s = 52.8734833175458170929415...
(s = 52.8757... for the archetype)
2214 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ780sq.gif>

This packing is very neat. It improves on the archetype in a specific way
which will be seen in two other packings below, N = 1591 and 3203. As such,
it is worth describing carefully:

Referring to the figure, the archetype would have had a trapezoidal
hexagonal-lattice group in the upper left corner of the square. The
vertices of that trapezoid would have been the centers of circles #21 and
129 and the topmost points of circles #24 and 130. But of course that would
have left substantial space between the right side of the trapezoid and the
left side of the large right triangle C. To take advantage of that space,
we break the trapezoidal group into three pieces:

1) an equilateral-triangular group, its vertices being the centers of
circles #21, 24 and 94;
2) a right-triangular group, its vertices being the centers of circles #48,
95 and 96; and
3) a columnar group, consisting of circles #129 and 130.

This allows the side length of the square to be reduced, as shown.

--------------------------------------------------------------------------

N = 822
p = 52, q = 30, p/q - sqrt(3) = 0.00128...
s = 53.9995653581407481787552800908613... suboptimal
(s = 53.9995653581407481787552800908664... for the archetype)
2330 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/subopt822sq.gif>

This packing is suboptimal for the same reason that the packing given
above for N = 418 is suboptimal. In this case, circle #199 is loose,
implying that circle #236 can be loosened, implying that circles #235
and 261 can be loosened, etc. But even though not fully optimized,
this packing is still almost certainly a density record.

--------------------------------------------------------------------------

N = 1307
p = 66, q = 38, p/q - sqrt(3) = 0.00479...
s = 67.9910501032779180646275...
(s = 67.99105078... for the archetype)
3753 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ1307sq.gif>

--------------------------------------------------------------------------

N = 1591
p = 73, q = 42, p/q - sqrt(3) = 0.00604...
s = 74.9827631580596116369814...
4596 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ1591sq.gif>

This neat packing is improved over the archetype in the same way as
described above for N = 780.

--------------------------------------------------------------------------

N = 1817
p = 78, q = 45, p/q - sqrt(3) = 0.00128...
s = 79.99899806096441158999...
5268 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circs1817sq.gif>

This packing is archetypal and is almost certainly a density record.

--------------------------------------------------------------------------

N = 3203
p = 104, q = 60, p/q - sqrt(3) = 0.00128...
s = 105.9982427170894915127586...
(s = 105.99830... for the archetype)
9364 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ3203sq.gif>

This neat packing is almost certainly a density record. It is improved over
the archetype in the same way as described above for N = 780.

--------------------------------------------------------------------------

N = 4106
p = 118, q = 68, p/q - sqrt(3) = 0.00324...
s = 119.986708218048413640656...
12051 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ4106sq.gif>

This packing is archetypal.

--------------------------------------------------------------------------

N = 4978
p = 130, q = 75, p/q - sqrt(3) = 0.00128...
s = 131.99727650071032184727630... suboptimal
(s = 131.997283... for the archetype)
14607 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ4978sq.gif>

This packing is suboptimal. As shown, it is rigid, except of course for the
five rattlers, shown in red. But the circle at the top of the twelfth
column from the left could be repositioned slightly so that it would be a
rattler and then, as for N = 418, the looseness would spread... But even
though not fully optimized, this packing is still almost certainly a
density record.

--------------------------------------------------------------------------

David W. Cantrell

unread,

Jul 2, 2010, 12:22:09 AM7/2/10

In a recent response to James Waldby, before introducing the triangle-shift
family, I had said:
> ...take a look at N = 418. It does fit a family which I recognize
> (but haven't mentioned before) ... and N = 378 is in the same family
> as N = 418.

In this article, that family is introduced briefly and two improved
packings are presented.

--------------------------------------------------------------------------

Two examples of the family in question are N = 72
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq195.html> and N = 195
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq195.html>. A brief glance
at those packings should make the pattern evident. Like triangle-shift
packings, packings in the new family have two large right-triangular
hexagonal-lattice groups of unit circles and a large equilateral-triangular
group. The other circles are grouped in columns, rather than in the smaller
equilateral-triangular groups found in triangle-shift packings. Other known
members of the family include N = 90, 110, 132 and 224.

Curiously, the new family competes for more-or-less the same niche as the
column-shift and triangle-shift families when p is odd. At the time I
responded to James, the best packing known for N = 418 was indeed in the
new family, but that was soon bettered by a triangle-shift packing.

--------------------------------------------------------------------------

N = 378
s = 36.9647264079734566272461...
1017 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ378sq.gif>

The best packing previously known had
s = 36.9653... and 983 contacts. That packing didn't quite fit the
archetype for the family; the new packing does.

--------------------------------------------------------------------------

N = 672
s = 48.9835873486371916431324...
1836 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ672sq.gif>

The best packing previously known had
s = 48.9853... and 833 contacts. (And prior to that, the best packing known
was a column-shift packing, having s = 48.9857...)

--------------------------------------------------------------------------

David W. Cantrell

unread,

Jul 7, 2010, 8:07:08 PM7/7/10

Some triangle-shift packings as well as some packings obtained by
appending one or two columns to a triangle-shift packing are presented,
with comments.

--------------------------------------------------------------------------

N = 279 (triangle-shift)
s = 31.9300827952756442948399... suboptimal
748 contacts
shown at the left of
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ279sq.gif>

The best packing previously known had

s = 31.9316... and 573 contacts.

--------------------------------------------------------------------------

N = 280 (triangle-shift + col.)
s = 31.9789154528744276481019... suboptimal
752 contacts
shown at the right of
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ279sq.gif>

The best packing previously known had

s = 31.9812... and 223 contacts.

--------------------------------------------------------------------------

The packings for N = 279 and 280 were shown together at the above link for
the sake of comparison. It is not at all uncommon to have such a pair of
packings, in which the first is a fairly dense triangle-shift packing and
the second is formed by appending a column to a rhombic or triangle-shift
packing. But it is not so common to have a third packing in the group:
N = 281 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq281.html> is a
grid packing with three columns appended.

At least two more triplets of such packings are known. One of them is
(85, 86, 87), shown at
<http://hydra.nat.uni-magdeburg.de/packing/csq/d8.html>. The packing for
N = 85 is triangle-shift; the packing for N = 86 has an added column,
albeit inserted in the middle, rather than at a side, of the packing; and
the packing for N = 87 has three columns appended to a grid packing.
Another triplet is (585, 586, 587), the first two packings of which are
new, shown at
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ585sq.gif>,
and the last is shown at
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq587.html>.

Not surprisingly, of course, pairs of such packings are more frequent than
triplets. One of the earliest such pairs, shown at
<http://hydra.nat.uni-magdeburg.de/packing/csq/d6.html>, is N = 68
(triangle-shift) and N = 69 (grid + 2 cols.) Another pair is (247, 248) at
<http://hydra.nat.uni-magdeburg.de/packing/csq/d21.html>. Many other pairs
can already be found at Packomania, and several others, including (538,
539), (880, 881) and (941, 942), will be submitted soon.

--------------------------------------------------------------------------

N = 315 (triangle-shift + 2 cols.)
s = 33.9773612511606594854421...
810 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ315sq.gif>

The best packing previously known had

s = 33.9881... and 477 contacts.

(In the new packing, there are several circles which, although not
touching, are very close together. Since Packomania uses only 30
significant digits, it is likely that, when the new packing appears there,
the reported number of contacts will exceed 810.)

--------------------------------------------------------------------------

N = 896 (archetypal triangle-shift)
s = 56.6893643561340760085219...
2557 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ896sq.gif>

The best packing previously known had

s = 56.6991... and 516 contacts.

--------------------------------------------------------------------------

As noted in my initial posting about the triangle-shift family, such
packings are often difficult to optimize. Due to that difficulty, many of
my new packings (such as N = 279 and 280) have not been fully optimized and
the packings are not rigid. And when optimization is attempted, as for
N = 315 above, the resulting packing can be very messy (and may still not
be optimal).

But in some cases, the packings are at least local optima. For example,
N = 896 is archetypal. And N = 585 and 586, although not archetypal, are
very neat.

--------------------------------------------------------------------------

"The Triangle-Shift Family, Part 2", which will discuss behavior for large
N, is still being prepared.

David W. Cantrell

unread,

Jul 11, 2010, 5:56:40 PM7/11/10

Earlier in this thread, there was a brief detour in which packings of unit
circles in rectangles with length/width = 5 or 10 were considered. (The
first of the three posts in that detour is
<http://groups.google.com/group/sci.math/msg/df25a12618e2183d>.) Recently
at Packomania, Eckard Specht has added packings of circles in rectangles
with length/width = 10/3:
<http://hydra.nat.uni-magdeburg.de/packing/crc_300/crc.html>.
In this post, some improved packings of that type are given, together with
comments, including reasons why packings in (non-square) rectangles are or
are not interesting.

------------------------------------------------------------------------
Note: Packing _unit_ circles in the smallest possible rectangle with
length/width = 10/3, the smaller dimension, width, of that rectangle
equals the quantity now called "ratio" at Packomania.
------------------------------------------------------------------------

Several of my packings are only slight improvements of ones now shown at
Packomania. I will not be posting figures for some of the improved
packings, supposing that they will appear at Packomania in due course.
(Below, "new" and"old" give, resp., the number of contacts in my packing
and in the one currently shown at Packomania.)

N width new old contacts
31 6.219249170995002809467646... 63 53
43 7.106245261194258251113958... 101 95
47 7.375672753530237878952092... 95 78
49 7.605448432271752180308248... 90 82

---------------------------------------------------------------------------

Figures for improved packings for N = 46 and 50 are shown together at
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/4650in10x3.gif>.
Their widths are 7.199994466957570160112695... and
7.702329400757996835427410..., resp. The new packings are significant
improvements. For N = 46, the old packing had 35 contacts, while the new
has 115. For N = 50, the old packing had 104 contacts, while the new has
124.

By the way, we can sometimes give precise values in terms of radicals. For
example, for N = 50, the width is exactly

3/65 (62 + 45 sqrt(3) + 2 sqrt(420 sqrt(3) - 546))

---------------------------------------------------------------------------

N = 200
width = 14.99757249125798345467314...
536 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs200rect10x3.gif>

The best packing previously known had

width = 15.0160... and 503 contacts.

Note that the new packing happens to reduce the width to slightly less than
15. So if someone asks how many unit circles can be packed in a 50x15
rectangle, the answer is "At least 200."

---------------------------------------------------------------------------

General comments about packing unit circles in rectangles

It's interesting to compare packings in squares to packings in other
rectangles. Not surprisingly, one finds the same classic "modes" of packing
in both squares and other rectangles. For example, a glance at
<http://hydra.nat.uni-magdeburg.de/packing/crc_300/d3.html> will reveal
that the packings for N = 23, 24 and 26 are grid packings, while those for
N = 27 and 30 are row-shift packings (that is, a column-shift turned
sideways). But the packings for N = 46, 50 and 200 are of an even more
common type in which there are equilateral-triangular hexagonal-lattice
groups of circles. (These look a good bit like the upper left corner of
triangle-shift packings in squares.) As length/width increases, that type
of packing seems to become more dominant. And for packings of that type,
the messiness tends to be confined to the ends -- often just one end -- of
the rectangle. The packing shown above for N = 200 is a good example of
that phenomenon.

Due to the dominance of that type of packing and the fact that the messy
part is then often just at the ends of the rectangle, packings in
non-square rectangles tend to show less variety and to be easier than
packings in squares. For that reason, packing in squares is more
interesting to me. (Of course, I'm not saying that there are no messy cases
when the rectangle is not a square. The packing for N = 70 circles in a 5x1
rectangle
<http://hydra.nat.uni-magdeburg.de/packing/crc_200/crc70_0.200000000000.html>
comes to mind...)

David W. Cantrell

unread,

Jul 23, 2010, 4:48:53 PM7/23/10

The rhombic family of packings of unit circles in squares may be
generalized to obtain a new family: the parallelogramic family.
It contains some new packings which are almost certainly density
records, five of which are presented.

--------------------------------------------------------------------------

Grid packings were generalized to rhombic packings earlier in this thread.
But there are other, closely related packings which are not quite as
"regular" as rhombic packings. In the new family, unit circles are again
found in hexagonal-lattice groups. But those groups are not necessarily
rhombic; they can, more generally, be parallelogramic. Looking at some
already known packings of this type should make their structure clear:
N = 63 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq63.html>
N = 114 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq114.html>
N = 270 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq270.html>

It happens that none of those three examples are density record packings.
(A packing of N circles is a density record if the packing's density is
greater than that for any lesser number of circles.) But some
parallelogramic packings are almost certainly density records. Five such
packings are now given.

--------------------------------------------------------------------------

N = 572
s = (1934 + 2527*Sqrt[3] + 209*Sqrt[191 + 168*Sqrt[3]])/241
= 45.2253483317...
1311 contacts
symmetry group C_2
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs572sq.gif>

The best packing previously known had

s = 45.2253483323... and 663 contacts.

--------------------------------------------------------------------------

N = 765
s = (4715 + 6498*Sqrt[3] + 209*Sqrt[-5 + 1116*Sqrt[3]])/482
= 52.1717261201702...
1813 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs765sq.gif>

The best packing previously known had

s = 52.171733... and 673 contacts.

--------------------------------------------------------------------------

N = 1435
s = (7014 + 10469*Sqrt[3] + 209*Sqrt[5*(-619 + 580*Sqrt[3])])/482
= 71.2109...
3603 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs1435sq.gif>

The best packing previously known was a grid packing with
s = 71.2112... and 2871 contacts.

--------------------------------------------------------------------------

N = 3520
s = (3*(16222 + 24975*Sqrt[3] + 390*Sqrt[2601 + 4736*Sqrt[3]]))/2701
= 111.089354...
8235 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs3520sq.gif>

The best packing previously known was a grid packing with
s = 111.089363... and 7041 contacts.

--------------------------------------------------------------------------

N = 4838
s = (10*(6151 + 9720*Sqrt[3] + 117*Sqrt[-2997 + 7968*Sqrt[3]]))/2701
= 130.128734...
11681 contacts
symmetry group D_1
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs4838sq.gif>

The best packing previously known was a grid packing with
s = 130.128755... and 9678 contacts.

--------------------------------------------------------------------------

More parallelogramic packings will probably be posted later.

David W. Cantrell

unread,

Aug 5, 2010, 7:39:42 PM8/5/10

Archetypal parallelogramic packings can often be improved by modifying the
packing near a corner of the square. This leads, for example, to a packing
for N = 572 which is even better than the one posted previously. Other
examples are given. Particularly noteworthy is a packing for N = 1166,
which is almost certainly a density record.

--------------------------------------------------------------------------

David W. Cantrell <DWCan...@sigmaxi.net> wrote:
> The rhombic family of packings of unit circles in squares may be
> generalized to obtain a new family: the parallelogramic family.
> It contains some new packings which are almost certainly density
> records, five of which are presented.
>
> -------------------------------------------------------------------------
>

> Grid packings were generalized to rhombic packings earlier in this
> thread. But there are other, closely related packings which are not quite
> as "regular" as rhombic packings. In the new family, unit circles are
> again found in hexagonal-lattice groups. But those groups are not
> necessarily rhombic; they can, more generally, be parallelogramic.
> Looking at some already known packings of this type should make their
> structure clear:
> N = 63 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq63.html>
> N = 114 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq114.html>
> N = 270 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq270.html>
>
> It happens that none of those three examples are density record packings.
> (A packing of N circles is a density record if the packing's density is
> greater than that for any lesser number of circles.) But some
> parallelogramic packings are almost certainly density records. Five such
> packings are now given.
>
> -------------------------------------------------------------------------
>

> N = 572
> s = (1934 + 2527*Sqrt[3] + 209*Sqrt[191 + 168*Sqrt[3]])/241
> = 45.2253483317...
> 1311 contacts
> symmetry group C_2
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs572sq.gif>
>
> The best packing previously known had
> s = 45.2253483323... and 663 contacts.
>
> -------------------------------------------------------------------------

An even better packing for N = 572, having
s = 45.225318524066822595891... and 1514 contacts, is shown at
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/bettr572sq.gif>.

The new packing, unlike the previous one, is not archetypal. Although It
does largely consist of parallelogramic hexagonal-lattice groups of circles
(or portions of such groups, produced by truncations at sides of the
square), this regularity breaks down in a corridor leading into the lower
left corner of the square. (And due to this breakdown of regularity, the
side length s cannot be given neatly, in terms of radicals, as can be done
for archetypal parallelogramic packings.)

The parallelogramic family is now seen to be like the triangle-shift family
in the sense that, in both families, many optimal packings are not
archetypal, requiring some breakdown in regularity in order to achieve
optimality. Both families may be considered as "structure classes", rather
than "pattern classes", so that their archetypes provide at least fair
approximations of optimal packings. (For example, the archetypal packing
which was modified to give the new packing for N = 572 had s = 45.225320...)

Another packing in the family which is not archetypal and also almost
certainly a density record is

-------------------------------------------------------------------------

N = 1166
s = 64.264381294241885680772...
3196 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs1166sq.gif>
Regularity breaks down in a corridor leading to the lower right corner.

The best packing previously known had

s = 64.26447... and 121 contacts.

-------------------------------------------------------------------------

Some optimal packings are, presumably, given by archetypal members of the
parallelogramic family. Two of these are given below.

-------------------------------------------------------------------------

N = 368 archetypal
s = (12*(122 + 156*Sqrt[3] + 7*Sqrt[-219 + 572*Sqrt[3]]))/193
= 36.47630...
879 contacts
symmetry group D_1
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs368sq.gif>

The best packing previously known had

s = 36.47646... and 894 contacts.

--------------------------------------------------------------------------

N = 525 archetypal
s = (1807 + 2448*Sqrt[3] + 84*Sqrt[-936 + 986*Sqrt[3]])/193
= 43.42327...
1300 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs525sq.gif>

The best packing previously known had

s = 43.42368... and 340 contacts.

-------------------------------------------------------------------------

David W. Cantrell

unread,

Aug 19, 2010, 11:26:06 AM8/19/10

Three new parallelogramic packings are presented. Of those, N = 6975 is
particularly noteworthy, being almost certainly a density record.

Also, an improved packing for N = 145 is given.

--------------------------------------------------------------------------

N = 864 archetypal
s = (2395 + 3456*Sqrt[3] + 84*Sqrt[3*(-879 + 656*Sqrt[3])])/193
= 55.515069...
2226 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs864sq.gif>

The best packing previously known had

s = 55.515086... and 602 contacts.

-------------------------------------------------------------------------

N = 924
s = 57.317614713098158235127...
2508 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs924sq.gif>
This is not archetypal. In order to optimize the packing, adjustments
were made in a corridor leading to the upper left corner.

The best packing previously known had

s = 57.3176194... and 1646 contacts.

-------------------------------------------------------------------------

N = 6975 archetypal
s = (3*(26362 + 42525*Sqrt[3] + 390*Sqrt[6*(-2164 + 2289*Sqrt[3])]))/2701
= 156.114321...
17404 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs6975sq.gif>

The best packing previously known was a grid packing with

s = 156.114348... and 13951 contacts.

-------------------------------------------------------------------------

N = 145
s = 23.3255972498280200689273967175...
312 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs145sq-2.gif>

The best packing previously known had

s = 23.32559772... and 163 contacts.

-------------------------------------------------------------------------

David W. Cantrell

unread,

Aug 31, 2010, 8:53:22 PM8/31/10

Improved packings are presented for N = 168, 170, 171, 172 and 175.

With these improvements, there are now, among the best packings known,
none for N <= 175 which are obviously suboptimal.

--------------------------------------------------------------------------

N = 168
s = 24.93616296500179481333...
342 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs168sq.gif>

The best packing previously known had

s = 24.93616296516... and 325 contacts.

--------------------------------------------------------------------------

N = 170
s = 25.25279220969683927488...
360 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs170sq-1.gif>

The best packing previously known had

s = 25.252792211... and 339 contacts.

--------------------------------------------------------------------------

N = 171
s = 25.325602865303967650481369403760896752685698752050...
404 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs171sq.gif>

The best packing previously known had 390 contacts. To the 30
significant digits shown at Packomania, its side length s is the same
as that of the new packing.

--------------------------------------------------------------------------

N = 172
s = 25.417250625164150300920405020304443...
383 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs172sq.gif>
[When this packing appears at Packomania (which uses only 30 significant
digits), the number of contacts will probably be inflated because some of
the circles which do not touch are very close to each other.]

The best packing previously known had

s = 25.417283... and 346 contacts.

--------------------------------------------------------------------------

N = 175
s = 25.600918082125163887335375372637...
398 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs175sq-1.gif>

The best packing previously known had

s = 25.600918082135... and 371 contacts.

--------------------------------------------------------------------------

David W. Cantrell

spudnik

unread,

Aug 31, 2010, 10:54:05 PM8/31/10

so, what is the ultimate criterion,
for "really ideal pennies'd actually touch?"

> N = 172
> s = 25.417250625164150300920405020304443...
> 383 contacts

> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs17...>

> [When this packing appears at Packomania (which uses only 30 significant
> digits), the number of contacts will probably be inflated because some of
> the circles which do not touch are very close to each other.]
>
> The best packing previously known had
> s = 25.417283... and 346 contacts.

thus:
hey; don't dodge the strawman!

> No it's really simple, your guys lied about the data, including what
> data was used in their research, how it was used, what effect certain
> data sources had on the results etc. They lied about what they did to
> cover up the lies and about whether they were obeying FOI laws. Then
> they set up whitewashing commissions and lied that they had been
> cleared by independent investigations, which none of them had been.

thus:
skimmed, and he made a good point about the Koch Bros.
funding of anti-warming, compared to Gore's fundings ...
which is odd, because he's not quite that rich, although
he has his own hedge-fund in Britain!... so,
how much has he invested in the huge,
voluntary cap&trade?

thus: oil is biomass, that comes out of the ground by itself,
under pressure, viz the Redondo Seep (off Los Angeles)
and "Organic Seeps of Oil in the Gulf of Mexioc,"
an old Sci.Am. article.
so, how much biomass does Earth produce per annum, and
where does it all, go?
every technology has its problems, and
the "renewable" ones problems will soon be known -- although
it wouldn't hurt to go to a U. in the Netherlands,
to learn the downsides of tilting with windmills, in advance!

thus: the Skeptics were a Delphic cult under the Roman Pantheon,
til Xianity became the state church a l'Angleterre (and
its Harry Potter PS#1, Oxford .-)
the court is of little scientific concern, although
Congress is under enormous creditor pressure to pass
the cap&trade "free-er trade" nostrum, in order
to vastly cut the amount of oil bought form abroad; so,
what happened with Waxman's original cap&trade,
'91's bill on NOX and SO2 per acid rain?
of course, there is a reason,
why the conspiracy to kill JFK, happened
to involve the patsy, working at the Texas Textbook Suppository!

thus: so, tell us, again, why oilcos are against cap&trade,
UNIPCC etc., please, Erwin. and, how's the funny cat?

thus: Bjorn's change-of-heart could have been predicted, since
he espoused his views in the Holy Economist guest editorial
-- the only thing that is ever signed by an author in it. so,
naturally, he is a proponent of bpTM's old KyotoTM cap&tradeTM,
and my Rep. Waxman's and my California Assemblywoman's
(now Senator) cap& trade variants, a.k.a. "free-er trade
on the free market -- free beer &or freedom!"
and, of course, one of Bjorn's telltales is that
cold generally leads to more deaths than heat,
per annum.

thus: What would you expect the result of "Al-bombplane
plus Fe-superstructure" to be, than what it was?
isn't all of Nature, essentially, nanotech?

thus: as can be seen from the constructions
of the Greeks, obscured by Euclid,
there is nothing remotely dimensionless
about numbers. however, the fact remains that
numbers as used for accounting & mensurement are inherently
and totally dimensionless -- so that you can use (or
abuse) what ever units are required in the wordproblemma;
then, expertise often drops the units in shorthand.
the rest of your stuff is indeed too vague, and
apparently New Agey, to bother with; I mean,
2012 is just the end of one calendric cycle;
so, What?

thus: interesting; what is Poincare's misequivocation
of Lorenz and Larmor?... as for Newton,
he stole that from Hooke, then burnt all
of his portraits -- "ahahaha,
on the shoulders of that clever little dwarf!" (viz,
Sir I., the plagiarist, Freemason, alchemist-
who-burnt-his-"Principles"-in-an-accident-and-
had-it-"reconstructed"-by-the-RS-with-the-dydx-rectangle
etc. ad vomitorium .-)

thus: Euclid's proof is so simple, that
it takes a truly linguistically challenged individual
to dyss it; after all, all
of math problems are, really, wordproblemmas!

thus: as for ordinary spatial finite elements,
you really need tetrahedronometry; eh?

--les ducs d'Enron!
http://tarpley.net

--Light, A History!
http://wlym.com/~animations/fermat/index.html

David W. Cantrell

unread,

Sep 13, 2010, 11:12:03 PM9/13/10

Improved packings are presented for N = 261 and 330. These packings
are members of a family which, for example, also includes my previous
packing for N = 154
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq154.html>.
More details about this family will be posted later.

--------------------------------------------------------------------------

N = 261
s = 31.0212311148607906225098521603...
647 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs261sq.gif>
The presumably optimized packing is shown at the right; the archetypal
packing, having
s = 4/5 * (9 + 16*Sqrt[3] + 2*Sqrt[-89 + 52*Sqrt[3]]) = 31.0227...,
is shown at the left. The archetype provides a substantially better
approximation to the presumably optimized packing than does the grid
packing, which has s = 2 + 952/Sqrt[1073] = 31.0627...

The best packing previously known had

s = 31.02123111486079074... and 578 contacts.

--------------------------------------------------------------------------

N = 330
s = 34.6656481672768168515993094803...
874 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs330sq.gif>
(The grid packing has s = 2 + 1216/Sqrt[1385] = 34.6744...
while the archetypal packing has
s = 4/5 * (10 + 18*Sqrt[3] + Sqrt[-463 + 270*Sqrt[3]]) = 34.6673...)

The best packing previously known had

s = 34.66564816748... and 794 contacts.

--------------------------------------------------------------------------

David W. Cantrell

unread,

Sep 27, 2010, 4:36:02 PM9/27/10

David W. Cantrell <DWCan...@sigmaxi.net> wrote:

> Improved packings are presented for N = 261 and 330. These packings
> are members of a family which, for example, also includes my previous
> packing for N = 154
> <http://hydra.nat.uni-magdeburg.de/packing/csq/csq154.html>.
> More details about this family will be posted later.

This family is a degenerate subfamily of the family of parallelogramic
packings. It is useful to contrast this subfamily with the best known
degenerate subfamily, the grid packings. In the parallelogramic family, the
grid packings are the "finest" in the sense that each hexagonal-lattice
group of circles consists of just one circle. Many grid packings are
density-record packings.

By contrast, the subfamily which includes N = 154, 261 and 330 has the
coarsest parallelogramic packings. The archetype for this subfamily
consists of three large hexagonal-lattice groups, as shown in the figure at
the left in the link below for N = 261. Unlike grid packings, the archetype
for this subfamily never provides an optimal packing in a square. (But in
non-square rectangles, such an archetypal packing may be optimal. See
<http://hydra.nat.uni-magdeburg.de/packing/crc_800/crc132_0.800000000000.html>,
for example.) Modifying the archetype in an attempt to optimize a
packing is often difficult and, even when optimized, such packings are
seemingly never highly dense. Below, inserted in numerical order, are five
more attempted optimizations in this subfamily: N = 295, 396, 437, 559 and
608.

> -------------------------------------------------------------------------
>
> N = 261
> s = 31.0212311148607906225098521603...
> 647 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs261sq.gif>
> The presumably optimized packing is shown at the right; the
> archetypal packing, having
> s = 4/5 * (9 + 16*Sqrt[3] + 2*Sqrt[-89 + 52*Sqrt[3]]) = 31.0227...,
> is shown at the left. The archetype provides a substantially better
> approximation to the presumably optimized packing than does the grid
> packing, which has s = 2 + 952/Sqrt[1073] = 31.0627...
>
> The best packing previously known had
> s = 31.02123111486079074... and 578 contacts.
>
-------------------------------------------------------------------------

N = 295
s = 32.84722079316941550069509743805953588164380603008...
767 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs295sq.gif>

The best packing previously known is reported at Packomania to have 763
contacts and side length s = 32.8472207931694155006950974376, which is
_smaller_ by about 5*10^-28 than that of my supposedly improved packing.
But I doubt that the last two digits there are actually correct.
(Supporting my doubt, I note that the value of s reported at Packomania for
my own packing for N = 369 is too small by about 6*10^-28.) I assume that
my packing, which has four more contacts, is a actually minute improvement.

-------------------------------------------------------------------------
>
> N = 330
> s = 34.6656481672768168515993094803...
> 874 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs330sq.gif>
> (The grid packing has s = 2 + 1216/Sqrt[1385] = 34.6744...
> while the archetypal packing has
> s = 4/5 * (10 + 18*Sqrt[3] + Sqrt[-463 + 270*Sqrt[3]]) = 34.6673...)
>
> The best packing previously known had
> s = 34.66564816748... and 794 contacts.
>
-------------------------------------------------------------------------

N = 396
s = 37.9752023477038158276526086976...
1048 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs396sq.gif>

The best packing previously known had

s = 37.97520254... and 593 contacts.

-------------------------------------------------------------------------

N = 437
s = 39.7990967295913438878197556569...
1151 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs437sq.gif>

The best packing previously known had

s = 39.7990975... and 569 contacts.

-------------------------------------------------------------------------

N = 559
s = 44.9292181069589788820408600419...
1485 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs559sq.gif>

The best packing previously known had

s = 44.9292181076... and 889 contacts.

-------------------------------------------------------------------------

N = 608
s = 46.7507427933279645562080145692...
1642 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs608sq.gif>

The best packing previously known had

s = 46.7507427945... and 1302 contacts.

-------------------------------------------------------------------------

David W. Cantrell

unread,

Oct 8, 2010, 10:00:52 PM10/8/10

A formula for side length s of archetypal packings in the "coarse"
subfamily is given. And it is noted that using just the archetype itself
gives some packings which are better than those previously known.

David W. Cantrell <DWCan...@sigmaxi.net> wrote:
> David W. Cantrell <DWCan...@sigmaxi.net> wrote:
> > Improved packings are presented for N = 261 and 330. These packings
> > are members of a family which, for example, also includes my previous
> > packing for N = 154
> > <http://hydra.nat.uni-magdeburg.de/packing/csq/csq154.html>.
> > More details about this family will be posted later.
>
> This family is a degenerate subfamily of the family of parallelogramic
> packings. It is useful to contrast this subfamily with the best known
> degenerate subfamily, the grid packings. In the parallelogramic family,
> the grid packings are the "finest" in the sense that each
> hexagonal-lattice group of circles consists of just one circle. Many grid
> packings are density-record packings.
>
> By contrast, the subfamily which includes N = 154, 261 and 330 has the
> coarsest parallelogramic packings. The archetype for this subfamily
> consists of three large hexagonal-lattice groups, as shown in the figure
> at the left in the link below for N = 261.

For an example of the archetype, now see N = 658 below.

> Unlike grid packings, the
> archetype for this subfamily never provides an optimal packing in a
> square. (But in non-square rectangles, such an archetypal packing may be
> optimal. See
<http://hydra.nat.uni-magdeburg.de/packing/crc_800/crc132_0.800000000000.html>,
> for example.) Modifying the archetype in an attempt to optimize a
> packing is often difficult and, even when optimized, such packings are
> seemingly never highly dense. Below, inserted in numerical order, are
> five more attempted optimizations in this subfamily: N = 295, 396, 437,
> 559 and 608.

[snip]

Let p/q be a ratio of natural numbers which underestimates sqrt(3). Then
the side length of the associated archetypal packing in the "coarse"
subfamily previously described is

s = (8 + p + 4 sqrt(3)(q - 1) + 2 sqrt(20 - (2 - p + sqrt(3)(q - 1))^2))/5

Although these archetypal packings are never optimal, the following table
shows that the side length of the archetype provides a fair approximation
for the side length of the best packing currently known.

N s_archetype s_bestknown
154 24.0679... 24.0662...
261 31.0227... 31.0212...
295 32.8488... 32.8472...
330 34.6673... 34.6656...
396 37.9768... 37.9752...
437 39.8009... 39.7990...
559 44.9304... 44.9292...
608 46.7524... 46.7507...

For some larger values of N, the archetype is actually a better packing
than any previously known. For example,

-------------------------------------------------------------------------

N = 658 archetype, suboptimal
s = 2*(27 + 52*Sqrt[3] + 2*Sqrt[-986 + 572*Sqrt[3]])/5
= 48.56710...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs658sq.gif>

The best packing previously known had

s = 48.56762...

-------------------------------------------------------------------------

Other instances for N <= 1000 in which the archetype is better than the
best packing previously known are N = 908, 952 and 998.

David W. Cantrell

unread,

Oct 22, 2010, 10:20:39 PM10/22/10

Improved packings of unit circles in squares are presented for N = 176,
185, 187, 192, 193, 194, 197, 198 and 199. Now, for N <= 200, the only
packings remaining which are obviously suboptimal are those for N = 177
and 179.

--------------------------------------------------------------------------

N = 176
s = 25.64706687540434307884...
407 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs176sq.gif>

The best packing previously known had

s = 25.647066875425... and 342 contacts.

-------------------------------------------------------------------------

N = 185
s = 26.14703866250858135322...
395 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs185sq.gif>

The best packing previously known had

s = 26.1470386688... and 358 contacts.

-------------------------------------------------------------------------

N = 187
s = 26.17728097165601133351...
399 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs187sq.gif>

The best packing previously known had

s = 26.1772809723... and 344 contacts.

-------------------------------------------------------------------------

N = 192
s = 26.70630925056512848248...
461 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs192sq.gif>

The best packing previously known had

s = 26.706309268... and 456 contacts.

-------------------------------------------------------------------------

N = 193
s = 26.79237498834520324044...
437 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs193sq.gif>

The best packing previously known had

s = 26.79237500... and 405 contacts.

-------------------------------------------------------------------------

N = 194
s = 26.84012646309309443561884947460428552...
450 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs194sq.gif>

The packing currently shown at Packomania has 447 contacts and is reported
to have s = 26.8401264630930944356188494743, but that last digit appears
to be incorrect. My packing's side length is smaller by approximately
2*10^-33 than that of Packomania's current packing.

-------------------------------------------------------------------------

N = 197
s = 27.12109121127510685014...
458 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs197sq.gif>

The best packing previously known had

s = 27.12109121127597... and 434 contacts.

-------------------------------------------------------------------------

N = 198
s = 27.194835943337079267583292124599522...
506 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs198sq.gif>

The best packing previously known had

s = 27.1948359433370792675832921248 and 502 contacts.

-------------------------------------------------------------------------

N = 199
s = 27.27216320164192489802...
424 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs199sq.gif>

The best packing previously known had

s = 27.272163234... and 398 contacts.

-------------------------------------------------------------------------

David W. Cantrell

unread,

Nov 11, 2010, 5:11:12 PM11/11/10

Improved packings of unit circles in squares are presented for

N = 209, 233, 234, 239, 243 and 245.

-------------------------------------------------------------------------

N = 209
s = 27.81642889733278214924...
527 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs209sq.gif>

The best packing previously known had

s = 27.8164288973330... and 518 contacts.

-------------------------------------------------------------------------

N = 233
s = 29.37201960549641944558...
583 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs233sq.gif>

The best packing previously known had

s = 29.3720196054988... and 524 contacts.

-------------------------------------------------------------------------

N = 234
s = 29.39929721027308715071...
536 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs234sq.gif>

The best packing previously known had

s = 29.39929721043... and 478 contacts.

-------------------------------------------------------------------------

N = 239
s = 29.62101382756905204722...
511 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs239sq.gif>

The best packing previously known had

s = 29.621026... and 481 contacts.

-------------------------------------------------------------------------

N = 243
s = 29.86107637657945596553...
571 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs243sq.gif>

The best packing previously known had

s = 29.861076676... and 492 contacts.

-------------------------------------------------------------------------

N = 245
s = 29.94989366645933273114...
602 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs245sq.gif>

The best packing previously known had

s = 29.949988... and 575 contacts.

-------------------------------------------------------------------------

David W. Cantrell

unread,

Dec 3, 2010, 5:21:14 PM12/3/10

An improved packing of 92 unit circles in a square is presented.

-------------------------------------------------------------------------

The packing, which appeared earlier in this thread, of 92 unit circles in a
square is still shown at
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs92sq.gif>.
It has side length s = 18.75571398383... and symmetry group C_2.

In October, Milos Tatarevic announced an improved packing. He has now
finished his work on that packing. It can currently be seen at
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq92.html>. It is not quite
symmetric and, according to Packomania, has s = 18.75571398360720... and
157 contacts.

But that packing can again be improved slightly, giving
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs92sq.gif>
which has s = 18.75571398360715229907... and 190 contacts. And, nicely,
this improvement restores symmetry group C_2.

David W. Cantrell

unread,

Dec 28, 2010, 10:43:48 PM12/28/10

Improved packings of 67, 130, 144, 170 and 193 unit circles in squares
are presented.

-------------------------------------------------------------------------

Earlier in this thread, a packing of 67 unit circles in a square was
presented.

Recently, Milos Tatarevic found a better packing, which can currently
be seen at <http://hydra.nat.uni-magdeburg.de/packing/csq/csq67.html>.
It has side length s = 15.977649302975335440506... and 105 contacts,
according to Packomania.

But that packing can again be improved slightly, giving

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs67sq.gif>
with s = 15.9776493029753354404870596956... and 142 contacts.
This is a density record packing.

-------------------------------------------------------------------------

N = 130
s = 22.20092806886289872968...
277 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs130sq.gif>

The best packing previously known had

s = 22.20092806904... and 274 contacts.

-------------------------------------------------------------------------

N = 144
s = 23.25376756300669450735...
332 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs144sq.gif>

The best packing previously known had

s = 23.253767563035... and 330 contacts.

-------------------------------------------------------------------------

N = 170
s = 25.25269897314905352089...
355 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs170sq.gif>

The best packing previously known had

s = 25.25269897419... and 299 contacts.

-------------------------------------------------------------------------

N = 193
s = 26.79237494767169938041...
429 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs193sq.gif>

The best packing previously known had

s = 26.792374968... and 353 contacts.

-------------------------------------------------------------------------

David W. Cantrell

unread,

Jan 24, 2011, 12:37:32 AM1/24/11

This article is mainly concerned with density-record packings of unit
circles in squares. A possible definition of _primary density record_
is given (and suggestions for a better definition are invited).

Also, five packings in a new family, three of which are density records,
are presented.

##########################################

Clumping of density records; primary density records

A packing of N unit circles in a square is a _density record_ if its
density is greater than that of any packing of fewer unit circles in a
square. Packomania now maintains a list of density records:
<http://hydra.nat.uni-magdeburg.de/packing/csq/txt/records.txt>. [The
beginning of that list is currently N = 2, 3, 4, 9, 30, 38, 39,... But
I suggest that it should actually begin with N = 1. And since the
packings for N = 1, 4 and 9 are all square-lattice packings and hence
have the same density, the beginning of my list of density records is
N = 1, 30, 38, 39,...]

A portion of Packomania's list, reformatted to emphasize consecutive
density records, is
N: density
67: 0.8245; 68: 0.8350;
99: 0.8402;
119: 0.8450; 120: 0.8516;
186: 0.8542; 187: 0.8573; 188: 0.8613;
215: 0.8615; 216: 0.8655;
303: 0.8674; 304: 0.8699;
339: 0.8700; 340: 0.8723;
407: 0.8726;
446: 0.8728; 447: 0.8743; 448: 0.8763; 449: 0.8781
It may initially seem surprising that density records tend to be found
in "clumps" of two or more consecutive N, but there is a simple
explanation for this phenomenon.

To illustrate, let's consider the packing for N = 188:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq188.html>. This grid
packing is sufficiently denser than the packing for N = 120 that we
can say, _a priori_, that the packings for N = 187 and 186 must be
denser than that for N = 120. Why? Because if we simply remove any one
or two circles from the packing for N = 188, we get packings for
N = 187 and 186, respectively, having densities
187/188 * 0.8613... = 0.8567... and 186/188 * 0.8613... = 0.8521...
(Of course, packings produced in that way are not optimal because, after
removing one or two circles, the remaining circles can then be readjusted
to give a slightly denser packing. Possibly optimal packings for N = 186
and 187 were presented earlier in this thread and are now shown at
Packomania.) In this sense, the packings for N = 186 and 187 have high
densities simply because they are "derived" from the packing for N = 188,
whose density is outstanding. For this reason, we may wish to have a term
to distinguish such outstanding packings. I propose "primary density
record", for which a possible definition would be

A packing of N unit circles in a square is a _primary density record_
if it is a density record and the packing for (N + 1) is not also a
density record.

Although the definition is simple and probably gives precisely those
packings which we want to call primary density records, I still have
misgivings about it. Hence, I welcome suggestions for other ways of
defining primary density record.

Every packing which is a primary density record consists of circles
which are very close to being in a single hexagonal lattice. And every such
packing is a member of one of three families, discussed earlier in this
thread:

parallelogramic (such as N = 572
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq572.html>),

column-shift (such as N = 30
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq30.html>) or

triangle-shift (such as N = 216
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq216.html>).

This makes it fairly easy to find N for which the packings are primary
density records. All such N < 10^4 are presumably known now and
Packomania shows packings (albeit not necessarily optimal ones) for
all of them. If a packing for N is a primary density record, then
apparently we always have

N = ceiling( (round(q*sqrt(3)) + 1)*(q + 1)/2 )

for some nonnegative integer q.

##########################################

Nonprimary density records

Since primary-density-record packings can be found fairly easily and
the other density-record packings are derived from the primary ones,
it might seem that we should be able to identify N for those other
density records without much trouble, just as we had done above for
N = 187 and 186. But, as we shall see, that is only partially true.

As an example of what can be done trivially, let's consider
density-record packings which can be derived from the grid packing for
N = 8281, a primary density record. The density of that packing is
p(8281) = 0.900120... (where p(x) denotes the density of the packing
of x unit circles), while the density of the previous
primary-density-record packing is p(7614) = 0.899632... After solving
the inequality x/8281 * p(8281) > p(7614) and obtaining
x > 8276.50..., we can guess confidently that the four previous packings,
for N = 8277-8280, will all be density records and that there will be
no other density records between N = 7614 and 8281.

In that way, we may now list those packings which are not in
Packomania's current list of density records but which will almost
certainly be density records:

1233-1234, 1509-1511, 1816, 2057, 2408-2411, 2790-2792, 3202, 3519,
3974-3977, 4462-4463, 5369-5371, 5931-5934, 7610-7613, 8277-8280 and
9502.

Below, we give new packings for N = 2792 and 4463, which are indeed
density records.

But matters are not always clear _a priori_. For example, N = 304 and
340 are successive primary density records. Solving x/340 * p(340) >
p(304), we obtain x > 339.089... and so it might seem that the packing
for N = 339 would not be a density record. But remember that, after
removing a circle from the packing for N = 340, we must readjust the
remaining 339 circles to get an optimal packing, and that readjustment
will give a packing having density slightly greater than 339/340 *
p(340) = 0.869767..., which is only slightly less than p(304) =
0.869996... In fact, the packing for N = 339 is a density record and,
below, we give a new packing having density 0.870019... For N < 10^4,
there are several other packings, like that for N = 339, for which we
do not know _a priori_ whether they should be density records or not.

##########################################

Five packings in a new family

Normally, when a circle is removed from a primary-density-record
packing for N, it is difficult to decide how the remaining circles
should be readjusted to give an optimal packing for N-1. But when the
packing for N happens to be in the column-shift family, it seems that
there may be a fairly simple pattern for the optimal packing for N-1.
These packings then form a new family, and it contains a few density
records. An early member of this family is the packing for 29 unit
circles: <http://hydra.nat.uni-magdeburg.de/packing/csq/csq29.html>.
In some cases, however, we have a packing in this family even when the
next packing does not happen to be a column-shift packing; an example
of this is the packing for 167 unit circles:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq167.html>. Below are
five more members of this new family, including three density records.

----------------------------------------------------------------------

N = 339 density record
s = 34.987295962620721948137873...
808 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs339sq.gif>

The best packing previously known had

s = 34.98732... and 787 contacts.

---------------------------------------------------------------------

N = 671
s = 48.980075668871131423336106...
1492 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs671sq.gif>

The best packing previously known had

s = 48.98020... and 803 contacts.

---------------------------------------------------------------------

Figures have not been prepared for the three packings below because
they are very much like the previous packings in the family. [Caution:
When the figures do appear at Packomania, the numbers of contacts
indicated there for N = 2792 and 4463 will be too large by approx. 6
and 12, resp., due to the fact that Packomania is currently limited to
using 30 significant digits.]

----------------------------------------------------------------------

N = 1049
s = 60.99289662850851725893877591...

----------------------------------------------------------------------

N = 2792 density record
s = 98.99980464083631431240961560...

----------------------------------------------------------------------

N = 4463 density record
s = 124.99931347401480898322986621...

----------------------------------------------------------------------

David W. Cantrell

unread,

Feb 11, 2011, 5:48:16 PM2/11/11

Several comments are inserted below, including a reason for disliking the
definition of primary density record. Also, improved packings are given for
N = 336, 338, 410, 411 and 413, which are members of a broad,
loosely-defined family.

David W. Cantrell <DWCan...@sigmaxi.net> wrote:

> This article is mainly concerned with density-record packings of unit
> circles in squares. A possible definition of _primary density record_
> is given (and suggestions for a better definition are invited).
>
> Also, five packings in a new family, three of which are density
> records, are presented.
>
> ##########################################
>
> Clumping of density records; primary density records
>
> A packing of N unit circles in a square is a _density record_ if its
> density is greater than that of any packing of fewer unit circles in
> a square. Packomania now maintains a list of density records:
> <http://hydra.nat.uni-magdeburg.de/packing/csq/txt/records.txt>.
> [The beginning of that list is currently N = 2, 3, 4, 9, 30, 38, 39,...
> But I suggest that it should actually begin with N = 1. And since the
> packings for N = 1, 4 and 9 are all square-lattice packings and
> hence have the same density, the beginning of my list of density
> records is N = 1, 30, 38, 39,...]

Packomania's list of density records now begins that way:

N = 1, 30, 38, 39,...

By the way, I have a guess as to why Eckard had previously excluded N = 1.
If we are packing circles in _circles_, then density = 1 for N = 1 and so
there could be no other density records thereafter. Thus, for circles in
circles, it's actually useful to consider density records beginning with
N = 2. And so perhaps that influenced him to do the same with packings of
circles in squares.

I dislike the above definition of primary density record because it has
nothing to do with a packing's independence (i.e., not being "derived")
from another packing.

Suppose that we generalize that definition so that it applies to packings
of circles in rectangles and then consider the packings for N = 64 and 65
in a rectangle having width/length = 0.8:
<http://hydra.nat.uni-magdeburg.de/packing/crc_800/crc64_0.800000000000.html>
and
<http://hydra.nat.uni-magdeburg.de/packing/crc_800/crc65_0.800000000000.html>.
These are both density records. Yet clearly the packing for N = 64 is in no
way "derived" from the packing for N = 65 and so both packings actually
deserve to be called primary density records. But according to the
generalized definition, the packing for N = 64 would not be a primary
density record.

> Hence, I welcome suggestions for other ways of defining primary
> density record.

[snip]

> ##########################################
>
> Five packings in a new family
>
> Normally, when a circle is removed from a primary-density-record
> packing for N, it is difficult to decide how the remaining circles
> should be readjusted to give an optimal packing for N-1. But when the
> packing for N happens to be in the column-shift family, it seems that
> there may be a fairly simple pattern for the optimal packing for N-1.
> These packings then form a new family, and it contains a few density
> records.

By the way, in cases when a column-shift packing for N does not happen
to be a density record, the optimal packing for N-1 is often not in
that new family. As an example, consider the packings for 56 and 55,
shown at <http://hydra.nat.uni-magdeburg.de/packing/csq/d5.html>.

> An early member of this family is the packing for 29 unit
> circles: <http://hydra.nat.uni-magdeburg.de/packing/csq/csq29.html>.
> In some cases, however, we have a packing in this family even when the
> next packing does not happen to be a column-shift packing; an example
> of this is the packing for 167 unit circles:
> <http://hydra.nat.uni-magdeburg.de/packing/csq/csq167.html>. Below are
> five more members of this new family, including three density records.
>
> ----------------------------------------------------------------------
>
> N = 339 density record
> s = 34.987295962620721948137873...
> 808 contacts
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs339sq.gif>
>
> The best packing previously known had
> s = 34.98732... and 787 contacts.
>
> ---------------------------------------------------------------------

Removing two circles from a column-shift packing for N and then readjusting
to optimize the packing for the remaining N-2 circles is somewhat messy,
but there does seem to be a pattern. Consider packings for 141-143:
<http://hydra.nat.uni-magdeburg.de/packing/csq/d12.html>. Removing one
circle from the column-shift packing for 143 and readjusting, we get the
packing for 142, which is in the previously described family. Removing two
circles (one at top and the other at bottom) from the packing for 143 and
readjusting, we get the packing for 141. This packing does not have
symmetry but, if we remove its eleven rightmost circles, the remaining
circles have symmetry group C_2. This is significant. The packing for 143
has an odd number of columns, and so the packing for 141 could not, as a
whole, have C_2 symmetry. But when the packing for N has an even number of
columns, it seems that we often get a packing for N-2 which has C_2
symmetry. One example of this is the packing for 166:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq166.html>.
Another example is the new packing

----------------------------------------------------------------------

N = 338
s = 34.974622430319046160367257...
741 contacts
symmetry group C_2
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs338sq.gif>

The best packing previously known had

s = 34.97462243087... and 684 contacts.

---------------------------------------------------------------------

All of the above packings could be considered to be in a broad,
loosely-defined family in which circles which are not close to the top or
bottom of the square are all arranged in columns. Such packings tend to
occur in groups when the side length s is a bit larger than 2 + p sqrt(3)
for some integer p. A good example is the group of packings for N =
163-167: <http://hydra.nat.uni-magdeburg.de/packing/csq/d14.html>; note
that 2 + 13 sqrt(3) = 24.516... and that side lengths of those four
packings range from 24.581... to 24.907...

Several improved packings in this broad family will now be sent to
Packomania: N = 336, 410, 411, 413, 450, 451, 528, 529, 717, 771-773,
824 and 872. Since these packings will probably be shown there soon, I
have not prepared figures for all of them. Here is a figure showing
just the first four of those new packings:
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs336sq.gif>.

David W. Cantrell

unread,

Feb 18, 2011, 7:09:25 PM2/18/11

Improved packings of 84 and 172 unit circles in squares are presented.
There may well be a few other packings for N < 100 which can be improved
slightly. For N < 200, the only remaining packings which are obviously

suboptimal are those for N = 177 and 179.

-------------------------------------------------------------------------

Earlier in this thread (Feb. 28, 2009), a packing of 84 unit circles in a
square was presented.

Recently, Milos Tatarevic found a better packing, which can currently be

seen at <http://hydra.nat.uni-magdeburg.de/packing/csq/csq84.html>. It has
side length s = 17.9029661741366900108635124167 and 163 contacts, according
to Packomania.

But that packing can again be improved slightly, giving

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs84sq.gif>
with s = 17.902966174136690010863512020777... and 172 contacts.
[Note: When this packing is shown at Packomania, it is possible that the
circle nearest the lower left corner of the square will be shown as
touching the left side of the square (and that the number of contacts would
then be indicated as 173). But that unit circle should actually be about
7*10^-29 away from the left side of the square.]

-------------------------------------------------------------------------

N = 172
s = 25.417214968442920546398024424665...
360 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs172sq.gif>
[Note: Some of the nontouching circles are very close together. When this
packing is shown at Packomania, the number of contacts indicated there will
probably be 369, due to the fact that Packomania uses only 30 significant
digits.]

The best packing previously known, due to Huang & Ye, had
s = 25.417214968442982... and 348 contacts.

-------------------------------------------------------------------------

David W. Cantrell

unread,

Mar 7, 2011, 1:04:45 AM3/7/11

This is a small update about packings in the triangle-shift family.
Improved packings are given for N = 279, 280, 418, 504, 822, 837, 1003,
2511, 3317 and 6090, but despite these improvements, many of these packings
are still suboptimal. (Yet to be written is The Triangle-Shift Family,
Part 2, which will discuss the behavior of triangle-shift packings when N
is large. But the packing presented below for N = 3317 gives an intriguing
foretaste of that behavior.)

--------------------------------------------------------------------------

This update was prompted, in part, by some improvements to triangle-shift
packings recently found by Huang and Ye. When the triangle-shift family was
introduced in this thread, there was little evidence from computer
minimization to support optimality of such packings. But now, since the
improvements found by Huang and Ye are _still_ within the triangle-shift
family, that evidence is substantially strengthened.

To illustrate the type of improvement found by Huang and Ye, we begin by
considering the triangle-shift packing for N = 418. Here is what had been
said about it earlier in this thread:

> -------------------------------------------------------------------------
>
> N = 418
> p = 37, q = 21, p/q - sqrt(3) = 0.02985...
> s = 38.913303138863028028609... suboptimal
> (s = 38.913316... for the archetype)
> 1141 contacts
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ418sq.gif>
>
> The best packing previously known has side length
> s = 38.91369... and 1084 contacts.
>
> The new packing is better than the archetype but is still suboptimal.
> Note that circle #160 is a rattler. That implies that circle #184 is
> also loose, and that implies that circles #183 and 202 are loose,
> etc... Looseness, in this case, is a contagion which spreads
> throughout the whole packing. I choose not to show all of the circles
> as rattlers simply because doing so would have obscured the
> triangle-shift structure.

Huang and Ye's improvement can currently be seen at
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq418.html>, with side
length s = 38.9133031237142... and 1127 contacts.

But their packing can again be slightly improved to give
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/418subopt2.gif>
having s = 38.9133031237139465734960810255931... and 1134 contacts.
This packing is still suboptimal (for essentially the same reason as
mentioned in the quotation above). But although suboptimal, it is
probably very close to optimality. (Indeed, it seems likely that any
further improvement will reduce side length by less than 10^-30.)

The other nine improved packings are given below, with comments.

--------------------------------------------------------------------------

N = 279
p = 30, q = 17, p/q - sqrt(3) = 0.0326...
s = 31.930082787454370971233024652416...
733 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/279imp.gif>
This packing is probably still suboptimal, although I have attempted
to optimize it. [Some of the nontouching unit circles are extremely close
together and so, when this packing appears at Packomania, the number of
contacts will probably be indicated to be 742.]

The best packing previously known, due to Huang and Ye, has side length
s = 31.93008278767... and 695 contacts.

--------------------------------------------------------------------------

N = 280
This is a triangle-shift structure with another column appended at the
right.
s = 31.978915452715030308297335929550... suboptimal
741 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/280imp.gif>

The best packing previously known, which appeared earlier in this thread,
has s = 31.97891545287... and 752 contacts.

--------------------------------------------------------------------------

N = 504
p = 41, q = 23, p/q - sqrt(3) = 0.0505...
s = 42.748838509669405454188277050362...
1408 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/c504s.gif>

The best packing previously known has side length
s = 42.7531... and 329 contacts.

--------------------------------------------------------------------------

N = 822 primary density record

p = 52, q = 30, p/q - sqrt(3) = 0.00128...

s = 53.9995653581407481787552800908613919875015538152959... suboptimal
2287 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/822subopt2.gif>
[Some of the nontouching unit circles are extremely close together and so,
when this packing appears at Packomania, the number of contacts will
probably be indicated to be 2300.]

The best packing previously known, which appeared earlier in this thread,
has 2330 contacts and side length s which is larger by approx. 1.3*10^-39
than that of the improved packing.

--------------------------------------------------------------------------

N = 837
p = 53, q = 30, p/q - sqrt(3) = 0.0346...
s = 54.78982368494917315509377884436...
2382 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/c837s.gif>

The best packing previously known has side length
s = 54.7930... and 1024 contacts.

--------------------------------------------------------------------------

N = 1003
p = 58, q = 33, p/q - sqrt(3) = 0.0255...
s = 59.851547626694181797185894119880... archetypal
2872 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/c1003s.gif>

The best packing previously known has side length
s = 60 and 1062 contacts.

--------------------------------------------------------------------------

N = 2511
p = 92, q = 53, p/q - sqrt(3) = 0.0037...
s = 93.9888078614867532966403278779222... suboptimal
7293 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/c2511s.gif>

The best packing previously known has side length
s = 94 and 2604 contacts.

--------------------------------------------------------------------------

N = 3317
p = 106, q = 61, p/q - sqrt(3) = 0.0056...
s = 107.9694556521308590984726236768270...
9674 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/c3317s.gif>
This triangle-shift packing is remarkable because it contains another
triangle-shift packing in its upper left corner, shown in detail in
the figure above. The 68 circles there fit in a rectangle which is
almost square, having aspect ratio 0.9983... That packing of 68
circles in an almost- square rectangle resembles fairly closely the
triangle-shift packing of 68 circles in a square:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq68.html>.

The best packing previously known has side length
s = 108 and 3424 contacts.

--------------------------------------------------------------------------

N = 6090
p = 144, q = 83, p/q - sqrt(3) = 0.0028...
s = 145.9843669308394543802640231010759... suboptimal
17905 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/c6090s.gif>

The best packing previously known has side length
s = 146 and 6235 contacts.

--------------------------------------------------------------------------

David W. Cantrell

unread,

Mar 21, 2011, 3:57:56 PM3/21/11

Improved packings of unit circles in squares are presented for N = 85, 202,
204, 205, 209, 210, 212, 220 and 225.

-------------------------------------------------------------------------

Earlier in this thread (Feb. 28, 2009), a packing of 85 unit circles in a
square was presented.

Recently, Milos Tatarevic found a better packing, which can currently be
seen at <http://hydra.nat.uni-magdeburg.de/packing/csq/csq85.html>.
It has 169 contacts and side length
s = 17.95971148515840310734..., according to Packomania.

But that packing can again be improved slightly, giving

<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs85sq.gif>
with 189 contacts and
s = 17.959711485158403107253272568056...

-------------------------------------------------------------------------

N = 202
s = 27.4085549811762984992246779508000916080111...
511 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs202sq.gif>

The best packing previously known has 509 contacts and side length s which
is larger by approx. 1.7*10^-30.

-------------------------------------------------------------------------

N = 204
s = 27.523381977358406170129484914984...
439 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs204sq.gif>

The best packing previously known has side length

s = 27.52338197735896... and 377 contacts.

-------------------------------------------------------------------------

N = 205
s = 27.576876116690654447588089458094...
476 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs205sq.gif>

The best packing previously known has side length

s = 27.5768761166915... and 413 contacts.

-------------------------------------------------------------------------

N = 209
s = 27.816328560750361810247897419278145525...
541 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs209sq.gif>

The best packing previously known has 535 contacts and side length s which
is larger by approx. 5.4*10^-32.

-------------------------------------------------------------------------

N = 210
s = 27.865431130128050884944566600127717855971...
529 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs210sq.gif>

The best packing previously known has 524 contacts and side length s which
is larger by approx. 2.0*10^-32.

-------------------------------------------------------------------------

N = 212
s = 27.943373577841878551612582851256580218178...
505 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs212sq.gif>

The best packing previously known has 462 contacts. (The reduction in side
length was not estimated in this case.)

-------------------------------------------------------------------------

N = 220
s = 28.581964018205224958761604966787...
484 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs220sq.gif>

[Note: Some of the nontouching circles are very close together. When

this packing is shown at Packomania, the number of contacts indicated
there will probably be 496, due to the fact that Packomania uses only
30 significant digits.]

The best packing previously known has side length
s = 28.5819640182052283... and 471 contacts.

-------------------------------------------------------------------------

N = 225
s = 28.892529959285044108229344555057...
565 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs225sq.gif>

The best packing previously known has side length

s = 28.89252995941... and 555 contacts.

-------------------------------------------------------------------------

David W. Cantrell

unread,

Apr 16, 2011, 7:42:02 PM4/16/11

Readers of this thread might also be interested in a different type of
packing problem mentioned in the new thread

"Maximizing the sum of the radii of packed disks"

David W. Cantrell

unread,

May 26, 2011, 8:09:37 PM5/26/11

[OT: This thread has been inactive for more than a month. I live in
Tuscaloosa, Alabama, substantial portions of which were devastated by a
tornado on April 27. Had my home been merely 1/4 farther south, I might
well have been killed and certainly my house would have been completely
obliterated. Internet access was only recently restored here.]

An improved packing of 400 unit circles in a square is presented.

-------------------------------------------------------------------------

N = 400
s = 38.164522999672522147272176439163...
1083 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs400sq.gif>

The best packing previously known has side length

s = 38.164523006... and 502 contacts.

-------------------------------------------------------------------------

David W. Cantrell

1treePetrifiedForestLane

unread,

May 26, 2011, 10:34:27 PM5/26/11

hey, 20 times itself circles; now,
please, try 400 spheres.

sorry to hear about that;
I did know that Tuscaloosa is a university town,
having spent some weeks, there.

David W. Cantrell

unread,

Jun 23, 2011, 8:10:57 PM6/23/11

Improved packings of unit circles in squares are presented

for N = 215 (a density-record packing), 223, 226 and 229.

-------------------------------------------------------------------------

N = 215
s = 27.999470785993890465591455284085...
531 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs215sq.gif>

The best packing previously known has side length

s = 27.9994711... and 209 contacts.

-------------------------------------------------------------------------

N = 223
s = 28.746373096430056917437776821128...
495 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs223sq.gif>

The best packing previously known has side length

s = 28.7463730974... and 462 contacts.

-------------------------------------------------------------------------

N = 226
s = 28.980195789900461420042567209470...
569 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs226sq.gif>

The best packing previously known has side length

s = 28.980195789912... and 566 contacts.

-------------------------------------------------------------------------

N = 229
s = 29.166477858265649681546686387781...
541 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs229sq.gif>

The best packing previously known has side length

s = 29.166477858265696... and 482 contacts.

-------------------------------------------------------------------------

David W. Cantrell

unread,

Jul 28, 2011, 5:51:09 PM7/28/11

Improved packings of unit circles in squares are presented

for N = 234, 238, 239 and 240.

-------------------------------------------------------------------------

N = 234
s = 29.399297204453865867610264182507...
494 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs234sq.gif>

The best packing previously known has side length

s = 29.39929720454... and 463 contacts.

-------------------------------------------------------------------------

N = 238
s = 29.52843241998213924557087327887109748...
601 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs238sq.gif>

The best packing previously known has 591 contacts. Its side length
is estimated to exceed that of the new packing by at least 2*10^-29.

-------------------------------------------------------------------------

N = 239
s = 29.620823282410978524111297578853...
529 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs239sq.gif>

The best packing previously known has side length

s = 29.62082349... and 500 contacts

-------------------------------------------------------------------------

N = 240
s = 29.666279529693218440499798663382...
604 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs240sq.gif>

The best packing previously known has side length

s = 29.6662795303... and 598 contacts.

-------------------------------------------------------------------------

David W. Cantrell

unread,

Sep 19, 2011, 6:26:49 PM9/19/11

Improved packings of unit circles in squares are presented

for N = 243, 244 and 245.

-------------------------------------------------------------------------

N = 243
s = 29.860683998328134438163890343713...
503 contacts
(When this packing appears at Packomania, it will probably indicate, due to
its use of only 30 significant digits, that there are 518 contacts.)
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs243sq.gif>

The best packing previously known has side length

s = 29.860683998374... and 506 contacts.

-------------------------------------------------------------------------

N = 244
s = 29.914182806724914647936399895489...
529 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs244sq.gif>

The best packing previously known has side length

s = 29.914182829... and 502 contacts.

-------------------------------------------------------------------------

N = 245
s = 29.949334437473714880268267672299...
570 contacts
(When this packing appears at Packomania, it will probably indicate, due to
its use of only 30 significant digits, that there are 572 contacts.)
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs245sq.gif>

The best packing previously known has side length

s = 29.94933443758... and 557 contacts

-------------------------------------------------------------------------

David W. Cantrell

Phil Carmody

unread,

Sep 23, 2011, 6:36:10 AM9/23/11

David W. Cantrell <DWCan...@sigmaxi.net> writes:
> Improved packings of unit circles in squares are presented
> for N = 243, 244 and 245.

Yay - at least there are still some sensible posts on sci.math! Keep
the updates coming, David. And give packomania a kick to use higher
precision arithmetic! Though it's fun that the difference between
touching and non-touching is so tiny - we're beyond the bounds of the
real world, those discs would probably be making hydrogen-bonds by
now!

Phil
--
"Religion is what keeps the poor from murdering the rich."
-- Napoleon

David W. Cantrell

unread,

Sep 29, 2011, 12:03:16 PM9/29/11

Phil Carmody <thefatphi...@yahoo.co.uk> wrote:
> David W. Cantrell <DWCan...@sigmaxi.net> writes:
>> Improved packings of unit circles in squares are presented
>> for N = 243, 244 and 245.
>
> Yay - at least there are still some sensible posts on sci.math! Keep
> the updates coming, David.

Thanks, Phil!

> And give packomania a kick to use higher precision arithmetic!

That's a reasonable suggestion, of course. But be aware that no _fixed_
amount of precision can ever be enough for all cases. I'm not sure, but for
Packomania to use more than 30 significant digits might be "more trouble
than it's worth".

Thankfully, using Mathematica, I can get as much precision as is needed.

> Though it's fun that the difference between
> touching and non-touching is so tiny - we're beyond the bounds of the
> real world, those discs would probably be making hydrogen-bonds by now!

See below.

>> N = 243
>> s = 29.860683998328134438163890343713...
>> 503 contacts
>> (When this packing appears at Packomania, it will probably indicate, due
>> to its use of only 30 significant digits, that there are 518 contacts.)
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs243sq.gif>

The three new packings now appear at Packomania. Here's the one for
N = 243: <http://hydra.nat.uni-magdeburg.de/packing/csq/csq243.html>

I had said that Packomania would probably indicate 518 contacts, but as you
can see, it actually indicates 519. That discrepancy was caused by my
forgetting to account for the following: The unit circle in the lower left
corner does not quite touch the left side of the square, being separated
from it by about 2*10^-54.

David W. Cantrell

David W. Cantrell

unread,

Nov 26, 2011, 12:35:43 PM11/26/11

Improved packings of unit circles in squares are presented

for N = 256, 258, 262, 263, 265 and 273.

-----------------------------------------

N = 256
s = 30.7331940875556142697555299004...
674 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs256sq.gif>

According to Packomania, the best packing previously known had side length
s = 30.73319408762... and 638 contacts.

-----------------------------------------

N = 258
s = 30.8912389175546836026577425717...
667 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs258sq.gif>

According to Packomania, the best packing previously known had side length
s = 30.8912389182... and 629 contacts.

-----------------------------------------

N = 262
s = 31.0616908714291813918255909642...
666 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs262sq.gif>

According to Packomania, the best packing previously known had side length
s = 31.06169087175... and 626 contacts.

-----------------------------------------

N = 263
s = 31.1353879352222806285114336639...
698 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs263sq.gif>

According to Packomania, the best packing previously known had side length
s = 31.13538793537... and 697 contacts.

-----------------------------------------

N = 265
s = 31.2175128413530879687868260893...
669 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs265sq.gif>

According to Packomania, the best packing previously known had side length
s = 31.2175128413589... and 648 contacts.

-----------------------------------------

N = 273
s = 31.6052079963581833257240445153...
673 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs273sq.gif>

According to Packomania, the best packing previously known had side length
s = 31.6052082... and 641 contacts.

-----------------------------------------

David W. Cantrell

David W. Cantrell

unread,

Dec 31, 2011, 6:59:29 PM12/31/11

To end the year, improved packings of unit circles in squares are presented
for N = 177, 179, 206, 207, 228, 230, 235, 242, 246 and 248.

With these improvements, no packing remains for N < 200 which is obviously
suboptimal. But of course, it's likely that some packings for N < 200 are
still suboptimal, just not obviously so. Indeed, the first packing below
might well be slightly suboptimal.

-------------------------------------------------------------------------

N = 177
s = 25.733697786397309573869748973738...
377 contacts (When this packing appears at Packomania, it will probably indicate more contacts, due to its use of only 30 significant digits.)
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs177sq.gif>

According to Packomania, the best packing previously known has 339 contacts
and side length s which is larger by about 3.7 * 10^-11.

-------------------------------------------------------------------------

N = 179
s = 25.851437558223042204137832757717...
380 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs179sq.gif>

According to Packomania, the best packing previously known has 269 contacts
and side length s which is larger by about 5.5 * 10^-9.

-------------------------------------------------------------------------

N = 206
s = 27.649819060378778820466685044671...
488 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs206sq.gif>

According to Packomania, the best packing previously known has 305 contacts
and side length s which is larger by about 6 * 10^-14.

-------------------------------------------------------------------------

N = 207
s = 27.677311797674990573616261752676...
457 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs207sq.gif>

According to Packomania, the best packing previously known has 297 contacts
and side length s which is larger by about 1.1 * 10^-9.

-------------------------------------------------------------------------

N = 228
s = 29.113455126520291955359867020749...
530 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs228sq.gif>

According to Packomania, the best packing previously known has 473 contacts
and side length s which is larger by about 4.7 * 10^-11.

-------------------------------------------------------------------------

N = 230
s = 29.186674754817217646219236030883...
555 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs230sq.gif>

According to Packomania, the best packing previously known has 313 contacts
and side length s which is larger by about 2.8 * 10^-9.

-------------------------------------------------------------------------

N = 235
s = 29.412549407317378692593843908469...
613 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs235sq.gif>

According to Packomania, the best packing previously known has 202 contacts
and side length s which is larger by about 6.3 * 10^-7.

-------------------------------------------------------------------------

N = 242
s = 29.752947871977164019597418476490...
562 contacts (When this packing appears at Packomania, it will probably indicate more contacts, due to its use of only 30 significant digits.)
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs242sq.gif>

According to Packomania, the best packing previously known has 507 contacts
and side length s which is larger by about 2 * 10^-9.

-------------------------------------------------------------------------

N = 246
s = 29.968323000577103383309376856310...
598 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs246sq.gif>

According to Packomania, the best packing previously known has 428 contacts
and side length s which is larger by about 6.6 * 10^-11.

-------------------------------------------------------------------------

N = 248
s = 30.183466091822441228655527083055...
592 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs248sq.gif>

According to Packomania, the best packing previously known has 312 contacts
and side length s which is larger by about 1.3 * 10^-8.

-------------------------------------------------------------------------

Happy New Year!
David W. Cantrell

David W. Cantrell

unread,

Feb 29, 2012, 12:03:19 AM2/29/12

Improved packings of unit circles in squares are presented

for N = 284, 291 and 292.

-------------------------------------------------------------------------

N = 284
s = 32.371743195454226863588299158976...
737 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs284sq.gif>

According to Packomania, the best packing previously known has 603 contacts
and side length s which is larger by about 6.8 * 10^-10.

-------------------------------------------------------------------------

N = 291
s = 32.737055151153283056247533932832...
742 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs291sq.gif>

According to Packomania, the best packing previously known has 683 contacts
and side length s which is larger by about 2.7 * 10^-8.

-------------------------------------------------------------------------

N = 292
s = 32.784245263643809865576726519519...
743 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs292sq.gif>

According to Packomania, the best packing previously known has 671 contacts
and side length s which is larger by about 6.6 * 10^-14.

-------------------------------------------------------------------------

David W. Cantrell

David W. Cantrell

unread,

Mar 22, 2012, 5:18:08 PM3/22/12

Improved packings of unit circles in squares are presented

for N = 245 and 257.

-------------------------------------------------------------------------

N = 245
s = 29.942673375217241303393474415468...
632 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs245sq.gif>

According to Packomania, the best packing previously known has 570
contacts and side length s which is larger by about 0.0067 .

-------------------------------------------------------------------------

N = 257
s = 30.824174684582306607924902921925...
655 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs257sq.gif>

According to Packomania, the best packing previously known has 654 contacts
and side length s which is larger by about 1.7 * 10^-10.

-------------------------------------------------------------------------

David W. Cantrell

David W. Cantrell

unread,

May 8, 2012, 10:05:13 PM5/8/12

An improved packing of 294 unit circles in a square is presented.

-------------------------------------------------------------------------

N = 294
s = 32.827175126299827288819272125780...
740 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs294sq.gif>

According to Packomania, the best packing previously known has 635 contacts
and side length s = 32.827175126299832...

-------------------------------------------------------------------------

David W. Cantrell

jdawi...@gmail.com

unread,

Jun 10, 2013, 6:06:39 PM6/10/13

I wrote and maintain software that makes placemats for wine tastings. Well, mostly Vintage Port tastings — but who’s counting? Of course, the circles for each of the n glasses should be arranged on the non-margin part of the paper such that the circles are as large as possible.

The program is in PostScript, a language in which all reals are single-precision; and too few tastings have more than three dozen glasses (so far, none). So much of the precision in these threads exceeds my needs.

But Packomania’s ten glasses on 1×0.7, that which I might yet call a /SnubDiamond formation, is new to me and a material improvement. And the seven-glasses version of the same, a mite worse than the seven-circle packing on Packomania, would also be an improvement. Coding to be done. Thank you.

Oh, my program available via
http://www.jdawiseman.com/placemat.html
That page, with its example packings, might interest.

NB: the margins are parameters. So packings cannot be pre-computed. Each time they must be computed afresh, and in PostScript. Hence my enthusiasm for classes of regular(ish) packings.

jdawi...@gmail.com

unread,

Jun 11, 2013, 6:04:25 AM6/11/13

My simple algorithm seems to have some numbers better than Packomania’s best.

Packomania’s best for 1607 circles is 0.013150206363931233253234572956. But take my /Diamonds pattern (see link above), with 43 rows and 75 columns can hold up to 1613 glasses, with radius 0.0131578947368421052631578947368421.

Likewise 45 rows and 78 columns gives 0.012658227848101265822784810126582 for up to 1755 glasses; and 51 rows and 88 columns gives 0.011235955056179775280898876404494 for up to 2244 glasses.

In all three of these it is not the diagonal constraint that binds, so there will be few contacts and hence room for further improvement.

A simple Mathematica doodle is at
http://www.jdawiseman.com/2013/20130611_Diamonds_example.nb

Obviously the full algorithm, would start with a loop over NG, the number of glasses. Within that loop NR, the number of rows, from 2 to NG (well, from ¾√NG until previous NR ≥ previous NC). Then compute NC = number of columns, and from those the three constraints on the radius (horizontal, vertical, diagonal). Take least, and compare to existing records.

Generating locations is then easy: For row = 0 to NR-1; For col = 0 to NC-1; if row+col is even then Y = R + (H–2R)*row/(NR–1), X = R + (W–2R)*col/(NC–1).

I wasn’t expecting to be able to help with this problem, so my having misunderstood something would not be a great surprise.

jdawi...@gmail.com

unread,

Jun 11, 2013, 6:18:18 AM6/11/13

My software for making placemats for wine tastings is not the right tool for this — really, not the right tool — but it is to hand. So 1613 on a square looks like
http://www.jdawiseman.com/2013/20130611_Packomania_1613.pdf

jdawi...@gmail.com

unread,

Jun 23, 2013, 10:19:34 AM6/23/13

Seven glasses (or circles) on a 1×0.6 rectangle. Packomania has, in a file dated 20-Jul-2010, a best radius of 0.138110324642.

This can be improved to
0.13820219366270000806325124692934093954866603821510
which is a root of
19729 - 194480 r + 273600 r^2 + 640000 r^3 + 640000 r^4

Positions are:
0.138202193662700008063251246929340940 0.138202193662700008063251246929340940
0.138202193662700008063251246929340940 0.461797806337299991936748753070659060
0.362302294504192981382112452898020366 0.300000000000000000000000000000000000
0.586402395345685954700973658866699793 0.138202193662700008063251246929340940
0.586402395345685954700973658866699793 0.461797806337299991936748753070659060
0.861797806337299991936748753070659060 0.161797806337299991936748753070659060
0.861797806337299991936748753070659060 0.438202193662700008063251246929340940
these being easy linear combinations of 1, 6/10, the radius, and the root of 165249 - 1218240 # + 2500800 #^2 - 1728000 #^3 + 640000 #^4 that is approximately 0.2241.

Picture at http://www.jdawiseman.com/2013/20130623_Packomania_7_on_6by10.pdf

jdawi...@gmail.com

unread,

Jun 24, 2013, 6:03:59 AM6/24/13

Likewise for seven glasses (or circles) on a 1×0.8 rectangle. Packomania has, in a file dated 18-Aug-2010, a best radius of 0.155511998041 with 13 contacts and one rattler.

This can be improved to 15 contacts, no rattlers, and a radius of
0.15598396016804864359529861420005908204589982425409

which is a root of

1769 - 15960 r + 22400 r^2 + 40000 r^3 + 40000 r^4

Positions are:
0.155983960168048643595298614200059082 0.155983960168048643595298614200059082
0.155983960168048643595298614200059082 0.644016039831951356404701385799940918
0.350355140191119636846889595501186363 0.400000000000000000000000000000000000
0.544726320214190630098480576802313645 0.155983960168048643595298614200059082
0.544726320214190630098480576802313645 0.644016039831951356404701385799940918
0.844016039831951356404701385799940918 0.244016039831951356404701385799940918
0.844016039831951356404701385799940918 0.555983960168048643595298614200059082

Picture at http://www.jdawiseman.com/2013/20130624_Packomania_7_on_8by10.pdf

0 new messages