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

Question

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

Answer 1

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.

Answer 2

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}$.