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
0, 1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 3, 2 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,5

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), 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.

LINKS

Table of n, a(n) for n=1..13.

CROSSREFS

Cf. A001221.

Sequence in context: A025877 A219182 A184171 * A029398 A025817 A109381

Adjacent sequences:  A133986 A133987 A133988 * A133990 A133991 A133992

KEYWORD

more,nonn

AUTHOR

Creighton Dement, Oct 01 2007

STATUS

approved

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 April 18 09:06 EDT 2021. Contains 343087 sequences. (Running on oeis4.)