0
$\begingroup$

Given a set of natural numbers {$N_1, ...N_n$} and another natural number $N$, find a closed form solution for the below sum

$M = \sum_{i=1}^n N_i \% N$
    where $N_i, N, n \in \mathbb N$
    and $N_i \% N$ is the remainder when $N_i$ is divided by $N$

Although trivial, I was able to reduce it to the below form

$M = KN + (\sum_{i=1}^n N_i)\%N$
   where $K$ is the quotient when $M$ is divided by N

but I am unable to reduce $K$ further into any closed form.

I don't have any formal proof that a closed form can exist, but belief that one could exist has driven be into looking for a solution. I have been looking up several research papers and questions posted here, but could not get any pointers. Any help is greatly appreciated.

Improve this question
$\endgroup$
11
  • $\begingroup$ What makes you think there is a closed form? $\endgroup$
    – Gerry Myerson
    Commented May 26, 2022 at 12:30
  • $\begingroup$ Also: $\{N_0,\dots,N_n\}$ is $n+1$ numbers, not $n$ numbers. $\endgroup$
    – Gerry Myerson
    Commented May 26, 2022 at 12:31
  • $\begingroup$ @GerryMyerson Oops that right, it should start from $N_1$ not $N_0$. $\endgroup$
    – userviswa
    Commented May 26, 2022 at 12:44
  • $\begingroup$ @NawafBou-Rabee K is the quotient when M is divided by N $\endgroup$
    – userviswa
    Commented May 26, 2022 at 12:46
  • $\begingroup$ @StevenClark I have modified the question to reduce confusions, wrt random. Please let me know if this clarifies your doubts. Distinct implied $N_i \neq N_j$, which is optional, just in case it helped to arrive at a solution quicker. $N$ can be any other number either inside or outside the set of {$N_i$} and $M$ is just the representation of the actual sum. $\endgroup$
    – userviswa
    Commented May 27, 2022 at 2:45

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .