Prime Powers and Multiples of Six
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.
Related problems & prerequisites
Worth solving first
- Take Away a Perfect Square 5.0/10
- Wythoff's Losing Pairs up to Fifty 5.0/10
- Race to 100 3.0/10
Source: Folklore-style take-away game; no traceable original source. Statement written for AxiomIQ.