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:
S1 := 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:
S2 := 1, 2, ..., N+2, 1, 2, 3, N+3, 1, 2, ..., N+2, N+3
Analogicaly, for N+3, we get (for N≥5):
S3 := 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,S1)=13, T(N+1,S1)=14 and T(N+2,S1)=T(N+3,S1)=7. Thus including S1 in the final sequence would generate a defficiency of 6 page faults in the case of N+2 and N+3. To counter this we would need to repeat S2 at least 7 times. Because T(N,S2)=T(N+1,S2)=15, T(N+3,S2)=8, this would againg create an another defficiency of 7*7 page faults in the case of N+3. Thus S3 would have to be repeated 7+7*7 times. This is however far above the limit of 300.
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):
S23 := 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,S23)=T(N+1,S2)=22, T(N+2,S2)=T(N+3,S2)=24. Thus we can use S1 and then 5 times S23. As a final note, we need a sort of "padding" between the sequences, to "flush out" the content of the FIFO so the next sequence does not have anything "cached" and generates all of the page faults.
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