3
$\begingroup$

I want to know if it is possible to find a formula that gives all the prime numbers? or can one find the distribution of prime numbers?

I know that there is a set of ongoing research on prime numbers. I know that there is already lot of results in prime numbers, the gap between primes, a lot of theorems starting from Euclid's one. My question is simple: Is it possible for someone to find explicit formula that gives all prime numbers (explicit function $f(x)$ is a prime for any natural number $x$)? or that gives the distribution of them? If it is not possible. Suppose that someone prove that factoring is an easy problem. Still not possible?

I mean, is there a theorem, logic, something that says that it is impossible to get all the primes or that all primes can be calculated based on condition $1$, $2$, $\dotsc$?

I hope that I make my question clear. I hope that it is a valid question.

Thank you very much for your help. Any reference or ideas would be appreciated.

$\endgroup$
0

4 Answers 4

Reset to default
8
$\begingroup$

There are explicit formulas for the $n$-th prime... but they are useless. See Prime Formulas in MathWorld.

$\endgroup$
2
  • 1
    $\begingroup$ I do not understand why useless? $\endgroup$
    – zighalo
    Apr 5, 2014 at 22:42
  • 3
    $\begingroup$ Try to use some... $\endgroup$
    – Martín-Blas Pérez Pinilla
    Apr 5, 2014 at 22:47
3
$\begingroup$

We know that if $B$ is an infinite set, but countable, and $A \subseteq B$ is also infinite, then $A$ is also countable.

We know that if two sets have the same cardinality, then there is an ismorphism between them, meaning there is a function that is both injective and surjective between the 2 sets.

Euclid's proof has shown that there are infinite amount of primes. since the primes are a subset of the natural numbers, and $card(\mathbb N) =\aleph_0$, we know that if $P$ is the set of all prime numbers, $card(P)=\aleph_0$.

Combining these 2 statements give us that there is a bijective function from the natural numbers to the primes.

So theoretically, yes, there is such a function that gets a natural number $k$ and will give you the $k-th$ prime.

However, such a function was not yet found...

$\endgroup$
3
  • 1
    $\begingroup$ See my answer and the comment by Amzoti... $\endgroup$
    – Martín-Blas Pérez Pinilla
    Apr 5, 2014 at 22:49
  • $\begingroup$ I guess you have just defined that function, i.e. the function $\mathbb{N}\rightarrow P$ that associates $n$ with the $n$-th prime. $\endgroup$
    – marco trevi
    Nov 30, 2015 at 7:19
  • $\begingroup$ A function that is both injective and surjective is just a bijection. Isomorphisms are not in the agenda with unstructured sets. $\endgroup$
    – user1007416
    Aug 8, 2022 at 6:42
0
$\begingroup$

An algebraic formula resolving to the (n+1)th Prime number was first discovered by A.Venugopalan in the year 1983. This formula among other formulas were published in the Proceedings of the Indian Academy of Sciences(Math. Sci.), Vol.92, No.1, September 1983 pp 49-52. The formula is shown below:

$$P_{n + 1}^2{\rm{ = 1 + }}\left| {{\rm{ }} - {{\log }_X}\left( {\raise.5ex\hbox{$\scriptstyle 1$}\kern-.1em/ \kern-.15em\lower.25ex\hbox{$\scriptstyle 2$} {\rm{ }}\sum\limits_{{a_1} = 1}^{{p_1} - 1} {...\sum\limits_{{a_n} - 1}^{{p_n} - 1} {\sum\limits_{b = 1}^n {{X^{ - {{\left( {\sum\nolimits_1^n {{a_i}{Q_i} - bQ} } \right)}^2}}}} } } - {\rm{ 1/X }}} \right)} \right| % MathType!MTEF!2!1!+- % feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0dg9Lq-Fc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaaDa % aaleaacaWGUbGaey4kaSIaaGymaaqaaiaaikdaaaGccaqGGaGaaeyp % aiaabccacaqGXaGaaeiiaiaabUcajqgaacGaaeiiaOWaaqWaaKazaa % sabaGaaeiiaiabgkHiTiGacYgacaGGVbGaai4zaOWaaSbaaKazbaka % baGaamiwaaqcbaAabaGcdaqadaqcKbaWaeaajqgaaeaeaaaaaaaaa8 % qacaGG9cGaaeiiaOWaaabCaeaacaGGUaGaaiOlaiaac6cadaaeWbqa % amaaqahabaGaamiwamaaCaaaleqabaGaeyOeI0YaaeWaaeaadaaeWa % qaaiaadggadaWgaaadbaGaamyAaaqabaWccaWGrbWaaSbaaWqaaiaa % dMgaaeqaaSGaeyOeI0IaamOyaiaadgfaaWqaaiaaigdaaeaacaWGUb % aaoiabggHiLdaaliaawIcacaGLPaaadaahaaadbeqaaiaaikdaaaaa % aaWcbaGaamOyaiabg2da9iaaigdaaeaacaWGUbaaniabggHiLdaale % aacaWGHbWaaSbaaWqaaiaad6gaaeqaaSGaeyOeI0IaaGymaaqaaiaa % dchadaWgaaadbaGaamOBaaqabaWccqGHsislcaaIXaaaniabggHiLd % aaleaacaWGHbWaaSbaaWqaaiaaigdaaeqaaSGaeyypa0JaaGymaaqa % aiaadchadaWgaaadbaGaaGymaaqabaWccqGHsislcaaIXaaaniabgg % HiLdqcKbaWa8aacqGHsislcaqGGaGccaqGXaGaae4laiaabIfajaa4 % peGaaeiiaaGcpaGaayjkaiaawMcaaaqcKbaaciaawEa7caGLiWoaaa % a!8140! $$

$\endgroup$
1
  • $\begingroup$ What should $X$ be? $\endgroup$
    – Daniel Donnelly
    Oct 17, 2017 at 3:38
0
$\begingroup$

Asymptotically, the probability of prime is $1/\log(n)$. As n increases, a random integer n becomes less and less likely to be a prime.

Intuitively, in approximate terms, $1/2$ of numbers are eliminated as multiples of $2$; $1/3$ eliminated as multiples of $3$; $1/4$ eliminated as multiples of $4$... So the probability is $(1-1/2) * (1-1/3) * (1-1/4) * (1-1/5)$... for any prime less than $n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .