Number of the positive integers up to $\sqrt x $ generated by the prime factors of $x$.

102 Views Asked by At

Let $x$ be a natural number and $F_x$ be the set of distinct prime factors of $x$. One more let $\langle F_x \cup \{ 1 \} \rangle$ be multiplicative semigroup generated by the set. Then, the problem what I ask is that the cardinality of the set $$ \{ n \mid n\in \langle F_x \cup \{ 1 \} \rangle , \ n \leq \sqrt x \} .$$

It would be siffice to prove for primorials, the cardinality is less than $$ \log_2 x \log_3 x \log_5 x \cdots \log_p x , \ \ \text{for a primorial }\ x=2\cdot 3 \cdot 5 \cdot \cdots \cdot p.$$ Now, if we use that $\pi(n)\sim n/ \log n$, the product brings so big estimation, whilst it seems to $o( \sqrt x / \log x).$

Are there some methods or papers to find an efficient estimation of the cardinality?

1

There are 1 best solutions below

0
On BEST ANSWER

Tea almost ready; you are asking, for example, how many triples $r,s,t$ satisfy $$ 2^r 3^s 5^t \leq W. $$ Take the logarithm, $$ r \, \log 2 + s \, \log 3 + t \, \log 5 \leq \log W. $$ Using the lower left rule, the number of solutions with $r,s,t \geq 0$ integers is well approximated by the volume of the simplex being described over the reals, that being $$ \frac{1}{3!} \frac{\log W}{\log 2} \frac{\log W}{\log 3} \frac{\log W}{\log 5} $$

Meanwhile, if $P$ is a primorial with largest prime factor $p,$ the Prime Number Theorem, in the version with Chebyshev's first function, says $$ \log P \approx p. $$

Other than that, specific estimates for the most useful things in Rosser and Schoenfeld (1962). Two books with lots of estimates are HANDBOOK which actually has two volumes, and ALGORITHMIC, just the one volume as far as I know. And there is always Hardy and Wright, which has the advantage of explaining things.

Tutorial: the lower left rule, no consistent name, is just the idea that, in the $x,y$ plane for example, we can identify a lattice square of side one with the (integer) $(x,y)$ point in its lower left corner. So, to approximate the number of such integer lattice points in some finite body, a calculation of the area of the body is a good guess; furthermore, with extra care, strict lower and upper bounds for the count can be constructed. The best known example is probably to estimate the number of integer pairs $(x,y)$ such that $x^2 + y^2 \leq A.$ A good estimate is $\pi A^2,$ the area of the disk.