Stefan Hougardy

Research Institute for Discrete Mathematics, University of Bonn

January 2010, update: April 2014

Research Institute for Discrete Mathematics, University of Bonn

January 2010, update: April 2014

In 1966 Leo Moser (1966) posed the following problem: What is the smallest number A such that every set of squares of total area 1 can be accommodated in some rectangle of area A?

Moon and Moser (1967) proved A≤2. This was improved by Kleitman and Krieger (1970) to 1.733 and in a further paper (1975) to 1.633. The best value known so far is due to Novotný (1996) who proved A<1.53. In our paper On Packing Squares into a Rectangle we improve this to A<1.4. Below we present proofs for different values of A downto 1.4 and a simple program that allows to verify the proofs.

Update (April 2014): Using essentially the same approach but faster rectangle packing algorithms we have improved meanwhile the value of A to less than 1.37.

value for A |
proven value* |
filename |
file size |
#cases |
discretization |
runtime** |
MD5 hash |

1.50 |
1.5 |
Proof_1.50_6 |
3,049,854 Bytes |
31,934 |
64 |
89s |
2f29985e64458c65a9d2c08deb2c0c17 |

1.49 |
6102/4096 < 1.48975 |
Proof_1.49_6 |
3,990,103 Bytes |
40,947 |
64 |
220s |
d4570ec1b14416ad19e6b2145455ca3c |

1.48 |
6060/4096 < 1.47950 |
Proof_1.48_6 |
5,423,131 Bytes |
54,425 |
64 |
481s |
250cccbd6fce2f57eba8a3ec7fe31e18 |

1.47 |
6020/4096 < 1.46973 |
Proof_1.47_6 |
7,274,098 Bytes |
71,381 |
64 |
2,262s |
31a406031914fccca554c842856ec8b6 |

1.46 |
5980/4096 < 1.45997 |
Proof_1.46_6 |
10,067,060 Bytes |
96,136 |
64 |
21,923s |
e3c28c3430c1a258ce0ec4c1856bbcf0 |

1.45 |
5936/4096 < 1.44922 |
Proof_1.45_6 | 13,781,783 Bytes |
127,807 |
64 |
181,412s |
ed93800618b91206b7e1450f8e5f4ec8 |

1.44 |
5896/4096 < 1.43946 |
Proof_1.44_6 |
19,284,428 Bytes |
173,536 |
64 |
1,074,894s |
1157cc60480e56321d12a1dedd292413 |

1.43 |
23427/16384 < 1.42988 |
Proof_1.43_7 |
190,815,860 Bytes |
1,700,408 |
128 |
70,167s |
5714e429ec9c3229f151328ea4690950 |

1.42 |
23265/16384 < 1.41999 |
Proof_1.42_7 |
280,570,966 Bytes |
2,437,097 |
128 |
327,091s |
95863a500cd4fe0a0386173c13d79f09 |

1.41 |
23100/16384 < 1.40992 |
Proof_1.41_7 |
421,289,825 Bytes |
3,558,634 |
128 |
1,105,542s |
8c556807a2730f3f7069c6cbe36e7098 |

1.40 |
22936/16384 < 1.39991 |
Proof_1.40_7 | 654,480,156 Bytes |
5,365,339 |
128 |
5,562,752s |
3889005c92133fb4f4bd451d03294057 |

1.37 (update 2014) |
5611/4096 < 1.36988 |
NewProof_1.37_6 |
3,213,447,608 Bytes |
14,078,192 |
64 |
535,764s |

*The proven value for A is in most cases slightly smaller. Here we provide the precise value.

**Runtime in seconds on a 3GHz Intel Xeon using 1 core

To download a proof simply click on its name.

CheckProof.cpp is a simple C++ program to verify the correctness of the proofs. It can be compiled using the gcc compiler and should compile with most other C++-compilers too.

Stefan Hougardy's homepage