[Math] The number of distinct prime factors of $n\in\mathbb N$

factorizationnt.number-theoryprime numbers

Let $\omega(n)$ be the number of distinct prime factors of a natural number $n$.

Note that $\omega(n)=0\iff n=1$, and that $\omega(24)=\omega(2^3\cdot 3^1)=2\ (\not = 4)$.

(For more details, you can see "Distinct Prime Factors" on wolfram math world)

Then, for $m\in\mathbb N$, let $S_m=\{n|n\in\mathbb N, \omega(n)=m\}$. Also, Let $N_m(x)$ be the counting function that gives the number of the elements of $S_m$ less than or equal to $x$, for any real number $x$. See the line graph below. This graph shows $N_m(x)\ (m=1,2,3,4)$ in $1\lt x\le 2309=2\cdot3\cdot5\cdot7\cdot11-1.$ Note that $N_m(2309)=0$ for $m\ge 5$, and that $\omega(2310)=\omega(2\cdot 3\cdot 5\cdot 7\cdot 11)=5$.

$\ \ \ \ \ \ \ \ \ \ $ enter image description here

In addition to this, let $P_m(x)=\frac{N_m(x)}{x}\times 100$. See the line graph below. This graph shows $P_m(x)\ (m=1,2,3,4)$ in $1\lt x\le 2309=2\cdot3\cdot5\cdot7\cdot11-1.$

$\ \ \ \ \ \ \ \ \ \ $ enter image description here

Then, here are my questions.

Question : Are the followings true?

$(1)$ For every $m\in\mathbb N$, $N_m(x)=O(x)\ (x\to\infty)$.

$(2)$ For every $m\in\mathbb N$, $\lim_{x\to\infty} P_m(x)=0$.

$(3)$ If $x\ge 50$, then $P_2(x)\gt P_m(x)$ for every $m\ge 3$.

The above graphs led me to the these conjectures, but I don't have any good ideas. I would like to know any relevant references. Can anyone help?

Best Answer

I don't quite understand question (1). Isn't $N_m(x) \leq x$ trivially? You seem to be interested in fixed $m$. Then an affirmative answer to (2) and a negative answer to (3) follows from a classical extension of the prime number theorem due to Landau. See, for example,

http://www2.imperial.ac.uk/~bin06/M34PM16-Analytic-Number-Theory/m3pm16div.pdf

In fact, the answer to (2) is "yes, uniformly in $m$." Indeed, a theorem of Hardy and Ramanujan implies that $N_m(x) \ll x/\sqrt{\log\log{x}}$ uniformly in $m$.

Related Solutions

[Math] Happy New Prime Year!

You missed the excitement of 1998, with $1999=1999, 2000=2^4 \cdot 5^3, 2001=3 \cdot 23 \cdot 29,$ and $2002=2 \cdot 7 \cdot 11 \cdot 13$

A quick set of thoughts, too long to fit in a comment:

this requires finding a "prime gap" of length $k-1$, since $s(n+1)=1$ means ~~that $n+1$ is prime~~ that $n+1$ is either prime or a power of a prime, but the next $k-1$ digits are composite since s(n+x)>1 for $2 \le x \le k$. This also means that $s(n+2)=2$ only because $s(n+2)$ is even, thus $2$ is one of the factors and implies that $(n+2)/2$ is prime (or that $(n+2)/2^j$ is prime for some $j \in \mathbb{Z}$), since $n+2$ only has two factors and one of them is $2$ (or $2^j$).

For $s(n+k)$ to have $k$ distinct prime factors means that it has to be at minimum a product of the first $k$ prime numbers, while it definitely has to be a multiple of the product of $k$ prime numbers. So the two key restrictions are that s(n+k) is $k$-composite (has $k$ prime factors) and that both (n+1) and (n+2)/2 are prime numbers.

Hmm, I thought something about the fact that either s(n+2) or s(n+4) would be divisible by $4$ while the other would be divisible by $2$ but not by $4$ would play some role in this.

Here are some quick results from running "bash", "factor", and "sed" and "awk" at the command line:

If you want an ascending run of 1,2, and 3 prime factors, the smallest example starts at $n=63$, with $64=2^6, 65=5 \cdot 13, 66=2 \cdot 3 \cdot 11$

If you want an ascending run of 1,2,3, and 4 prime factors, we already missed the exciting years of $n=1866$ and $n=1998$

1867: 1867
1868: 2 2 467
1869: 3 7 89
1870: 2 5 11 17

1999: 1999
2000: 2 2 2 2 5 5 5
2001: 3 23 29
2002: 2 7 11 13

And the next few years with ascending runs of 1,2,3, and 4 prime factors will start after the years 3216, 4056, and 4176 with 3217, 4057, and 4177 as prime years. Unfortunately, these computational results are not giving me the germ of any shortcut or understanding. There are also some descending sequences in terms of the number of prime factors, and their placement also does not help.

If you want an ascending run of 1,2,3,4, and 5 prime factors, we have to wait almost half-a-million years to get to the exciting years of $n=491850$ and $n=521880$ for $k=5$

491851: 491851
491852: 2 2 122963
491853: 3 19 8629
491854: 2 11 79 283
491855: 5 7 13 23 47

521881: 521881
521882: 2 260941
521883: 3 3 3 3 17 379
521884: 2 2 11 29 409
521885: 5 7 13 31 37

Now with four numbers computed and found, I searched the OEIS and found the corresponding sequence. Since the Online Encyclopedia already has this sequence, I'm hanging up my computational hat and heading off to work. :)

http://oeis.org/A086560

Start of first run of n successive numbers in which i-th number has exactly i distinct prime divisors for i = 1..n
2, 5, 64, 1867, 491851, 17681491, 35565206671
J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 64, p. 23, Ellipses, Paris 2008.

Explicit Expression for Chebyshev Polynomials Modulo xr-1 – Number Theory

There's a rapid algorithm to compute $T_n(x)$ modulo $(n,x^r-1)$. Note that $$ \pmatrix{T_n(x) \\ T_{n-1}(x)} = \pmatrix { 2x & -1 \\ 1&0} \pmatrix{T_{n-1}(x) \\ T_{n-2}(x)} = \pmatrix { 2x & -1 \\ 1&0}^{n-1} \pmatrix{ x\\ 1}. $$ Now you can compute these matrix powers all modulo $(n, x^{r}-1)$ rapidly by repeated squaring. Clearly $O(\log n)$ multiplications (of $2\times 2$ matrices) are required, and the matrices have entries that are polynomials of degree at most $r$ and coefficients bounded by $n$. So the complexity is a polynomial in $r$ and $\log n$.

Best Answer

Related Solutions

[Math] Happy New Prime Year!

Explicit Expression for Chebyshev Polynomials Modulo xr-1 – Number Theory

Related Question