3
$\begingroup$

I am trying to figure out the number of integers greater than $1$ and less than or equal to $x$ that have a prime factor other than $2$ or $3$. For example, there are only two such integer less than or equal to $7$.

It is straight forward to determine how many many integers less than or equal to $x$ have a prime factor other than $2$: $$x - \left\lfloor{\log}_2x\right\rfloor$$

Or to make the same determination about $3$: $$x - \left\lfloor{\log}_3x\right\rfloor$$

What is the method or formula for figuring out how many integers less than or equal to $x$ have a prime factor other than $2$ or $3$?

I know that it is less than:
$$x - \left\lfloor{\log}_2x\right\rfloor - \left\lfloor{\log}_3x\right\rfloor$$

and greater than: $$x - \left\lfloor{\log}_2x\right\rfloor - \left\lfloor{\log}_3x\right\rfloor - \left\lfloor\frac{x}{6}\right\rfloor$$

Thanks,

-Larry


Edit: Added a greater than clause.

$\endgroup$
  • $\begingroup$ Use the Inclusion-Exclusion principle. $\endgroup$ – Edward Jiang Dec 16 '14 at 2:54
  • 1
    $\begingroup$ Inclusion-exclusion (and $\log_6 x$) seems to be a red herring here: we exclude the powers of $2$, we exclude powers of $3$, and we need to keep excluding the other numbers of the form $2^a 3^b$. $\endgroup$ – Rebecca J. Stones Dec 16 '14 at 2:58
  • $\begingroup$ It's clearly equal to $x-\lfloor \log_2 x\rfloor - \lfloor \log_2 \frac{x}3 \rfloor - \lfloor \log_2 \frac{x}9 \rfloor-\ldots$. But that answer kind of stinks. $\endgroup$ – Milo Brandt Dec 16 '14 at 3:06
3
$\begingroup$

In Hardy's book of Twelve Lectures on Ramanujan's work, in the chapter "A lattice point problem", he discusses Ramanujan's result that

"the number of numbers of the form $2^x 3^y$ less than $n$ is

$\dfrac{\log(2n) \log(3n)}{2 \log 2 \log 3} $"

There is a very extended discussion of this problem. Among the results is a proof that the error in Ramanujan's formula is $O(\frac{n}{\log n})$

$\endgroup$
2
$\begingroup$

The answer is $n - A(n)$ where $A(n)$ is the number of integers $\le n$ of the form $2^x 3^y$. Now $A(n)$ is the number of nonnegative integer solutions of $x \log 2 + y \log 3 \le \log n$, i.e. the number of lattice points in the triangle $x \log 2 + y \log 3 \le \log n$, $x \ge 0$, $y \ge 0$. This is within $O(\log n)$ of the area of the triangle, i.e. $\log(n)^2/(2 \log(2)\log(3))$. But I doubt you'll get a "closed form" for the exact value.

EDIT: See also OEIS sequence A071521 and references there.

$\endgroup$
  • 1
    $\begingroup$ I was thinking this too; I believe Baker's theorem is relevant to finding better approximations (and maybe a closed form), since it lets you bound quantities like $x\log(2)+y\log(3)$ and I've seen papers where people somehow use it to get explicit, numeric bounds. You wouldn't happen to know how such tricks are done, and if they might be applicable here, would you? $\endgroup$ – Milo Brandt Dec 16 '14 at 3:15
  • $\begingroup$ Thanks to both of you. Wow. Some great topics to read up on. $\endgroup$ – Larry Freeman Dec 16 '14 at 3:25
  • $\begingroup$ I don't immediately see the relevance of Baker's theorem here. $\log(n) - x \log(2) - y \log(3)$ for nonnegative integers $x, y, n$ can be $0$ (if $n = 2^x 3^y$), or if positive it's at least $\log(n/(n-1))$ (with equality if $n = 2^x 3^y + 1$). $\endgroup$ – Robert Israel Dec 16 '14 at 3:27

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.