Filling a square (n,n) with
rectangles with unequal prime sides, all rectangles may have the same
The minimum number of
rectangles. Call this Minimum(n).
(I) n=3, no solution. So the minimum is 0.
(II) n and n-2 prime
There is a split in (n,n-2) and
(n,2). So the minimum is 2.
This covers n=5,7,13,19,etc.
(IV) n prime and n-2k prime,
k>1. (And k<>0 mod 3 because 0 mod 3 is not possible)
Every primegap 2k can be written
as a sum of two primes p,q <n (Assuming Goldbach). The minimum is 3,
since we have the split (n,p) (n,q) (n,n-(p+q)).
(V) n not prime and n-2k, n-2l
prime (k<>l). (We have at least n>=9).
Split into (n,n-2k) which can
be split into (n-2l,n-2k)and (2l,n-2k) which splits into 2 or 3 tiles
(n,2k) which splits into (n-2l,2k) and (2l,2k), the first of which into
2 the latter in 4. A minimum of 8 or 9 tiles, which is probably just an
n=9 = 2+7 a tricky one. Use 2x7
4 times at the border of the main square and in the middle we have a
tile of size: 5x5 which we can split in 2, so 6 tiles! 81=4.14+25.
(VI) n not prime and n-2 prime
and n can be written as a sum of 3 odd primes:
Split into (n-2,n) and (2,n)
split each of these 3 into 3 tiles, total 6 tiles.
(V) n not prime and n-2 not
prime with n two splits of 3 odd primes, such that the intersection of
the two sets of 3 primes is empty.
The splits are obvious, a total
of 9 tiles. Which is probably an upperbound for the minimum.
No solutions for n=2, 4.
If n can be written as the sum
of two different primes in at least two ways (hence n is even), we have
n=p1+p2 =q1+q2, so (n,n) can be divided in (p1,q1),(p1,q2),(p2,q1) and
(p2,q2). So an upperbound for the minimum is 4. It canít be less than 4
because both sides with length n have to be dissected. So the minimum is
4. As I understand Paul has proven (an extension of) Goldbach for n>12.
(Sorry Paul, you probably mentioned this as well).
Minimum(6): The only splits
are 6=3+3 and 6=2+2+2, so the minimum equals 6.
Minimum(10): Since n=3+7=5+5 we can use (B), the minimum equals 4.
Minimum(12): I would say: split into (5,5) and (7,7) and two
The two squares can be further split into
two tiles (II): 6 tiles in total.
As an alternative: 12=5+7=3+3+3, so 3
tiles (3,5) and 3 tiles (3,7).
The maximum number of
rectangles. Call this Maximum(n).
All tiles (p,q), p<>q, and both
Write n=a.pq+r, with r=n mod pq.
Now n^2= r^2 mod pq. And r^2=0 mod pq if and only if r=0 mod pq. So the
square (n,n) can only be divided into (p,q)-tiles if n is a multiple of
6.k^2 tiles, size (2,3)
Maximum(pqk): Maximum(pqk)>=Maximum(pq).k^2 >= pq.k^2 size
A better general procedure to
find an lowerbound would entail finding solutions for Maximum(6k+l) with
l in [1..5].
If l=1: 6k+1=6(k-1)+7. Leading to:
2.(k-1) rectangles of size (7,6)=(3+4,6) split (3,6) in 3 (2,3) tiles,
(4,6) in 4 tiles: 7 tiles: 14.(k-1). <---!!!!
1 rectangle of size (7,7)=(2,7)+(5,2.2+3) into 4 tiles
(2,7)(2,7)(3,2)(3,5) or (2,7)(2,5)(2,5)(3,5)
So a total of 6.(k-1)^2+14.(k-1)+4=6k^2+2k-4
If 6k+1=pq(k-1), for instance
55=6.9+1=5.11.1, this estimate gives: 6.81-16.9+2=452 and the other rule
6k+2,6k+3,6k+4 are even better,
because 2 and 3 are divisors of 6.
If l=5: 6k+5=6(k-1)+11. Leading
6(k-1)^2 (2,3) tiles
2(k-1) rectangles of size (11,6)=(2+3.3,6)=2 (2,3)+9(2,3), 11 tiles:
1 rectangle of size (11,11)=(6+5,2+3.3)=2 (2,3)+(2,5)+3(3,5)+ 9 (2,3):
So a total of 6(k-1)^2+22(k-1)+15=6k^2+10k-1
A good way to compare these kind
of rules would be to define the average tile size = # area /#tiles, the
smaller the better (or the reciprocal, the density the larger the
Maximum(6k): 6 [Absolute minimum]
Maximum(6k+1): (6k+1)^2/(6.k^2-4k+2) which tends to 6 for k
Maximum(6k+5): (6k+5)^2/(6k^2+10k-1) which is an even better
lower bound! [We miss 26 tiles]