2

For $p=2$ the answer is all of them (given that between here can only reasonably mean strictly between). For $p=3$ or 5 or 7 the answer is just under half of them. But for $p=11$, unless I slipped up it is just 29 out of 110.

I am afraid the answer as $p$ rises may be embarrassingly obvious, but don't see the pattern, so I want to ask.

I am not looking for an exact count. That is why I did not report the exact count for $p=3,5,7$ though of course I found it.

Colin McLarty
  • 1,956
  • It is exactly $\pi(p^2)-\pi(p)$. So answer is calculation of $\pi(p^2)$, which is unknown in general. – Gevorg Hmayakyan Dec 05 '17 at 00:08
  • Are you expecting an exact count? I can see estimating the count by way of the average density of prime numbers, and perhaps in some sense a formula that gives an "exact" number (but without being practical for computation). – hardmath Dec 05 '17 at 00:09
  • 3
    @GevorgHmayakyan No it's not; that's just the number of primes in $(p,p^2)$. A number in $(p,p^2)$ doesn't need to be prime to have a prime factor greater than $p$. – Milo Brandt Dec 05 '17 at 00:09
  • OK. Seems I misunderstood, you mean that only one prime factor is greater, but not all. – Gevorg Hmayakyan Dec 05 '17 at 00:10
  • OK. So it can not have more than one prime factor from the range $p..p^2$. This means that it should depend on the $\pi(p^2)-\pi(p)$ diff, which can be only estimated, no exact formula. So do you want to find the exact count, if so the answer is that it is not known. – Gevorg Hmayakyan Dec 05 '17 at 00:13
  • But we can define the $\pi(p^2)-\pi(p)$ as some $\delta(p)$ and represent the solution in terms of this $\delta(p)$. – Gevorg Hmayakyan Dec 05 '17 at 00:15
  • Between $11$ and $121,$ isn't the count $60$? – RideTheWavelet Dec 05 '17 at 00:22
  • 1
    We could write this as $$\sum_{p<p'<p^{2}}\left\lfloor\frac{p^{2}}{p'}\right\rfloor.$$ – RideTheWavelet Dec 05 '17 at 00:26
  • @RideTheWavelet I just posted that as answer, but derived independently. – orlp Dec 05 '17 at 00:27
  • @orlp It was that idea's time, I suppose. – RideTheWavelet Dec 05 '17 at 00:27

2 Answers2

2

As RideTheWavelet noted in comments below the OP, the exact answer is given by

$$\sum_{p\lt q\le p^2}\left\lfloor p^2\over q\right\rfloor$$

where the sum is over primes $q$ between $p$ and $p^2$. An upper bound is therefore

$$p^2\sum_{p\lt q\lt p^2}{1\over q}$$

Since

$$\sum_{q\lt x}{1\over q}\approx\ln(\ln x)$$

for large $x$, we get $p^2(\ln(\ln(p^2)-\ln(\ln p))=p^2\ln2$ as an approximate upper bound for large $p$. For a lower bound we have

$$p^2\sum_{p\lt q\lt p^2}{1\over q}-\sum_{p\lt q\lt p^2}1\approx p^2\ln2-(\pi(p^2)-\pi(p))\approx p^2\ln2-{p^2\over2\ln p}=p^2\left(\ln2-{1\over2\ln p} \right)$$

Again, the approximations here are trustworthy only for large $p$. However, we can at least look at them for a small prime like $p=11$. They suggest $121\ln2\approx83.87$ as an upper bound and $121(\ln2-1/(2\ln11))\approx58.64$ as a lower bound. This doesn't come close to the OP's count of $29$. But that count is inaccurate: There are $25$ primes between $11$ and $121$, and the correct count turns out to be

$$\sum_{11\lt q\lt121}\left\lfloor121\over q\right\rfloor=\left\lfloor121\over 13\right\rfloor+\left\lfloor121\over 17\right\rfloor+\cdots+\left\lfloor121\over 113\right\rfloor=9+7+\cdots+1=60$$

So that untrustworthy lower bound, in this case, is surprisingly accurate!

Barry Cipra
  • 79,832
  • So (unless i slipped up again), this lower bound will be over half of $p$ whenever $p\geq 13$, right? – Colin McLarty Dec 05 '17 at 01:47
  • @ColinMcLarty, I think you mean half of $p^2$, not $p$. Asymptotically, the fraction of numbers between $p$ and $p^2$ that are divisible by a prime greater than $p$ goes to $\ln2\approx69.3%$. It might be of interest to compute the exact fraction for additional small values of $p$, to see how good (or bad) the approximations are. – Barry Cipra Dec 05 '17 at 02:59
  • Right, yes. Thanks. – Colin McLarty Dec 05 '17 at 03:11
1

We know the number of primes in $[p,p^2]$ is gonna be $\pi(p^2)-\pi(p)$. However we also need to include numbers of the form $kq$, where $q$ is prime and $p<q<p^2$. For each such $q$, there are roughly $(p^2-p)/q$ such $k$'s.

The $n$'th prime $p_n\approx n\ln n+n\ln\ln n-n$. If $q$ is prime, then it's index is $\pi(q)$. So we're summing:

$$\sum_{p<q<p^2, q:\mbox{ prime }}\frac{p^2-p}{q}\approx (p^2-p)\sum_{r=\pi(p)}^{\pi(p^2)}\frac{1}{r\ln r}\approx (p^2-p)[\log(\log(\pi(p^2))-\log(\log(\pi(p))].$$

Alex R.
  • 32,771