2
$\begingroup$

Let $a,n$ be any positive integers.

Let $\varphi(x)$ be the Euler totient function.

It seems to me that the number of elements $x$ with $a \le x < a+n$ that have a given least prime factor will be less than each of the following expressions:

  • $\left\lfloor\dfrac{n}{2\#}\right\rfloor + 1$
  • $2\left\lfloor\dfrac{n}{3\#}\right\rfloor + 2$
  • $8\left\lfloor\dfrac{n}{5\#}\right\rfloor + 8$

  • $\vdots$

  • $\varphi(p\#)\left\lfloor\dfrac{n}{p\#}\right\rfloor + \varphi(p\#)$

Am I correct in this assumption? Will each of these expressions always be larger than the actual count of elements with a given least prime factor in a sequence of size $n$?

I ask because I made this assumption in a question I asked previously (now deleted) and I seemed to confuse everyone. One person asked why I was using $30$, I explained that $30 = 5\#$ and tried to explain that I was using it to count the elements with a given least prime factor.

I think that my explanation confused everyone more.

I am also wondering if there is a better way to estimate the number of elements with a given least prime factor in a such a sequence.

$\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.