Loading [MathJax]/extensions/TeX/mathchoice.js

Problem #43

Game of Stacks

Drake and Josh play a game to take a break from programming. In this game, there is a stack of N sheets. Drake starts first and alternating turns, they remove an odd number of sheets in each turn and put them in a basket which is initially empty. After every turn they note down the count of the sheets in the basket and thus construct an increasing sequence of numbers. But then, Drake wonders, how many distinct games of this kind can they play such that the stack gets empty at last and there are exactly k numbers in the sequence i.e. the game ends after k turns. Josh answers this when N and k were small. But now Drake who is also good in Mathematics asks you the same question with slight complications:

N = 999999 and k = 5^p can be any number where \frac{(2^{p-1} - 1)}{p} is a perfect square, i.e. you have to take the sum for all such k!

Give your answer \mod10^9+7.

Note that distinct games generate distinct sequences.

Contributed by Varun Syal

Solved by 14 users

Log in to submit answers.

Is something wrong?

Maintaining a collection of high quality questions is our top priority. If, however, you do find an error, report the problem and we'll make sure it is reviewed soon.