
COMMENTS

Assume either n or m > 1. An n X m grid can always be cut into n*m squares by first making p_1 cuts, then p_2 cuts, ..., then p_t cuts where p_1, p_2, ...p_t are prime numbers or 1. 0. For the general case, cuts can be made along any line segment which starts on the edge (itself the corner of 2 boxes) and terminates at the corners of 2, 3, or 4 boxes.
Define Fu(n,m) as the set off all such t. Define fu(n,m) as the smallest number in the set Fu(n,m). Lastly, define fu(1,1) = It follows that Fu(n,m) = Fu(m,n) and fu(n,m) = fu(m,n) Let (1, 2, ..., n) mean "to make n adjacent cuts" Let (1, 2, ..., n) <> (1, 2, ..., m) means "to make n adjacent cuts, then m adjacent cuts".
Note: Adjacent cuts are assumed here only to simplify the notation for the examples, below. For more complicated examples (i.e., where n, m are larger numbers), nonadjacent cuts may need to be taken into account.
Note also that the cuts given below are only examples other (adjacent) cuts are possible which lead to the same result for fu.
Note: 1 and p are always elements of Fu(p+1,1) since we can cut in the following two ways: (1, 2, ..., p) <> (0) and (1) <> (1) <> ... <> (1) (p times).
For p prime, it follows immediately that fu(p, 1) > 1 and: fu(p+1, 1) = 1; (1, 2, ..., p) <> (0) fu(p+2, 1) = 2; (1, 2, ..., p) <> (1) fu(p+3, 1) = 2; (1, 2, ..., p) <> (1, 2) (2 is prime) fu(p+4, 1) <= 2 since the number 2 is always an element of Fu(p+4, 1): (1, 2, ..., p) <> (1, 2, 3) (3 is prime).
Note: fu(p+4) = 1 for the case that p and p+3 are twin primes. fu(2p+2, 1) = 2; (1, 2, ..., p) <> (1, 2, ..., p)
For any number n we have: fu(n+1, 1) <= fu(n, 1) + 1 Table: fu(2, 1) = 1; (1) <> (0) fu(3, 1) = 1; (1, 2) <> (0) fu(4, 1) = 1; (1, 2, 3) <> (0) fu(5, 1) = 2; (1, 2, 3) <> (1) fu(6, 1) = 1; (1, 2, 3, 4, 5) <> (0) fu(7, 1) = 2; (1, 2, 3, 4, 5) <> (1) or (1, 2, 3) <> (1, 2, 3) fu(8, 1) = 1; (1, 2, 3, 4, 5, 6, 7) <> (0) fu(9, 1) = 2; (1, 2, 3, 4, 5, 6, 7) <> (1) fu(10, 1) = 2; (1, 2, 3, 4, 5, 6, 7) <> (1, 2) fu(11, 1) = 2; (1, 2, 3, 4, 5, 6, 7) <> (1, 2, 3) fu(12, 1) = 3; (1, 2, 3, 4, 5, 6, 7) <> (1, 2, 3) <> (1) fu(13, 1) = 2; (1, 2, 3, 4, 5, 6, 7) <> (1, 2, 3, 4, 5).
Could be interesting to compare this sequence with A001221(n) = omega(n), the number of distinct primes dividing.
