What are the best results you can find for various n? Can you prove your results? Some particular questions:

• Can you show that eventually f(n)>1? Can you show that f(n) goes to ∞ ?
• If n is composite with smallest prime factor p, is f(n) = n/p and g(n) = g(p)? If not, what is the smallest n for which these fail to hold?
• Is g(p) (for p prime) increasing? Can you show g(p) (for p prime) goes to ∞ ?
• The smallest n for which h(n)=3 is n=7. What is the smallest n for which h(n)=2?
• The tiling below shows that h(112)=1. Can you show that h(n)=1 for infinitely many n? Does h(n)=1 for all large n?

He mentions this is similar to a problem which he discussed on the rec.puzzles newsgroup in March 1998. He proved that any square besides a 2×2, 3×3, 5×5, 7×7, and 13×13 can be cut into squares with sides 2, 3, and 5. Later on, this discussion turned to tiling squares with smaller squares of sides which were not factors of the larger square. They eventually agreed the largest square which could not be tiled in this way has side 60.

Another of his observations is that many of the best fewest square tilings of prime sided squares use exactly 5 odd-sided squares. He proves that 5 is the minimum possible: Each row and column must contain an odd number of odd-sided squares, and 1 isn't enough. Since the area of odd-sided squares is 1 mod 4 and the area of even squares is 0 mod 4, we need a number of odd-sided squares that is 1 mod 4. Since 1 is not sufficient, at least 5 are required.

Brendan Owen proved that f(n)>1 eventually. He also wrote a computer program to find the values of f(n) for n≤82. He found many tilings which beat the previous bounds.

Olexandr Ravsky found all the data in the table below.

John Hoffman wrote a computer program to find f(n) for n≤102. He also showed that f(n) can be larger than n/p, where p is the smallest prime factor of n. In fact, since f(11)=2, f(121)≥22. He conjectured that for composite n, f(n) = max_k {n/k f(k) : k | n, k<n }. This is true for all but two values of n≤120. It fails for f(49)=9>7f(7) (shown here) and f(119)=18>17 f(7) (shown here).

Hoffman also notes that f(p) is not increasing, since f(37) = 7 and f(41) = 6.

Here are the values of f(p) for prime p:

The sequence of values of f(n): 1, 1, 2, 1, 3, 1, 4, 3, 5, 2, 6, 2, 7, 5, 8, 2, 9, 3, 10, 7, 11, 4, 12, 5, 13, 9, 14, 5, 15, 5, 16, 11, 17, 7, 18, 7, 19, 13, 20, 6, 21, 7, 22, 15, 23, 7, 24, 9, 25, 17, 26, 8, 27, 11, 28, 19, 29, 9, 30, 10, 31, 21, 32, 13, 33, 10, 34, 23, 35, 11, 36, 11, 37, 25, 38, 14, 39, 13, 40, 27, 41, 12, 42, 17, 43, 29, 44, 14, 45, 14, 46, 31, 47, 19, 48, 14, 49, 33, 50, 16, 51, . . . is now sequence A036445 of the Encyclopedia of Integer Sequences.

Joseph DeVincentis found the best-known bounds for g(p) for p prime≤47.

Brendan Owen confirmed these with a computer program for n≤36.

John Hoffman found g(n) for n≤28.

Olexandr Ravsky found g(43)=16 in 100 minutes on his Pentium 466.

There is some evidence that if p is the smallest prime dividing n, then g(p)=g(n). There are no known counterexamples. Hoffman showed that g(2n) = 4, and g(6n+3) = 6. The proofs are based on the observation that 4 different squares must cover the corners of the larger square. This means the conjecture is true for p=2 and p=3. I managed to generalize his result to cover p=5 as well.

Here are the values of g(p) for prime p:

The sequence of values of g(n): 4, 6, 4, 8, 4, 9, 4, 6, 4, 11, 4, 11, 4, 6, 4, 12, 4, 13, 4, 6, 4, 13, 4, 8, 4, 6, 4, 14, 4, 15, 4, 6, 4, 8, 4, . . . is sequence A018835 of the Encyclopedia of Integer Sequences.

There is a closely related problem that has been well-researched. Define G(n) to be the smallest number of co-prime squares (squares whose sides have no common divisor except for 1) that can tile a square of side n. Then G(n)≥g(n) and G(p)=g(p) for prime p. In 1964, John H. Conway proved that G(n) ≥ log₂ n, and in 1965, G. B. Trustum showed that G(n) ≤ 6 log₂ n. Several solvers guessed that this was the correct order of magnitude. The sequence of values of G(n): 1, 4, 6, 7, 8, 9, 9, 10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, . . . is sequence A005670 of the Encyclopedia of Integer Sequences.

Most of the tilings of Joseph DeVincentis, are symmetrical, which led him to investigate g_i(n), the smallest number of squares needed to tile an n × n square with a i × i square missing from a corner. Below are his best known bounds on g_i(n).

Olexandr Ravsky corrected one error below and found g₁(20)=13.

Olexandr Ravsky defined G₁(n) to be the fewest number of squares needed to tile an n × n square if one if the squares is 1 × 1. His data is shown below. He conjectures that g(p)=G₁(p) for primes p.

Joseph DeVincentis showed that h(n)≤3 for 11≤n≤52, and for many more larger n.

Brendan Owen used these bounds in his computer program to find h(n) for n≤50. In particular, he found that the smallest n for which h(n)=2 is n=19.

Ed Pegg and John Hoffman mention that if h(n)=m, h(kn)≤m, so there are infinitely many n with h(n)=1.

Ed asks whether similar triangles can be packed with different sized congruent copies of themselves. The answer for equilateral triangles is no. To see this, consider a triangle in a corner. There must be a smaller triangle which shares a face. This new triangle must have a yet smaller triangle which shares a face, and so on. Since this progression cannot last forever, no such tiling can exist.

But such unique tilings of right triangles and isosceles triangles exist. The tiling of an isosceles right triangle is here. For a non-isosceles right triangle, an altitude to the hypotenuse divides the triangle into two similar triangles. The tiling of a non-right isosceles triangle is here.

Hoffman managed to show that h(n)≥2 for n≤40. He did n≤20 by hand!

Hoffman also asked for which values of n can n squares tile a square? The answer is all n except n=2, 3, and 5. For n≥2, 2n squares can tile a square of side n (1 square of side n–1 and 2n–1 squares of side 1). For n≥3, 2n+1 squares can tile a square of side 2n–2 (4 squares of side n–2 and n–3 squares of side 2).

Here are the values of h(n):

By modifying the tilings of Owen, I can show that h(n)≤2 for 22≤n≤102. The key observation is that if there is a h(n)=2 tiling with a k×k square in the corner, removing that square and adding 3 others gives a tiling which shows h(2n-k)≤2. In 1993, Skinner proved that the smallest n for which h(n)=1 are 110, 112, 120, 139, 140, . . . . The sequence of values of h(n): 4, 5, 4, 4, 4, 3, 4, 3, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, . . . is now sequence A036444 of the Encyclopedia of Integer Sequences.

The question of tiling rectangles with integer-sided squares is also interesting. For most small rectangles, f(m,n)=gcd(m,n), the greatest common divisor of m and n. The smallest counterexample is f(5,6)=2. For most small rectangles, g(m,n) can be found by the greedy strategy of always using the biggest square possible at every stage. Again, the smallest counterexample is g(5,6)=5.

In October 2007, Stewart Hinsley sent me the following page of his predictions for values of g(m,n). The values with a red background are the values where the greedy algorithm would correctly predict g(m,n). These guesses assume g(km,kn) = g(m,n), for which there is experimental evidence, and some other things, for which there is less evidence.

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 10/16/07.