I have an irrational number $0<a<1$ for which I need to calculate the sum $$\sum_{i=0}^N\lfloor ai\rfloor^2\mbox{ mod }m.$$ Here $m$ is an $8$-digit number and $N$ is a $15$-digit number. The number needs to be exact.

The context is a puzzle. I managed to show that the answer is exactly $$\sum_{i=0}^N\lfloor\phi i\rfloor(\lfloor\phi i\rfloor+4i+1)/2$$ plus something I already computed. Here $N$ is also a number I already computed to be $15$ digits, and $\phi=(\sqrt5-1)/2$. And I need to give the answer modulo $7^{10}$.

The biggest problem is the square. I did find a little theory online on how you might do this without the square. Formula and proof for the sum of floor and ceiling numbers Also, simply summing over $ai-\frac12$ already gives an approximation that differs by less than $2$ for all $N\leq10^6$. This trick will definitely not work with the square, though, since an off-by one of one of the values will already have a huge impact on the result.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.