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.