login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A133989 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. 0

%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), non-adjacent 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 13 00:57 EDT 2021. Contains 344980 sequences. (Running on oeis4.)