|
COMMENT
|
Assume either n or m > 1. An nXm 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 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), non-adjacent 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.
|
