A similar problem is A018805, where a(n) is the
number of coprime pairs
(x, y) with 1 <= x,y <= n.
I found the recursion
a(n) = n^2 - SUM(j=2..n;
a(floor(n/j)))
This recusion is gotten by noticing that the
number of pairs (x,y) with
gcd(x,y) = j, 1
<= x,y <= n, is just a(floor(n/j)). So a(n) is gotten
by taking all n^2 pairs, and subtracting out
those whose gcd's fall
between 2 and n.
With clever programming, this identity is the
basis for a fairly quick
algorithm for a(n), much faster than the obvious
SUM(j=1..n; phi(j)).
I was hoping something similar might be done with
A027424. For example,
observe that the number of distinct even entries
in the n x n
multiplication table is just the number of
distinct entries in the
n x floor(n/2) multiplication table, analogously
for entries divisible
by other primes.