Solution
Prime Powers and Multiples of Six
Show the problem again
A pile contains n stones. Two players alternate; on each turn a player removes m stones where m is 1 or a prime power p^k (p prime, k ≥ 1), with m at most the pile size. So the allowed amounts are 1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, ... The player who takes the last stone wins. For how many n with 1 ≤ n ≤ 1000 does the player to move lose with optimal play? Give an integer.
Worked solution
The answer is 166. The losing positions are exactly the multiples of 6. A multiple of 6 other than 0 is never 1 or a prime power, because it has at least two distinct prime factors (2 and 3); so no allowed move leaves a multiple of 6 in place, and every move from a multiple of 6 lands on a non-multiple (the difference between two multiples of 6 would have to be a multiple of 6). Conversely, from 6k + r with r in {1, 2, 3, 4, 5}, the amount r is allowed (1, 2, 3, 5 are 1 or primes and 4 = 2²), and it reaches the multiple 6k. Induction from the terminal position 0 proves the claim. There are ⌊1000/6⌋ = 166 multiples of 6 in 1..1000.
Source: Folklore-style take-away game; no traceable original source. Statement written for AxiomIQ.