1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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, 2014 at 17:07
  • $\begingroup$ Also on wikipedia: en.wikipedia.org/wiki/Legendre_sieve $\endgroup$
    – Terry Tao
    May 7, 2014 at 20:51

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.