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