1
$\begingroup$

It is straight forward to count the number of integers $i$ where $1 < i < p\#$ and lpf($i$) $> p$.

If $p$ is the $n$th prime, then the count is $(p_n - 1)*(p_{n-1} - 1) * \dots *(2-1) - 1$

To count the number of integers $i$ where $1 < i < p\#$ and gpf($i$) $ > p$, the only thing that I could come up with is:

  1. Count the number where lpf($i$)$ > p$
  2. For each of these where lpf($i$)$ > p$ and $i \le \frac{p\#}{2}$, count the number of times each $i$ divides $p\#$ making sure not to double count.
  3. Then, add step #2 to $\frac{\text{step #1}}{2}$

Is there a more straight forward way?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.