I have just started to learn Sprague-Grundy Number. Now trying to solve lightoj 1296 — Again Stone Game this problem.

Alice and Bob are playing a stone game. Initially there are n piles of stones and each pile contains some stone range[1,10^9]. Alice start the game and they alternate moves. In each move, a player has to select any pile and should remove at least one and no more than half stones from that pile. Who will win the game.

I think it's not possible to solve by Dynamic Programming. Need to find out a pattern. I just calculate some values Sprague-Grundy Number and find a pattern for even number that each even number Sprague-Grundy Number is its own half. (I using term SGN as Sprague-Grundy Number). Like it – SGN(2) = 1, SGN(4) = 2, SGN(6) = 3, SGN(8) = 4.........

For some odd numbers it SGN(1)=0, SGN(3)=0, SGN(5)=1, SGN(7)=0,SGN(9)=2......... But I could not find out any pattern for odd numbers. I can not understand that my observations is right or wrong. Looking help for odd values pattern or a new hints to solve this problem.

Thanks in advance………………………….