# Given the primes, how many numbers are there?

I have a concrete question and a more abstract version of the same. There are lots of theorems that take information on the number of elements and translate it to information on the primes; I’m looking to go the other way.

Abstract: I have an arithmetic semigroup generated by a collection of “primes” which have a known distribution function. What information do I need (e.g., about the small primes) to find the number of elements with norm at most $$x$$, and what is this?

Concrete: The primes are the odd primes $$p$$ of the natural numbers, and their valuations are $$|p| = p/2$$. Hence there are $$\sim 2x/\log x$$ primes up to $$x$$. How many elements are there up to $$x$$?

• Aren't you just counting odd numbers, then? Commented Jul 17 at 23:03
• @QiaochuYuan No, because the valuations are different. 27 < 15. Commented Jul 18 at 0:04
• It is hard to figure what you mean there are lots of theorems for. Can you give us examples? Commented Jul 18 at 0:14
• Also, "the primes are the odd primes..." It is entirely unclear what you mean by that. What do you mean by the word "valuation?" Commented Jul 18 at 0:17
• @Charles If you're going to make this distinction between a prime/element and its valuation, then you'll need to be more specific about your counting functions. Are you counting primes up to $x$, or primes whose valuations go up to $x$? elements up to $x$, or elements whose valuations go up to $x$? Is an element a product of primes or a product of valuations? If the former, is the valuation of a product of primes equal to the product of the valuations of the primes? Commented Jul 18 at 3:22

To state the question more clearly, we are interested in $$\#\{ n\in\Bbb N,\, n\text{ odd}\colon n/2^{\Omega(n)} \le x\}$$ where $$\Omega(n)$$ is the number of prime factors of $$n$$ counted with multiplicity. There is probably a standard method for attacking this type of problem directly (compare for example to classical results for $$\#\{n\colon \phi(n)\le x\}$$). But to orient ourselves, we can proceed by writing $$\#\{ n\in\Bbb N,\, n\text{ odd}\colon n/2^{\Omega(n)} \le x\} = 1 + \sum_{w=1}^\infty \#\{ n\in\Bbb N,\, n\text{ odd}\colon \Omega(n) = w,\, n \le 2^wx \}.$$ Without the restriction to $$n$$ odd, this simply references the classical Selberg–Sathe result $$\#\{ n\le y\colon \Omega(n)=w\} \sim G\biggl( \frac{w-1}{\log\log y} \biggr) \frac{y(\log\log y)^{w-1}}{(w-1)!\log y}$$ where $$G(z) = \frac1{\Gamma(z+1)} \prod_p \biggl( 1-\frac zp\biggr)^{-1} \biggl( 1-\frac1p \biggr)^z.$$ We would then get a sum like $$\sum_{w=1}^\infty G\biggl( \frac{w-1}{\log\log y} \biggr) \frac{2^wx(\log\log x)^{w-1}}{(w-1)!\log x}$$ (in practice $$\log(2^wx)$$ is close enough to $$\log x$$) which could be analyzed by standard means; indeed, the maximal summand occurs near $$w\approx 2\log\log x$$, in a region where the $$G()$$ value is basically constant, and we'd simply get the series for $$\approx G(2) \frac x{\log x} e^{2\log\log x} \approx G(2) x\log x$$.
I recommend going to a treatment of the Selberg–Sathe result (Montgomery & Vaughan Section 7.4, or Tenenbaum Chapter 2 Section 6.1) and modifying the method to restrict to odd numbers. One should be able to get an asymptotic formula of size $$x\log x$$, with the right leading constant even. [Technical note: the Selberg–Sathe result only holds as stated uniformly for $$w\le(2-\delta)\log\log x$$, which is just short of what we need. However, when restricted to odd integers, the range of uniformity will extend to $$w\le(3-\delta)\log\log x$$.]