June 2012
First we factor 1,506,009,006,001,500,000,000.
It is easy to factor out 10^8=2^8 * 5^8 and then 15=3*5.
Noticing the binomial coefficients in the result (1,004,006,004,001) we get 1001^4=7^4 * 11^4 * 13^4.
So the factorization of N is 2^8 * 3^1 * 5^9 * 7^4 * 11^4 * 13^4.
Then we note that the game is a actually the classic game of Nim in disguise.
The winning moves from the initial state of (8,1,9,4,4,4) are to remove one of the piles of 4.
Translating it back to our game - the winning moves are 7^4, 11^4 and 13^4.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com