You already covered 1-6, and the missing number is 7. Adding 7, you will cover 1-13. Therefore, 7 is optimal for N = 7~13. Note that here by optimal we mean that we need the minimum number of patches (which is 1).

4 is equally optimal for N = 7~10, but not for N = 11 to 13.

The proof is quite straightforward by induction or contradiction.

What we want to prove is

If the greedy algorithm needs to patch `k`

numbers to cover 1~N, it is impossible to patch less than `k`

numbers to do the same.

Proof by contradiction

For a given `N`

the `k`

patches found by greedy algorithm is M1 < M2 < ... < Mk <= N.

If there is another set of patches X1 <= X2<= ... <= Xk', with `k' < k`

, then we have

X1 <= M1 (otherwise M1 is not covered)

X2 <= M2 (otherwise M2 is not covered)

.

.

.

Xk' <= Mk' (otherwise Mk' is not covered)

We can see that since M1 M2... Mk' is not enough to cover Mk, therefore X1, X2,..., Xk' is also not enough to cover Mk <= N. This contradicts the fact that X covers 1~N.