0
$\begingroup$

I have been trying to find this summation faster, Is there any sequence that can be observed?

$$Z(N)=\sum_{i=1}^N i^2\left\lfloor \frac{N}{i^2} \right\rfloor$$

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

This sequence is OEIS' A309125 with some interesting links like A035316 for the differences obtained with following Dirichlet generating function (and much more) : $$\zeta(s)\, \zeta(2s-2)$$ Details appear at $\,3.6\,$ (for $\,t=2$) in Richard Mathar's paper "Survey of Dirichlet Series of Multiplicative Arithmetic Functions".

Using the free pari/gp we may obtain these differences and (adding) your initial sequence :

 vz=vector(50,n,1)
 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...]
 vz2=vector(#vz,n,n*(sqrtint(n)^2==n))
 = [1, 0, 0, 4, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 16,...]
 d= dirmul(vz,vz2)
 = [1, 1, 1, 5, 1, 1, 1, 5, 10, 1, 1, 5, 1, 1, 1, 21, 1, 10, 1, 5, 1, 1, 1,...]
 s=0;vector(#vz,n,s+=d[n])
 = [1, 2, 3, 8, 9, 10, 11, 16, 26, 27, 28, 33, 34, 35, 36, 57, 58, 68, 69,...]
$\endgroup$
3
  • $\begingroup$ @bumble_bee: 'faster' may have different significations depending of context (that you didn't provide). This is a mathematical answer allowing to see the problem from other points of view (proposed in A035316) with the idea that this problem could be part of a more complicate one. For a direct software implementation use Yves Daoust's answer. $\endgroup$
    – Raymond Manzoni
    Apr 9, 2020 at 21:07
  • 1
    $\begingroup$ So Yves went away (he could undelete and modify his answer!) and you need a substitute? :-) His last message to you was "@bumble_bee: I mean that for a given ratio $k$, we consider the $i$ such that $ki^2\le N<(k+1)i^2$, or $\frac N{k+1}<i^2\le\frac Nk$. So, my bad, the expression "between two perfect squares" is wrong, as is probably the estimate of the complexity reduction." so that the discontinuity points in the sequence are simply given by the $\;\displaystyle i=\left\lfloor\sqrt{\frac Nk}\right\rfloor$ terms (for $k\ge 1$ but not going up to $N$). $\endgroup$
    – Raymond Manzoni
    Apr 10, 2020 at 14:55
  • 1
    $\begingroup$ The sum of the $i$ first squares is $i(i+1)(2i+1)/6$ so subtract this for two consecutive $i_k$ given by the previous relation (starting at the right with $k=1$). You'll have to stop for the consecutive $i_k$ too near one another (the cost of the simplification must not exceed the initial direct evaluation for the terms at the left). Excellent continuation, $\endgroup$
    – Raymond Manzoni
    Apr 10, 2020 at 15:00

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