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 $p(n)$ denote the number of primes less than $n$. Show that there are infinitely many $n$ for which $n$ is divisible by $p(n)$.

Source : here

share|improve this question
1  
Welcome to Math.SE! Since you're new here, I thought I'd mention that we like to see the work you have done in trying to answer you own question--it prevents us from back-tracking and doing unnecessary searching. On a side note more related to your question, you may want to research the prime counting function (often denoted $\pi(n)$), as this is the typical name given to your $p(n)$. –  anorton May 27 '13 at 16:46
    
@anorton: The prime counting function $\pi(n) $ is the number of primes less than or equal to n. This is not the same as the OP's function. –  daniel May 27 '13 at 17:58
    
@daniel I stand corrected. Sorry. Then $p(n) = \pi(n-1)$, right? –  anorton May 27 '13 at 18:57
    
@anorton: Right. –  daniel May 27 '13 at 18:58

1 Answer 1

up vote 9 down vote accepted

Hint: Let $f(n): \mathbb{N} \rightarrow \mathbb{N}$ be a function such that $f(n+1) - f(n) = 0 $ or $1$ and $\lim_{n\rightarrow \infty} \frac{ n} { f(n) } \rightarrow \infty$.

Show that the image of $\frac{ n}{f(n) } $ includes all integers greater than $\frac{ 1}{f(1)} $. It will help for you to consider how this function behaves going from $\frac{n}{f(n)} $ to $\frac{n+1} { f(n+1)}$.

Proof: Consider the integer valued function $g(n) = n - k f(n)$, where $k$ is an integer greater than $\frac{1}{f(1)}$. Observe that $g(n+1)-g(n)$ is equal to 1 (if $f(n+1)=f(n)$) or is negative (if $f(n+1) > f(n)$). From the conditions, we get that $g(1)$ is negative, and $g(n)$ is eventually positive for a large enough value of $n$. Hence, there is a value $n^*$ such that $g(n^*) = 0$, which gives us $\frac{n^*}{f(n^*)} = k $.


The reason for presenting the answer this way, is that it has nothing to do with the prime counting function, apart from the properties listed in the hint.

share|improve this answer
1  
I scratched my head over "the image of $\frac{n}{f(n)}$" for a while. You mean the image of the function $g:\mathbb N \to \mathbb R$ defined by $g(n) = \frac{n}{f(n)}$, right? –  TonyK May 27 '13 at 18:11
1  
@TonyK Yes. That is what it means. –  Calvin Lin May 27 '13 at 18:40
1  
I guess this idea can be shown by induction. If we have n/p(n) = k then for some m we must be able to get m/p(m) = k+1. But my version is verbose. Is there a better way? +1 –  daniel May 27 '13 at 21:58
    
@daniel Certainly. The easiest way I know, is to consider the integer valued function $n - k g(n)$, where $k$ is an integer that's larger than $\frac{1}{f(1)}$. This starts off negative (or 0), and eventually becomes positive. Each step, it either increases by 1 (if $f(n)$ stays constant) or decreases by a bunch (if $f(n)$ increases). Show that there is some value such that $n^* - k g(n^*) = 0 $. –  Calvin Lin May 27 '13 at 22:01
1  
@karmanaut: I thought Calvin's solution was good and didn't want to distract by posting it--if you like I can try to re-do it and post. Too long for comment. –  daniel Jun 2 '13 at 9:55

Your Answer

 
discard

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.