0
$\begingroup$

In a previous question, I was looking for an equation for counting the number of the number of integers between $1$ and $x$ that have a prime factor besides $2$ or $3$.

There were 2 iterative equations that came up:

  • $x−\left\lfloor{log_2x}\right\rfloor−\left\lfloor{log_2\frac{x}{3}}\right\rfloor−\left\lfloor{log_2\frac{x}{9}}\right\rfloor− \dots$

  • $x - \left\lfloor{log_2x}\right\rfloor - \left\lfloor{log_3x}\right\rfloor - \left\lfloor{\frac{x}{6}}\right\rfloor + $ count integers in [$1,\frac{x}{6}$] with factor other than $2$ or $3$

There were two answers that involved interesting approximations:

  • $\dfrac{\log(2n) \log(3n)}{2 \log 2 \log 3}$ with error $O(\frac{n}{\log n})$

  • $\dfrac{\log(n)^2}{2 \log(2)\log(3)}$ with error $O(\log n)$

Are there any standard methods for getting from the iterative equations above to the approximation equations below? If not, would anyone be able to show an approach to be able to approximating either of the equations above with an error estimate?

Thanks very much,

-Larry

$\endgroup$
  • 1
    $\begingroup$ Since the number of numbers of the form $2^a3^b$ plays a role, you can look at wikipedia, smooth numbers (in this case $3$-smooth). A number is $k$-smooth, if every prime factor of it is $\le k$. $\endgroup$ – Peter Dec 17 '14 at 17:25
  • $\begingroup$ Thanks, Peter. I'll take a look at the wikipedia article on smooth numbers for details on approximating the total number less than a given integer $x$. $\endgroup$ – Larry Freeman Dec 17 '14 at 20:44
1
$\begingroup$

With Peter's help above, I was able to answer my question using the Wikipedia article on smooth numbers.

The best way to proceed on this is to recognize that the { number of integers $\le x$ with factor other than $2$ or $3$ } = $x$ - { the number of $3$-smooth numbers $\le x$ }

The number of 3-smooth numbers can be approximated using:

$$\Psi(x,3) = x \cdot \rho(u) + O(\frac{x}{log{\,3}}) $$

where $u = \dfrac{\log x}{\log 3}$

and

$\rho(u)$ is the Dickman function

and

$\Psi(x,y)$ denotes the number of $y$-smooth integers less than or equal to $x$

$\endgroup$

Your Answer

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

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