# How to compute sum of sum of gcd of factor pairs of a number upto a large number efficiently?

Define $$f(n)=\sum_{d|n}gcd(d,\frac{n}{d})$$ $$F(x)=\sum_{n=1}^xf(n)$$ for natural numbers d,n and x.

I would like to know if there is some simplified form of $$F(x)$$ in terms of arithmetic functions, or atleast some computationally feasible form for large $$x$$.($$x$$ is of the order $$10^{15}$$ or higher).

A brute force approach is not efficient because of the $$d|n$$.Exchanging the summations is a slight improvement.But even after that I can't evaluate $$F(x)$$ for $$x>10^7$$ within reasonable time for which I believe a total mathematical algorithmic change is needed.

How can we manipulate the given expression so that the computation is reasonably fast?

EDIT:I just found out this is one of the Project Euler problems-problem no. 530

• Actually we dont even need n, since there is a sum over n too while defining F(x). Sep 2, 2020 at 8:34
• Perhaps you can precompute the values of $f(n)$ and $F(x)$.
– cgss
Sep 2, 2020 at 8:34
• No idea whether this is of any use. But for squarefree $n$, $f(n)$ is just the number of divisors of $n$. Sep 2, 2020 at 8:54
• No idea whether this is of any use, but if we define $$c(p,i):=\begin{cases} 2p^{\tfrac{i+1}{2}}&\text{ if }i\equiv1\pmod{2}\\ p^{\tfrac i2+1}+p^{\tfrac i2}&\text{ if }i\equiv0\pmod{2}\ \end{cases},$$ then for the function $S(n,k)$ defined by the recursion $$S(n,k):=\sum_{i=0}^{\lfloor\log_{p_k}x\rfloor}\frac{c(p_k,i)-2}{p_k-1}S\big(\lfloor\tfrac{x}{p_k^i}\rfloor,k+1\big),$$ and $S(0,k)=0$ and $S(1,k)=1$, we have $$S(x,1)=\sum_{n=1}^x\sum_{d\mid n}\gcd(d,\tfrac dn)=F(x).$$ Here $p_k$ denotes the $k$-th prime, starting from $p_1=2$. Sep 3, 2020 at 16:44

PARTIAL ANSWER: Here is an alternative formula for $$F(x)$$: $$F(x)=\sum_{k=1}^{\sqrt{x}}g_x(k)k$$ where $$g_x(k) = |\{ (a,b) : abk^2 \le x, \ \gcd(a,b)=1 \}|$$

proof:

For a fixed $$x>0$$, consider the following set $$I_x=\{ (k, d, n) \ : \ k=\gcd(d, n/d), \ \ d|n,\ \ n \le x\}$$ Then your $$F(x)$$ is just $$F(x)= \sum_{(k,d,n) \in I_x} k$$ Let's study how this set $$I_x$$ is made.

First of all, note that for all $$(k,d,n) \in I_x$$ you have that $$k$$ divides both $$d$$ and $$n/d$$, hence $$k^2 \ \mbox{ divides } n = d \cdot (n/d)$$ In particular $$k \le \sqrt{x}$$.

On the other hand, for arbitrary $$k \le \sqrt{x}$$ you have $$(k,k,k^2) \in I_x$$. This means that all numbers $$k \le \sqrt{x}$$ appear at least once as the first coordinate of a triple $$(k,d,n) \in I_x$$, while all numbers $$k > \sqrt{x}$$ don't.

So, let's call $$g_x(k) = |\{ (d,n) \ : \ (k,d,n) \in I_x \}|$$ This function counts how many times $$k$$ appears as a first coordinate of a triple $$(k,d,n) \in I_x$$, so that $$F(x)= \sum_{(k,d,n) \in I_x} k=\sum_{k=1}^{\sqrt{x}} g_x(k) \cdot k$$ To conclude the proof we have to show that $$g_x(k) = 2 \lfloor \frac{x}{k^2} \rfloor-1$$

For a fixed $$k \le \sqrt{x}$$, you have that $$(k,d,n) \in I_x$$ if and only if $$k= \gcd(d,n/d)$$. This means that $$d=ak$$ and $$n/d=bk$$ for some $$a,b$$. Thus we can consider the set of quintuples $$J_x= \{ (k,a,b,d,n) \ : \ d=ak, \ n/d=bk, \ \gcd(a,b)=1, \ d|n, \ n \le x \}$$ which is in clear bijection with $$I_x$$ by the map $$(k,a,b,d,n) \mapsto (k,d,n)$$. Note that $$a=d/k$$ and $$b=n/(dk)=n/(abk^2)$$. So that our $$J_x$$ is in bijection with the set $$L_x = \{ (k, a, b) : \ abk^2 \le x , \ \gcd(a,b)=1\}$$ by the map $$(k,a,b,d,n) \mapsto (k,a,b)$$, because $$n=abk^2 \le x$$. In other words $$g_x(k)$$ counts the number of pairs $$(a,b)$$ of coprime numbers $$a,b$$ such that $$abk^2 \le x$$, or $$ab \le \frac{x}{k^2}$$

continues...

OK, MY BAD, NOW I NOTICED THAT THIS NUMBER IS NOT $$2 \lfloor \frac{x}{k^2} \rfloor-1$$, BUT IT'S TRICKIER. I'll leave this answer for who wants to conclude my computations.

• Appears to be a very nice approach (+1) Sep 2, 2020 at 9:15
• $(k,k,k) \not\in I_x$. Perhaps you meant $(k,k,k^2)$?
– cgss
Sep 2, 2020 at 9:30
• Sorry guys, while I was writing the proof I noticed that my idea was good, but more complicated than I thought. Sep 2, 2020 at 9:47

It can be proved that $$\displaystyle \sum_{d\mid n} (d,n/d) = \sum_{d^2\mid n}\tau(n/d^2)\varphi(d)$$.

So one can show that $$\displaystyle F(x) = \sum_{n\le \sqrt{x}}\varphi(n)\sum_{m \le x/n^2} \left\lfloor\frac{x}{n^2 m}\right\rfloor$$.

This is the best i can do, but this is still computationally unfeasible for $$x \approx 10^{15}$$.

• With this formula, my computer calculate $F(10^9)$ in about 13 minutes. Since it grows at least linearly, $x = 10^{15}$ is definitely out of range. Sep 2, 2020 at 14:34
• You have a typo in your formula for $F(x)$, it ought to be $$F(x) = \sum_{n \leqslant \sqrt{x}} \varphi(n) \sum_{m \leqslant x / n^2} \biggl\lfloor \frac{x}{m\cdot n^2}\biggr\rfloor\,.$$ And you can easily make that computationally feasible ($7$ seconds for $x = 10^{15}$ in not yet optimised C on my old laptop) using two tricks. First, don't compute $\varphi(n)$ for each $n$ separately, precompute all needed values in an array, similar to a sieve of Eratosthenes (takes $O(\sqrt{x})$ space and $O(\sqrt{x}\,\log \log x)$ time as long as you can use a builtin integer type). Sep 3, 2020 at 11:23
• (For $10^{15}$, 64-bit integers suffice.) Second, for the inner sum use Dirichlet's trick (hyperbola method), $$T(y) = \sum_{k \leqslant y} \tau(k) = \sum_{k \leqslant y} \biggl\lfloor \frac{y}{k}\biggr\rfloor = 2\sum_{k \leqslant \sqrt{y}} \biggl\lfloor \frac{y}{k}\biggr\rfloor - \lfloor \sqrt{y}\rfloor^2$$ to compute $T(y)$ in $O(\sqrt{y})$ time. That gives an overall time complexity of $$\sum_{n \leqslant \sqrt{x}} O\biggl(\sqrt{\frac{x}{n^2}}\biggr) = O\bigl(\sqrt{x}\,\log x\bigr)\,.$$ If that's not fast enough one can start to optimise. Sep 3, 2020 at 11:23
• @DanielFischer Thank you, i corrected the typo. Doh! how I forgot the Dirichlet's trick?! That make it computationally feasible! Sep 3, 2020 at 14:45
• I kinda hoped you'd also include the algorithmic suggestions in your answer. Sep 3, 2020 at 14:47