How to simplify $F(k)=\sum\limits_{n=1}^k\sum\limits_{d|n}\gcd({d},{\frac{n}{d}})$?

Question

I have the following summation:

$$F(k)=\sum\limits_{n=1}^k\sum\limits_{d|n}\gcd\left({d},{\frac{n}{d}}\right)$$

This is nearly impossible to compute (using coding) for large numbers, due to the time it'd take.

It's been suggested that the above summation can be simplified to this:

$$F(k)=\sum_{d=1}^{d^2\leqslant k}\ \sum_{n=1}^{nd\leqslant k}\gcd({d},{n})$$

I've tried testing the simplification, and it doesn't work. For instance, F(10) gives an output of 22 instead of 32.

How do I simplify the first summation?

Stuff here might be relevant, but I'm not sure: Wikipedia: Divisor function.

EDIT: Algorithm for thefunkyjunky's suggestion:

long k = 10;

    for (long d = 1; d*d <= k; d++) {
        for(long n = 1; n*d <= k; n++) {
            if (d*d <= n) result = result.add(BigInteger.valueOf(GCD(d,n)));
        }
    }

Answer 1

You can use the fact that if d is a divisor such that $d<\sqrt{n}$, then $\frac{n}{d} > \sqrt{n}$ and $\frac{n}{d}$ is also a divisor of $n$. So $gcd(d, \frac{n}{d})$ form pairs of gcds, which means that you can compute for divisors only smaller than $\sqrt{n}$ and then multiply the sum by $2$ which is(I think) fast enough.

EDIT: I forgot to add that you need to make a special case when $n$ is a square, because then you have $d$ that $d^2=n$ and the $gcd(d, d)$ factor must be counted only once, not twice.

EDIT2: The algorithm I had in mind was:

long sum = 0;
for(int n = 1; n <= k; n++) {
    for(int d = 1; d <= sqrt(n); d++) {
        if(n % d == 0) {
            if(d * d != n)
                sum += gcd(d, n / d) * 2;
            else
                sum += d; // GCD(d, d) = d
        }
    }

}

But I think yours is faster. What you do(if you haven't understood it) in your algorithm is just finding all pairs $(x, y)$ such that $xy \leq k$ which means that their gcd is included in the sum as divisors of some $n = xy$

EDIT3: The algorithm that you firstly tried to implement(the rewritten sum) has a mistake. It can be written as(The following is a combination of my and your solution):

int sum = 0;                                                                                            
for(int x = 1; x * x <= k; x++) {                                                                        
     for(int y = x; x * y <= k; y++) {                                                                    

         if(x != y) sum += 2 * gcd(x, y);                                                                
         else sum += x;                                                                                  

     }                                                                                                   
 }   

Please comment to tell me whether it passes(I'm also interested)!

Answer 2

I have found another way to calculate this, although I am not really answering the question of how to rearrange the original sum.

I started by considering for myself the possible pairs and the $gcd$s:

n= 1:  (1,1)                        1                 f( 1)=1   F( 1)= 1
n= 2:  (1,2)  (2,1)                 1  1              f( 2)=2   F( 2)= 3 
n= 3:  (1,3)  (3,1)                 1  1              f( 3)=2   F( 3)= 5
n= 4:  (1,4)  (2,2)  (4,1)          1  2  1           f( 4)=4   F( 4)= 9
n= 5:  (1,5)  (5,1)                 1  1              f( 5)=2   F( 5)=11
n= 6:  (1,6)  (2,3)  (3,2)  (6,1)   1  1  1  1        f( 6)=4   F( 6)=15
n= 7:  (1,7)  (7,1)                 1  2  1           f( 7)=2   F( 7)=17
n= 8:  (1,8)  (2,4)  (4,2)  (8,1)   1  2  2 1         f( 8)=6   F( 8)=23
n= 9:  (1,3)  (3,3)  (9,1)          1  3  1           f( 9)=5   F( 9)=28
n=10: (1,10)  (2,5)  (5,2) (10,1)   1  1  1  1        f(10)=4   F(10)=32

I didn't find it obvious what was going on here, so I laid out the same results like this:

I noticed that the table can be viewed as a set of inverted "V"s.

The entries for $(1,n)$ and $(n,1)$ make one such V: with all the $gcd$ equal to 1.

The entries for $(2,\frac n2)$ and $(\frac n2,2)$ make another V (marked in green): but the entries start with 2 and then alternate 1, 2, 1, 2, ...

It is important to note also that the $i$th V begins at $n=i^2$ with a single value $gcd = i$, then continues on with $2(i-1)$ values of $gcd=1$ and then 2 values of $gcd=i$, with this pattern being repeated.

By my method we have $F(n)=\Sigma_{i=1}^{i={\sqrt n}}V(i,n)$

where $V(i,n)$ is the sum of the values in the $i$th V and is found by this algorithm:

Find positive integers $p$ and $q$ so that $n=pi^2+qi+r$.

Then $V(i,n)=i + 2(p-1)(2i-1)+2q$

I think this might be better because there is no need to calculate any $gcd$.