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
    $\begingroup$ In your example, you seem to be summing mu(i)*floor(p/i) rather than floor(mu*p/i). $\endgroup$ – David Cohen Jun 20 '12 at 22:59
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$
  • $\begingroup$ But Larry is using the floor function. Are you? Gerhard "Ask Me About System Design" Paseman, 2012.06.20 $\endgroup$ – Gerhard Paseman Jun 20 '12 at 23:13
  • $\begingroup$ Thanks very much! I'll check out the proof behind the very well known equation! Cheers, -Larry $\endgroup$ – Larry Freeman Jun 20 '12 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$ – Larry Freeman Jun 20 '12 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$ – David Cohen Jun 21 '12 at 2:49

Your Answer

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

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