Legendre's Formula for $\pi(x)$: Who identified the recurrence relation $\phi(x, a) = \phi(x, a - 1) - \phi( x / p_a, a - 1)$?

32 Views Asked by At

Whilst it is clear that Legendre was the first to notice that you could use the Inclusion-Exclusion Principle to directly compute $\pi(x)$ without finding all the primes up to $x$, I am having trouble figuring out if it was he who identified the recurrence relation $\phi(x, a) = \phi(x, a - 1) - \phi(x / p_a, a - 1)$ or a later mathematician (Meissal?).

Whilst I have found Legendre's Essai sur la théorie des nombres online, I have not had any luck finding an English translation. Still looking around for Meissal's work. I did find Lehmer's, which seems to suggest that Legendre only identified the sum, whilst Meissal identified the recurrence relation that made it practical; but his equation is also more advanced than just this recurrence equation. I would appreciate any help clarifying who did what exactly.

Also, Wikipedia and Wolfram refer to Legendre's equation for $\pi(x)$ as Legendre's Formula. But if you look around online, most of the results under that search will direct you to a different equation. Is there perhaps a better term for his prime counting function?

Thanks!

EDIT: See https://mathworld.wolfram.com/LegendresFormula.html