Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The following identity seems to follow from a simple analysis of the sieve of Eratosthenes and inclusion-exclusion, where $p_i, p_j, p_k, \ldots$ denote primes and $N$ is an integer $\geq 2$:

$\Sigma_{p_i\leq N} \lfloor{N/p_i}\rfloor - \Sigma_{p_i, p_j\leq N} \lfloor{N/(p_i.p_j)}\rfloor + \Sigma_{p_i, p_j, p_k\leq N} \lfloor{N/(p_i.p_j.p_k)}\rfloor + \ldots = N - 1$

For example for $N = 6$, $\lfloor 6/2 \rfloor + \lfloor6/3\rfloor + \lfloor6/5\rfloor - \lfloor6/(3.2)\rfloor = 3 + 2 + 1 - 1 = 5 = 6 - 1$

Is this identity correct? If wrong, can it be fixed? If right, it must be well known -- so apologies in advance for a silly question, but is there a published reference? Also, is there any way to remove $N$ from the LHS so it becomes an identity/inequality only on sums of reciprocals of prime products?

share|improve this question
Legendre. Present in many books on primes and factorization. See e.g. Hans Riesel's book om computer methods, or Pomerance and Crandall's more recent text. –  The Masked Avenger May 7 '14 at 17:07
Thanks. I"ll look it up. Tim –  timvarghese May 7 '14 at 17:49
Also on wikipedia: en.wikipedia.org/wiki/Legendre_sieve –  Terry Tao May 7 '14 at 20:51
Thanks! That's a very accessible reference - Tim –  timvarghese May 7 '14 at 22:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.