3
$\begingroup$

Number of prime before a sufficiently large $N$ equals to $\frac{N}{\log(N)}$.

Is there a way to prove it by prime factorizations?

Suppose $N$, and all the primes $\{p_1,p_2,...,p_j\}$, thus all the number below $N$ was of the form $r=p_1^{\alpha_1} p_2 ^{\alpha_1} ...p_j^{\alpha_j}$.

Computationally speaking, we know that if we took $\log_{10}(r)$ we could get the "digits" of the number $r$ under $N$. Therefore, suppose $N=10^{10}$, we could easily compute all the unique "permutation/tuple" of those prime number whose bijective $r_l$ had value under $N$. Say we have $q$ of those permutations whose bijective values smaller or equal to $N$. Then we know for sure that $N=q+1$(or if we justify 1 as the 0 tuple), otherwise we know there was some prime number missing from the set.

Since this is a computational result, it must be true for all $N$ of order $10^k$.(If we let $log_{10}(r_i)$ compute more digits, it would be true for all $N$.) Thus such relation must hold for all $N$. (Think if we had a table of holes with primes as index, and we use those permutation/tuple to fill out the holes(the missing numbers), until we couldn't. Then we must have obtained a new prime.)

Notice the interesting part about this question:

First: the program itself is highly efficient: if we save every integer it generated as tuple $X(r)=r$ and make the iteration with respect $N$ itself, then we generate the nature number exactly once. There is no "deviation" towards the number, or any other logical statement except comparing the size of the number, and count the order of the set we had already generated.

Second: Although it calculated out all the non-primes. Notice the existence and generating of the prime was independent of calculation. We simply count the size of the generated sets below $N$. If it's $N-1$, then $N$ was a prime. Thus if we would effectively obtain the prime generating function if we can prove it through prime factorization.

$\endgroup$
  • 6
    $\begingroup$ This is the Prime Number Theorem. If you can prove it by this sort of elementary consideration, fame beckons! $\endgroup$ – Lord Shark the Unknown Oct 6 '17 at 17:35
  • $\begingroup$ With elementary arguments, you can't prove the PNT, but you can find some heuristics justifying why we want $\sum_{p \le x} 1 \sim \frac{x}{\log x}$ (the heuristic is to assume a random model for the prime numbers where $X_n = 1_{n \text{ is prime }}$ is a sequence of independent random variables) $\endgroup$ – reuns Oct 6 '17 at 17:38
  • $\begingroup$ I wouldn't say "equals to..." First, the right hand side isn't an integer. $\endgroup$ – Thomas Andrews Oct 6 '17 at 17:40
  • $\begingroup$ @reuns not "you can't" just has not been done $\endgroup$ – qbert Oct 6 '17 at 17:42
  • $\begingroup$ If I were to look for a simple proof, I'd try to use that the harmonic mean of $1,2,\dots,n$ $\sim\frac{n}{\log n}$. $\endgroup$ – Thomas Andrews Oct 6 '17 at 17:50

Your Answer

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