  Let N_{a,b}(x) count the number of primes p<=x with p dividing a^k+b^k for
some k>=1. It is known that asymptotically N_{a,b}(x) grows like c(a,b)x/log x
for some rational number c(a,b) that depends in a rather intricate way on a and
b. A simple heuristic formula for N_{a,b}(x) is proposed and it is proved that
it is asymptotically exact, i.e. has the same asymptotic behaviour as
N_{a,b}(x). Connections with Ramanujan sums and character sums are discussed.
