Proof: from any number that is not a multiple of 4, taking 1, 2 or 3 can make it into a multiple of 4. However, because all multiples of 4 are composites, a player starting at a multiple of 4 can only take values that will not retain this property.
Proof: if 2K<N<2K+1, then we take away N-2K< to make the result a power of 2. If N=2K, the result after subtraction cannot be a power of 2.
Strategy: take away x=gcd(N,2N). Doing so ensures that
Strategy for first player: Let F(k)<N<F(k+1) and x=N-F(k). If x<F(k)/2, take x. (This puts the other player on F(k) with no ability to take all the elements, and hence wins the game by induction on N.) Otherwise, play as you would for an initial pile of size x. (Because x≥F(k)/2, we have F(k-2)<x<F(k-1), so by induction the strategy for x will reduce the pile to a size of F(k). Furthermore, we know that the last amount to be taken by the player in the last round before reducing to F(k) must have been less than F(k)/2. If it was otherwise, this would indicate that in the previous move the second player took more than F(k)/4, for a total of 1.75 F(k)>F(k+1), contradicting N<F(k+1). Thus, after reaching F(k), the first player cannot immediately clear the pile, and is therefore in a losing position.)
Strategy for second player: Let N=F(k). If the first player took 1/3 or more of the pile, simply empty it and win. Otherwise, the first player must have taken less than F(k-2). Employ the second player strategy for F(k-2), followed by the second player strategy for F(k-1). By induction, this leads to winning. Note that on the first move after reaching F(k-1) the first player cannot take the entire pile, because, once again, this would imply N≥1.75 F(k)>F(k+1).