Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $ f: \mathbb{N} \to \mathbb{N} $ be a number-theoretic function satisfying $ f(xy) = f(x) + f(y) $ whenever $ \gcd(x,y) = 1 $.

How can I prove that $$ \sum_{\substack{p ~ \text{prime}; \\ p \leq n}} f(p) \frac{p}{n} \bigg\lceil \frac{n}{p} \bigg\rceil \left\{ \frac{n}{p} \right\} \sim \frac{1}{2} \sum_{\substack{p ~ \text{prime}; \\ p \leq n}} f(p), $$ i.e., the ratio of these two sums, as $ n $ tends to $ \infty $, is equal to $ 1 $?

Notation: $ \lceil \cdot \rceil $ denotes the ceiling function, and $ \{ \cdot \} $ the fractional-part function.

If someone could just simplify the problem, not even necessarily prove it, I would greatly appreciate it.

Also, I don't know if the following relations might help in a proof/simplification: \begin{align} \lim_{n \to \infty} \frac{1}{n} \sum_{k=1}^{n} \frac{k}{n} \bigg\lceil \frac{n}{k} \bigg\rceil \left\{ \frac{n}{k} \right\} &= \frac{1}{2}, \\ \lim_{n \to \infty} \frac{1}{n} \sum_{\substack{p ~ \text{prime}; \\ p \leq n}} \frac{p}{n} \bigg\lceil \frac{n}{p} \bigg\rceil \left\{ \frac{n}{p} \right\} &= \frac{1}{2}. \end{align}

share|improve this question
you think you can spare "at least" in your first line ? what does that mean? –  ashley Dec 24 '12 at 1:05
It means thats the only property it has to satisfy, other then that, it can satisfy any propertys you want, for example the natural logarithm satisfies those conditions because not only does it satisfy $ln(ab)=ln(a)+ln(b)$, when gcd(a,b)=1, it also does it when gcd(a,b) is not equal to one. –  Ethan Dec 24 '12 at 1:31
Ethan, when you ask a question, please do not use non-standard abbreviations. For example, not many people know that 'idk' means 'I don't know'. Also, please keep the question and comments about notation separate. It is not advisable to bunch them together in a single sentence. –  Haskell Curry Dec 27 '12 at 3:23
I don't understand what your saying –  Ethan Dec 27 '12 at 4:20
(1) You wrote 'Also, idk if the following relations might help...', so I replaced 'idk' by 'I don't know'. (2) You asked how you could prove that the ratio is $ 1 $ and then tried to explain the meaning of $ \lceil \cdot \rceil $ and $ \{ \cdot \} $, all in one sentence! Such practice is not part of good mathematical exposition. Try to separate your question from comments about notation that you have used. Readers aren't in a rush to read your post, so you don't have to worry if they are unfamiliar with notation that you intend to explain right after the question is posed. –  Haskell Curry Dec 27 '12 at 5:08

1 Answer 1

The statement that $\sum_{\substack{p ~ \text{prime}; \\ p \leq n}} f(p) \frac{p}{n} \bigg\lceil \frac{n}{p} \bigg\rceil \left\{ \frac{n}{p} \right\} \sim \frac{1}{2} \sum_{\substack{p ~ \text{prime}; \\ p \leq n}} f(p)$ is not true in general.

Consider the following counterexample: \begin{equation} f(x)= \begin{cases} 1& \text{if $n$ is even} \\ 0& \text{if $n$ is odd} \end{cases} \end{equation}

Then $\frac{1}{2} \sum_{\substack{p ~ \text{prime}; \\ p \leq n}} f(p)=\frac{1}{2}$ and \begin{equation} \sum_{\substack{p ~ \text{prime}; \\ p \leq n}} f(p) \frac{p}{n} \bigg\lceil \frac{n}{p} \bigg\rceil \left\{ \frac{n}{p} \right\}= \frac{2}{n} \bigg\lceil \frac{n}{2} \bigg\rceil \left\{\frac{n}{2}\right \} \begin{cases} 0& \text{if $n$ is even} \\ \frac{n+1}{2n} & \text{if $n$ is odd}\end{cases} \end{equation}

Thus the ratio of the 2 sums has no limit. (Though if we restrict $n$ to be odd then the limit of the ratio is indeed 1)

Are there additional restrictions?

share|improve this answer

Your Answer


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

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