1
$\begingroup$

I noticed that for primes $p \le 109$, the following seems to be true:

$$\sum_{i | p\#}^{p\#} \left\lfloor{\frac{p}{i}\mu(i)}\right\rfloor = 1$$

where $\mu(i)$ is the Mobius function.

For example:

$\frac{2}{1} + \frac{2}{2}(-1) = 1$

$\frac{3}{1} + \lfloor\frac{3}{2}(-1)\rfloor + \frac{3}{3}(-1) + \lfloor\frac{3}{6}\rfloor = 1$

and so on...

I verified this up to $p=109$ using a simple java application.

I might be making a mistake in my code or my thinking. This seems like a very surprising result to me.

Is it correct? If it is, does it stop being true for some prime? Could anyone help me to understand this result.

Thanks very much,

-Larry

$\endgroup$
1
  • 1
    $\begingroup$ In your example, you seem to be summing mu(i)*floor(p/i) rather than floor(mu*p/i). $\endgroup$ Jun 20, 2012 at 22:59

1 Answer 1

8
$\begingroup$

Assuming that $p\text{#}$ means the product over primes $\prod_{q\leq p}q$, then it is clear that $$\sum_{i\leq p} \mu(i)[\frac{p}{i}] = \sum_{i | p\text{#}} \mu(i)[\frac{p}{i}].$$

But this formula is very well known: $$\sum_{d\leq n} \mu(d)[\frac{n}{d}]=\sum_{k\leq n}\sum_{d | k} \mu(d)=1+0+0+\ldots$$

$\endgroup$
4
  • $\begingroup$ But Larry is using the floor function. Are you? Gerhard "Ask Me About System Design" Paseman, 2012.06.20 $\endgroup$ Jun 20, 2012 at 23:13
  • $\begingroup$ Thanks very much! I'll check out the proof behind the very well known equation! Cheers, -Larry $\endgroup$ Jun 20, 2012 at 23:15
  • $\begingroup$ Hi Gerhard, Yes, I am using the floor function. Isn't the equation cited by David also using a floor function? -Larry $\endgroup$ Jun 20, 2012 at 23:16
  • $\begingroup$ I am using [] to denote floor. The first equality in the second equation comes from reversing the order of summation on the right hand side, since d divides exactly [n/d] elements of {1,...,n}. $\endgroup$ Jun 21, 2012 at 2:49

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.