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?

  • 2
    $\begingroup$ 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. $\endgroup$ – The Masked Avenger May 7 '14 at 17:07
  • $\begingroup$ Also on wikipedia: en.wikipedia.org/wiki/Legendre_sieve $\endgroup$ – Terry Tao May 7 '14 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.