Puzzles

Yes: 8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16.

It is clearly possible for the numbers 1 to 15 (remove the 16 from the end of the sequence above) and 1 to 17 (add 17 to the start of the sequence above).

The OEIS sequence A090461 gives other numbers for which this is possible. It starts 15, 16, 17, 23, then includes every number from 25 onwards. It is conjectured, but not proven, that it is possible for every number above 25.