This is a classical problem from memory management, known as the
Belady's anomaly.
The book numbers correspond to virtual memory pages, the bookcase
is the physical memory, and fetching a book from the storage
is called a *page fault*.

The best way how to find the sequences is simply by experimenting, maybe with a help of a small program that simulates the librarian's bookcase and always removes the right book – it's easy to make a mistake when simulating the process by hand.

The Wikipedia link gives an example for N=3:

1 2 3 4 1 2 5 1 2 3 4 5

Through understanding this example, a bit more precise googling or just wild guessing from the looks of it, we can derive a more general pattern for the anomaly:

** S _{1} := 1, 2, ..., N+1, 1, 2, N+2, 1, 2, ..., N+1, N+2**

This sequence creates one more page fault when the number of pages increases from **N** to **N+1**.
Thus for the easy task, all we need is to write an instance of it for some **N>3**, for example:

4 14 1 2 3 4 5 1 2 6 1 2 3 4 5 6

For the hard task, we first need to understand how the extra page fault is generated,
and then we can construct a sequence for the increase from **N** pages to **N+2**.
After that, a sequence for **N+3** will be easy. By combining all three sequences
(for **N+1, N+2** and **N+3**) we can get the final solution.

Consider the example sequence **1 2 3 4 1 2 5 1 2 3 4**. Let us write down the steps along with the
contents of the FIFO-like memory (the bookshelf):

Request | N+1 | N+2 | ||

1 | 1 | PF | 1 | PF |

2 | 1 2 | PF | 1 2 | PF |

3 | 1 2 3 | PF | 1 2 3 | PF |

4 | 2 3 4 | PF | 1 2 3 4 | PF |

1 | 3 4 1 | PF | 1 2 3 4 | |

2 | 4 1 2 | PF | 1 2 3 4 | |

5 | 1 2 5 | PF | 2 3 4 5 | PF |

1 | 1 2 5 | 3 4 5 1 | PF | |

2 | 1 2 5 | 4 5 1 2 | PF | |

3 | 2 5 3 | PF | 5 1 2 3 | PF |

4 | 5 3 4 | PF | 1 2 3 4 | PF |

5 | 5 3 4 | 2 3 4 5 | PF |

The reason for the extra page fault is that after the "execution" of the middle part ** 1 2 5**, the pages 1 and 2
are left at the end of the fifo and immediately pushed out byt the page **5**. In the final part, they are thus re-added
at the begginning of the FIFO and thus they push the page **5** out thus causing page fault at the end.

So what with the **N+2** case? First we enlarge the first part, because we now need to fill **N+2** pages in the
larger FIFO and also we need 3 pages from the beginning in the middle part. Because of this the sequence will only work for
**N≥4**. Thus we get the sequence:

** S _{2} := 1, 2, ..., N+2, 1, 2, 3, N+3, 1, 2, ..., N+2, N+3**

Analogicaly, for **N+3**, we get (for **N≥5**):

** S _{3} := 1, 2, ..., N+3, 1, 2, 3, 4, N+4, 1, 2, ..., N+3, N+4**

To put them together, we would choose **N=5**. For this size we have **T(N,S _{1})=13, T(N+1,S_{1})=14** and

To fit into the maximum length, we need to make up a better sequences such that they have either more page faults, or that they
work simultaneously for two or all three cases. One of such sequences is (for **N=8**):

** S _{23} := 1 2 3 4 5 6 7 8 9 10 1 2 3 4 20 21 1 2 3 4 5 6 7 8 9 10 20 21 **

**T(N,S _{23})=T(N+1,S_{2})=22, T(N+2,S_{2})=T(N+3,S_{2})=24**.
Thus we can use

A sample output for the hard task can thus look like this (pages **31,..,33** are used as padding):

8 169 1 2 3 4 5 6 7 8 9 1 2 20 1 2 3 4 5 6 7 8 9 20 31 32 33 1 2 3 4 5 6 7 8 9 10 1 2 3 4 20 21 1 2 3 4 5 6 7 8 9 10 20 21 31 1 2 3 4 5 6 7 8 9 10 1 2 3 4 20 21 1 2 3 4 5 6 7 8 9 10 20 21 31 1 2 3 4 5 6 7 8 9 10 1 2 3 4 20 21 1 2 3 4 5 6 7 8 9 10 20 21 31 1 2 3 4 5 6 7 8 9 10 1 2 3 4 20 21 1 2 3 4 5 6 7 8 9 10 20 21 31 1 2 3 4 5 6 7 8 9 10 1 2 3 4 20 21 1 2 3 4 5 6 7 8 9 10 20 21