%I
%S 0,1,1,1,2,1,2,1,2,2,2,3,2
%N Define fu(1,1) = 0. Then a(n) = fu(1,n) = smallest number t such that an n X 1 strip of n squares can be cut into n squares using p_1, p_2, ..., p_t cuts where p_t is a prime number or p_t = 1.
%C 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.
%C 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".
%C 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.
%C Note also that the cuts given below are only examples other (adjacent) cuts are possible which lead to the same result for fu.
%C 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).
%C 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).
%C 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)
%C 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).
%C Could be interesting to compare this sequence with A001221(n) = omega(n), the number of distinct primes dividing.
%Y Cf. A001221.
%K more,nonn
%O 1,5
%A _Creighton Dement_, Oct 01 2007
