Math? I Thought This Was Computer Science!

The first step to solving the problem is realizing that $f(a, b)$ will always be zero when $b > a$ . Using this fact we can simpify the expression to a finite summation instead of an infinite one. $G(n)=\sum _{ i=1 }^{ n }{ \sum _{ j=2 }^{ i }{ f(i,j) } }$ It's not too difficult to write functions for $f()$ and $G()$ that evaluate them as they are literally defined, but you'll likely run into trouble when you try to run it on $G(10^8)$ . It's way to slow!

Let's try summing things in a diferent order. If we run $f(a, b)$ for every $a\le n$ , it's going to return a value of at least 1 for all numbers that $b$ divides, of which there are exactly $\left\lfloor \frac { n }{ b } \right\rfloor$ . We'll add that number to our running sum. It's going to return 2 for all values divisible by $b^2$ , of which there are exactly $\left\lfloor \frac { n }{ b^2 } \right\rfloor$ . Since we already added 1 to the sum during our previous sweep, we'll just add 1 again to make the total value added to the sum from twice divisible numbers into 2. We can continue this for powers $p$ until $b^p>n$ , after which our floor will always be zero.

It takes far less time to run the above process for every number from 2 to n than running our original algorithm. Most of our iteration steps will actually run in constant time!

It takes 1.750411155 seconds to run the following java code with input $10^8$ on my computer and come up with the final answer of $\boxed{1857496376}$

static long G(long n)
{
    long sum = 0;
    for (long j = 2; j <= n; ++j)
    {
        sum += n / j;
        long pow = j * j;
        while (pow <= n)
        {
            sum += n / pow;
            pow *= j;
        }
    }
    return sum;
}

If anybody has a more efficient algorithm I'd love to see it! I feel like it's very possible that one exists.