4
$\begingroup$

Now the sum is approximated by $$\sum_{a=1}^{N} \left({\left\lfloor{\frac{N+1}{a}}\right\rfloor + \left\lfloor{\frac{N-1}{a}}\right\rfloor}\right) \approx 2 \sum_{a=1}^{N} \left\lfloor{\frac{N}{a}}\right\rfloor$$.

when $N$ is large. This part of my on going research in polynomial factoring with constraints over the coefficients. I am looking for a possible closed form solution or if I can combine these two sum terms into one term.

$\endgroup$
  • 2
    $\begingroup$ Math is case-sensitive. I'm assuming you mean $\sum_{a=1}^N,$ and not $\sum_{A=1}^N?$ $\endgroup$ – Adrian Keister Jul 1 '19 at 19:10
  • $\begingroup$ This looks like one of those summations that would solve integer factoring if it was computable in polytime. You are probably better off attempting to prove that fact than to actually attempting to close the sum. (That said, if you can find an equivalence, then at least you have integer factoring algorithms you can use.) $\endgroup$ – DanielV Jul 1 '19 at 19:22
  • 1
    $\begingroup$ Link to a relevant OEIS page: oeis.org/A006218. $\endgroup$ – Adrian Keister Jul 1 '19 at 19:23
2
$\begingroup$

A first useful point to consider is that $$ \eqalign{ & \left\lfloor {{{N + 1} \over a}} \right\rfloor + \left\lfloor {{{N - 1} \over a}} \right\rfloor = \cr & = {{N + 1} \over a} + {{N - 1} \over a} - \left\{ {{{N + 1} \over a}} \right\} - \left\{ {{{N - 1} \over a}} \right\} = \cr & = {{2N} \over a} - \left( {\left\{ {{{N + 1} \over a}} \right\} + \left\{ {{{N - 1} \over a}} \right\}} \right) \cr} $$

And a second one is that $$ \eqalign{ & \left\{ x \right\} + \left\{ y \right\} = \cr & = \left\{ {x + y} \right\} + \left\lfloor {\left\{ x \right\} + \left\{ y \right\}} \right\rfloor = \cr & = \left\{ {x + y} \right\} + \left[ {1 \le \left\{ x \right\} + \left\{ y \right\}} \right] \cr} $$ where $[P]$ denotes the Iverson bracket

From these, you can get a rough estimate, considering that the fractional part is less than one, and on avg. it can be take to equal $1/2$.
Then it depends on the approximation you need to reach.

A further point is that $$ \eqalign{ & \left\lfloor {x + y} \right\rfloor = \cr & = \left\lfloor x \right\rfloor + \left\lfloor y \right\rfloor + \left\lfloor {\left\{ x \right\} + \left\{ y \right\}} \right\rfloor = \cr & = \left\lfloor x \right\rfloor + \left\lfloor y \right\rfloor + \left[ {1 - \left\{ x \right\} \le \left\{ y \right\}} \right]\quad \Rightarrow \cr & \Rightarrow \;\quad \left\lfloor {{{N + 1} \over a}} \right\rfloor = \left\lfloor {{{N - 1} \over a}} \right\rfloor + \left\lfloor {{2 \over a}} \right\rfloor + \left[ {1 - \left\{ {{2 \over a}} \right\} \le \left\{ {{{N - 1} \over a}} \right\}} \right] \cr} $$ which for $a=1$ and for $a=2$ gives simple results, and for $3 \le a$ becomes $$ \eqalign{ & \left\lfloor {{{N + 1} \over a}} \right\rfloor \quad \left| {\;3 \le a} \right.\quad = \cr & = \left\lfloor {{{N - 1} \over a}} \right\rfloor + \left[ {{{a - 2} \over a} \le \left\{ {{{N - 1} \over a}} \right\}} \right] = \cr & = \left\lfloor {{{N - 1} \over a}} \right\rfloor + \left[ {a - 2 \le \left( {N - 1} \right)\bmod a} \right] = \cr & = \left\lfloor {{{N - 1} \over a}} \right\rfloor + \left[ {a - 2 = \left( {N - 1} \right)\bmod a} \right] + \left[ {a - 1 = \left( {N - 1} \right)\bmod a} \right] = \cr & = \left\lfloor {{{N - 1} \over a}} \right\rfloor + \left[ {0 = \left( {N + 1} \right)\bmod a} \right] + \left[ {0 = N\bmod a} \right] = \cr & = \left\lfloor {{{N - 1} \over a}} \right\rfloor + \left[ {a\backslash N} \right] + \left[ {a\backslash \left( {N + 1} \right)} \right] \cr} $$ so that the sum of the two terms differ for the number of divisors of $N$ and $N+1$.

$\endgroup$
  • 1
    $\begingroup$ From the Rocky Mt. Journal of Math, V 15, N0 2, Spring 1985 we have $$\sum_{n \le x} \left\{{x/n}\right\} = \left({1-\gamma}\right) x + O \left({x/\log \left({x}\right)}\right)$$ where $\gamma$ is EEuler's constant. $\endgroup$ – Lorenz H Menke Jul 2 '19 at 1:09
  • $\begingroup$ @LorenzHMenke: very interesting to know ! thanks for signalling $\endgroup$ – G Cab Jul 2 '19 at 9:06
  • $\begingroup$ @LorenzHMenke: can you please give more details of the article (title, author) so to ease to find it, thanks $\endgroup$ – G Cab Jul 2 '19 at 9:16
1
$\begingroup$

Those are basically partial sums of the divisor counting function. Note that $$ \sum_{a \leq n} \left \lfloor \frac n a \right \rfloor = \sum_{\substack{a \leq n \\ b \leq a/n }} 1 = \sum_{ab \leq n} 1 = \sum_{m \leq n} \tau(m)$$ Now $$\sum_{a \leq N} \left \lfloor \frac {N+1} a \right \rfloor = \sum_{a \leq N+1} \left \lfloor \frac {N+1} a \right \rfloor - 1 = \sum_{m \leq N+1} \tau(m) - 1$$ and $$\sum_{a \leq N} \left \lfloor \frac {N-1} a \right \rfloor = \sum_{a \leq N-1} \left \lfloor \frac {N-1} a \right \rfloor = \sum_{m \leq N-1} \tau(m)$$ so your sum equals $$\sum_{a=1}^{N} \left({\left\lfloor{\frac{N+1}{a}}\right\rfloor + \left\lfloor{\frac{N-1}{a}}\right\rfloor}\right) = 2 \sum_{m \leq N-1} \tau(m) + \tau(N) + \tau(N+1) - 1$$ Finding a closed form is thus equivalent to finding a closed form for partial sums of the divisor function, which is too much to hope for. The state of the art is (https://en.wikipedia.org/wiki/Divisor_problem) $$\sum_{m \leq N-1} \tau(m) = N \log N + (2\gamma - 1)N + O_\epsilon(N^{\theta +\epsilon})$$ with $\theta = 131/416$. To get an asymptotic for your expression, simply multiply this by $2$ (because the three other terms are $O_\epsilon(N^\epsilon)$).

$\endgroup$
  • $\begingroup$ The link to Divisor_divisor_problem on wikipedia is dead. $\endgroup$ – Don Hatch Aug 23 '19 at 7:30
  • $\begingroup$ thank you, fixed $\endgroup$ – punctured dusk Aug 23 '19 at 9:09

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.