Take the 2-minute tour ×

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

$\sum_{i | p\\#}^{p\\#} \lfloor{\frac{p}{i}\mu(i)}\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,


share|improve this question
In your example, you seem to be summing mu(i)*floor(p/i) rather than floor(mu*p/i). –  David Cohen Jun 20 '12 at 22:59
Thanks, David. I'll update the example. –  Larry Freeman Jun 20 '12 at 23:01

1 Answer 1

up vote 6 down vote accepted

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$$

share|improve this answer
But Larry is using the floor function. Are you? Gerhard "Ask Me About System Design" Paseman, 2012.06.20 –  Gerhard Paseman Jun 20 '12 at 23:13
Thanks very much! I'll check out the proof behind the very well known equation! Cheers, -Larry –  Larry Freeman Jun 20 '12 at 23:15
Hi Gerhard, Yes, I am using the floor function. Isn't the equation cited by David also using a floor function? -Larry –  Larry Freeman Jun 20 '12 at 23:16
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}. –  David Cohen Jun 21 '12 at 2:49

Your Answer


