0
$\begingroup$

Given integer n and float z find sum s of modulo z of first n natural numbers i.e 1%z + 2%z + ... + n%z. Note that z is irrational number!

$$ s=\sum_{i=1}^n {(i\mod z)} \\ z \ is \ irrational $$

For my concrete case z is $$ {\sqrt 2+1}$$

I found similar problem: https://www.geeksforgeeks.org/find-sum-modulo-k-first-n-natural-number

For my case n could be bigger than 10^100, so naive linear time solution would not work.

$\endgroup$
5
  • 1
    $\begingroup$ $i\bmod z$ just means $i-\lfloor i/z\rfloor\,z$, correct? With $n$ possibly bigger than $10^{100}$, that just looks like some programming challenge, not a practical or research problem. Ok, not much of a challenge for your particular $z$, so... $O(\log^3 N)$ should be easy. $\endgroup$
    – user436658
    Dec 21, 2020 at 19:11
  • $\begingroup$ @ProfessorVector, exactly! And how can it be calculated with only 𝑂(log3𝑁)? $\endgroup$
    – Oleksandr Knyga
    Dec 21, 2020 at 19:15
  • $\begingroup$ If it's some contest, I'd rather win it myself. ;-) $\endgroup$
    – user436658
    Dec 21, 2020 at 19:17
  • $\begingroup$ I assure you that it is not a contest and it is not possible to win for anybody :) $\endgroup$
    – Oleksandr Knyga
    Dec 21, 2020 at 19:22
  • $\begingroup$ Why do you need an answer, then? Sums with $10^{100}$ terms are... strange. $\endgroup$
    – user436658
    Dec 21, 2020 at 19:32

2 Answers 2

Reset to default
2
$\begingroup$

Sums are almost linear. I found linear regression $$s\approx 1.20708 n+0.0506173$$ For $n=10^5$ exact sum is $120712$ while the approximation gives $120708$

For $n=2\cdot 10^5$ exact sum is $241420.917186$ and approximation is $241416.6$

$\endgroup$
3
  • $\begingroup$ Unfortunately, we can compare against the correct result only for small $n$. In general, there is no error estimate, as far as I know. $\endgroup$
    – user436658
    Dec 22, 2020 at 19:26
  • $\begingroup$ @ProfessorVector You are right. Doyou sincerely believe it can make sense looking for a sum like that "with $n$ largest than $10^{100}$"? $\endgroup$
    – Raffaele
    Dec 22, 2020 at 19:30
  • $\begingroup$ Yes, of course. It's relatively easy (if you can handle numbers of that magnitude) to compute the exact result for $n=10^{100}$, say. $\endgroup$
    – user436658
    Dec 22, 2020 at 19:36
0
$\begingroup$

I ended up reducing the problem to the $$ s=\sum_{i=1}^n {(i\mod z)} = \sum_{i=1}^n(i * z) - \sum_{i=1}^n\lfloor i*z \rfloor \\ z \ is \ irrational $$

Solving first term is trivial and the second one could be solved using the Beatty sequence: How to find $\sum_{i=1}^n\left\lfloor i\sqrt{2}\right\rfloor$ A001951 A Beatty sequence: a(n) = floor(n*sqrt(2)).

$\endgroup$
1
  • $\begingroup$ This equation contradicts the interpretation of $i\bmod z$ you confirmed above, but both are closely related, naturally. Mercio's answer is using the same idea I'd use myself, but it's a bit confusing, since $\alpha$ and $\beta$ are used in various different meanings. Moreover, it's not clear what to do if you have $\sqrt{3}$ instead of $\sqrt{2}$. $\endgroup$
    – user436658
    Dec 22, 2020 at 10:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .