MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
2  
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

 
discard

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

Browse other questions tagged or ask your own question.