Блог пользователя mister_bull

Автор mister_bull, история, 3 года назад, По-английски

Hola community.

My contribution is a bit low, so I wanted to ask a question. Inspired by cses problem, finding sum of divisors till 10^12,

I have the following question:

What will be sum of square of number of divisors till 10^12.

Just curious to know the answer, I some red guy can crack it ;)

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 5   Проголосовать: нравится +20 Проголосовать: не нравится

$$$\overset{n}{\underset{x = 1}{\LARGE \Sigma}} \tau(x)^2 = \overset{n}{\underset{x = 1}{\LARGE \Sigma}} \tau(x^2) \times \left \lfloor \frac{n}{x} \right \rfloor$$$

You can notice that the series $$$S = $$$ { $$$\left \lfloor \frac{n}{1} \right \rfloor, \left \lfloor \frac{n}{2} \right \rfloor, \dots, \left \lfloor \frac{n}{n} \right \rfloor$$$ } have $$$O(S) = O(2\sqrt{n})$$$

Therefore you can split into $$$O(\sqrt{n})$$$ interval of $$$\tau(x^2)$$$ to calculate

Now you need to calculate this fast enough $$$\overset{r}{\underset{x = l}{\LARGE \Sigma}} \tau(x^2)$$$

We also have $$$\overset{n}{\underset{x = 1}{\LARGE \Sigma}} \tau(x^2) = \overset{n}{\underset{x = 1}{\LARGE \Sigma}} S(\left \lfloor \frac{n}{x} \right \rfloor)$$$ where $$$S(n) = \overset{n}{\underset{x = 1}{\LARGE \Sigma}} \mu(x)^2 \times \left \lfloor \frac{n}{x} \right \rfloor$$$

But I am not sure if we can calculate this fast enough

Update: There is a also a formula that $$$T(n) = \overset{n}{\underset{x = 1}{\LARGE \Sigma}} 2^{\omega(x)} \left \lfloor \frac{n}{x} \right \rfloor$$$

Still, I am not sure if we can calculate $$$\overset{r}{\underset{x = l}{\LARGE \Sigma}} 2^{\omega(x)}$$$ fast enough

Editted: Fixed the barrack that was invisble on latex though it should not be like that

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I am trying to understand it, meanwhile is'nt the first line wrong ?

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

      Unless you have a proof in mathematics, I ran for $$$100.000$$$ tests and found the same result !

      Output - Horizontal
      Output - Vertical
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    For anyone lost, these transformations involved are relatives of those described in this blog. It turns out that for any sequence $$$a$$$,

    $$$ \displaystyle \sum_{x=1}^n a_x = \sum_{x=1}^n \lfloor \frac{n}{x} \rfloor (\mu * a)_x , $$$

    where $$$*$$$ denotes Dirichlet convolution and $$$\mu$$$ the Möbius function. The proof of this is straightforward. Letting $$$\zeta = (x \mapsto 1)$$$ and recalling that $$$\mu$$$ and $$$\zeta$$$ are inverses with respect to Dirichlet convolution, we have:

    $$$ \begin{array}{rl} \displaystyle \sum_{x=1}^n a_x & = \displaystyle \sum_{x=1}^n (\zeta * \mu * a)_x \\ & = \displaystyle \sum_{x=1}^n \sum_{d | x} (\mu * a)_d \\ & = \displaystyle \sum_{d, k \in \mathbb{Z}_{>0},\, dk \leq n} (\mu * a)_d \\ & = \displaystyle \sum_{x=1}^n \lfloor \frac{n}{x} \rfloor (\mu * a)_x \text{, as desired.} \end{array} $$$

    The first and last equations in (revision 3 of) the parent comment are instances of the above identity, since the following equations hold, where $$$\tau$$$ and $$$\omega$$$ count the number of factors and the number of prime factors, respectively.

    $$$ \displaystyle \mu * (x \mapsto \tau(x)^2) = (x \mapsto \tau(x^2)), $$$
    $$$ \displaystyle \mu * (x \mapsto \tau(x^2)) = (x \mapsto 2^{\omega(x)}) $$$
    $$$ \displaystyle \mu * (x \mapsto 2^{\omega(x)}) = (x \mapsto \mu(x)^2) $$$

    The claim that "$$$ \overset{n}{\underset{x = 1}{\LARGE \Sigma}} \tau(x^2) = \overset{n}{\underset{x = 1}{\LARGE \Sigma}} S(\left \lfloor \frac{n}{x} \right \rfloor) $$$ where $$$ S(n) = \overset{n}{\underset{x = 1}{\LARGE \Sigma}} \mu(x)^2 \times \left \lfloor \frac{n}{x} \right \rfloor $$$" is not of the same sort, but can be proven by a similar argument using two intermediate Dirichlet convolutions.

    I believe the necessary partial sums of $$$(x \mapsto \mu(x)^2)$$$ can be found in $$$\tilde{O}(n^{2/3})$$$ from the prime-counting function $$$\pi$$$ using a factorization technique nearly identical to the one this comment by ecnerwala uses to perform a pseudo-Euler transform. But $$$(10^{12})^{2/3}$$$ is still a rather large number considering that there are several stages of Dirichlet convolution mumbo jumbo that each incur a cost of roughly that magnitude in this solution.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 9   Проголосовать: нравится +8 Проголосовать: не нравится

      If I fix not the $$$\mu(x)^2$$$ function but the floor function $$$f(x) = \left \lfloor \frac{n}{x} \right \rfloor$$$ right here then can we calculate it fast enough ?

      Since the series $$$S = $$$ { $$$\left \lfloor \frac{n}{1} \right \rfloor, \left \lfloor \frac{n}{2} \right \rfloor, \dots, \left \lfloor \frac{n}{n} \right \rfloor$$$ } actually can be splited into $$$O(\sqrt[3]{n})$$$ parts:

      or parts that can be calculated in $$$O(\sqrt[3]{n})$$$

      there is actually a third method which used another idea but I am not sure if it is actually $$$O(\sqrt[3]{n})$$$ or faster and somewhat related to this comment

      But I am not sure if $$$\mu(x)^2 \times f(x)$$$ can be calculated this fast or maybe somehow even faster in this special case

      Also Rick Sladkey described in this comment that we can calculate $$$\overset{n}{\underset{x = 1}{\LARGE \Sigma}} \tau(x^2)$$$ in $$$O(n^{5/9})$$$

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I was aware of the fact that $$$D_2(n) = \sum_{i=1}^n \lfloor \frac{n}{i} \rfloor$$$ can be calculated in $$$O(n^{1/3})$$$ arithmetic operations, but didn't see any useful reduction to this. Sladkey's observation that $$$\mu(n)^2 = \sum_{d,\, d^2|n} \mu(d)$$$ is a nice one, and kind of obvious in hindsight. Maybe it's "well known to some people." The fast growth of $$$d^2$$$ is what provides the leverage needed to avoid paying the full $$$O(n^{2/3})$$$ cost of a full Dirichlet convolution. Unfortunately, for the same reason, using Sladkey's $$$O(n^{5/9})$$$ approach to calculating $$$\sum_{x=1}^{n} \tau(x^2)$$$ as a subroutine is not an option.

        But that's OK. For basically the same reasons Sladkey outlined, we have that

        $$$ \displaystyle \sum_{x=1}^{n} \tau(x)^2 = \sum_{a=1}^{\lfloor \sqrt{n} \rfloor} \mu(a) D_4(\lfloor \frac{n}{a^2} \rfloor), $$$

        where $$$D_4(n)$$$ is the number of 4-tuples of positive integers with product at most $$$n$$$. The method Sladkey's paper gives at the end of section 8 for calculating $$$D_4(n)$$$ ($$$T_4(n)$$$ in the notation of the paper) is $$$O(n^{2/3})$$$, but we can do a bit better. Start by calculating all values of $$$D_2(\lfloor \frac{n}{i} \rfloor)$$$. This can be done in $$$O(n^{3/5})$$$ by using the $$$O(n^{1/3})$$$ single-point method for $$$i \leq n^{2/5}$$$ and a linear sieve for the rest. In terms of these numbers, $$$D_4(\lfloor \frac{n}{i} \rfloor)$$$ can be calculated in $$$O(\sqrt{\frac{n}{i}})$$$ using the observation that a 4-tuple is just two 2-tuples. Then, calculating all of the terms in the formula for $$$\sum_{x=1}^{n} \tau(x)^2$$$ above takes only $$$O(n^{1/2} \log{n})$$$ time, so the overall time complexity is dominated by the $$$O(n^{3/5})$$$ calculation of the values of $$$D_2$$$.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          What an amazing solution that blow my mind each time I read one more line of you math.

          By the way, if I am not wrong then is the space complexity $$$O(n^{1/2})$$$

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Thank you! The sieve step for calculating values of $$$D_2(x)$$$ for $$$x \leq n^{3/5}$$$ is the limiting factor space-wise. It can probably be done with less than $$$O(n^{3/5})$$$ space by segmenting the sieve, but I currently know close to nothing about such techniques. Every other step needs only $$$O(n^{1/2})$$$ integers each not much bigger than $$$n$$$.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    That way is $$$O(n^{3/4})$$$ I think. So it will still take a while.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It's definitely possible to do it in $$$O(n^{2/3})$$$ using this method; I'm not sure if the $$$O(n^{2/3}/\log n)$$$ method will work here because we need to evaluate the prefix sum of this multiplicative function at all $$$\lfloor\frac nx\rfloor$$$.

      It might be possible to obtain a smaller constant factor by finding a good function and doing the Dirichlet sieve.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

Let's iterate through every number $$$d \in [1, n]$$$, and let's see its contribution to the answer. Of course, $$$d$$$ contributes to the Sum of squared divisors of a single number in $$$d^2$$$. How many times does $$$d$$$ do that? Well, there are $$$\left\lfloor\frac{n}{d}\right\rfloor$$$ multiples of $$$d$$$, so the contribution of $$$d$$$ to the answer is $$$\left\lfloor\frac{n}{d}\right\rfloor\cdot d^2$$$.

Hence, the answer is $$$\displaystyle\sum_{d = 1}^n \left(\left\lfloor\frac{n}{d}\right\rfloor\cdot d^2\right)$$$.

Obviously, computing it directly is not good, because $$$n \le 10^{12}$$$. But we can optimize it and make it work in $$$\mathcal{O}(\sqrt{n})$$$.

Fact: The sequence $$$a_1, a_2, \dots, a_n$$$, defined by $$$a_i = \left\lfloor\frac{n}{i}\right\rfloor$$$, has $$$\mathcal{O}(\sqrt{n})$$$ distinct values.

  • Proof: For every $$$i > \sqrt{n}$$$, it holds that $$$\left\lfloor\frac{n}{i}\right\rfloor < \sqrt{n}$$$. From that, it follows that there are at most $$$\sqrt{n}$$$ distinct values of $$$a_i$$$ for $$$i >\sqrt{n}$$$. Now, for $$$i \le \sqrt{n}$$$, obviously there are $$$\sqrt{n}$$$ values, and therefore there are at most $$$\sqrt{n}$$$ distinct values of $$$a_i$$$. Thus, there are at most $$$2\sqrt{n}$$$ distinct values in the sequence $$$a_1, a_2, \dots, a_n$$$. This concludes the proof.

Another fact: $$$a_i \ge a_{i+1}$$$.

  • Proof: $$$i < i+1\implies \frac{n}{i} > \frac{n}{i+1}\implies \left\lfloor\frac{n}{i}\right\rfloor \ge \left\lfloor\frac{n}{i+1}\right\rfloor$$$.

Now, we could split the sequence $$$a_1, a_2, \dots, a_n$$$ in maximal buckets where all $$$a_i$$$'s in the same bucket are equal. From the previous facts, it follows that there are $$$\mathcal{O}(\sqrt{n})$$$ buckets, and now for each bucket $$$[l, r]$$$ we need to add to the answer $$$\left\lfloor\frac{n}{l}\right\rfloor\cdot (l^2 + (l+1)^2 + \dots + r^2)$$$.

For computing the sum of the squares, we can use a well-known formula: $$$1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n\cdot(n + 1)\cdot(2n + 1)}{6}$$$.

Now, some sample code:

def sum_of_squares(n):
    return n * (n + 1) * (2*n + 1)//6

n = int(input())
l = 1
ans = 0
while l <= n:
    r = n//(n//l)
    ans += (n//l) * (sum_of_squares(r) - sum_of_squares(l-1))
    l = r + 1
print(ans)
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    This is a correct solution to a different problem. OP asks about the sum of the squares of the number of divisors, you calculate the sum of the squares of the divisors themselves. (Of course, your version is closer in both statement and solution to the CSES problem the OP refers to.)