Given a function $G(N)$ defined as
$$G(N)=\sum_{j=1}^{N}\sum _{i=1}^{j} GCD(i,j)$$ where $GCD$ is Greatest Common Divisor of two numbers
If it is known that $G(10)=122$, Find Value of $G(10^{11})$
Source: https://projecteuler.net/problem=625
I dont have any clue but i hope its useful to convert summation as
$$G(N)=122+\sum_{j=11}^{100}\sum_{i=1}^{j} GCD(i,j)$$
$\sum_{k=1}^{j}\gcd(k,j)$ is Pillai's function, which equals $\sum_{d\mid j}d\cdot \varphi(j/d)=j\sum_{d\mid j}\frac{\varphi(d)}{d}$.
In particular $$ \sum_{n=1}^{N}\sum_{k=1}^{n}\gcd(k,n) = \sum_{n=1}^{N} n \sum_{d\mid n}\frac{\varphi(d)}{d} = \frac{1}{2}\sum_{d=1}^{N}\varphi(d)\left\lfloor\tfrac{N}{d}\right\rfloor\left(\left\lfloor\tfrac{N}{d}\right\rfloor+1\right)$$ and the asymptotic behaviour of $\sum_{d=1}^{N}\frac{\varphi(d)}{d^s}$ is pretty well-known, for instance through $$ \forall s>2,\qquad \sum_{n\geq 1}\frac{\varphi(n)}{n^s} = \frac{\zeta(s-1)}{\zeta(s)} $$ and the tauberian theorem, or summation by parts applied to $$ \sum_{n=1}^{N}\varphi(n) = \frac{3}{\pi^2}N^2+O\left(N\log N\right).$$ Unluckily we need to derive many terms of such asymptotic behaviours to get an exact value of $G(10^{11})$, and I am too lazy to really do it. Roughly, $G(N)\approx \frac{3}{\pi^2}N^2\log(N+1)$.
It looks like the computation of $G(1000)$ was asked before.