0
$\begingroup$

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.

$\endgroup$

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.