yet another 'proof' of the legendary conjecture - Page 6

science_man_88 · 2017-12-31, 15:39

Quote:

Originally Posted by guptadeva

step 1 implies the knowledge of all prime numbers <= sqr(x)

That was not a condition given.

CRGreathouse · 2017-12-31, 15:40

Quote:

Originally Posted by guptadeva

are there some known (exact) primality tests for a number n requiring less than pi(n) steps other using a lookup table or wilsons theorem[B]?

Trial division would be one example. pi(101) = 26, for example, but it suffices to check for divisors up to 10.

Quote:

Originally Posted by guptadeva

and yes, of cause i take my words back that the aks-test is a sieve in disgiuse

You’re learning!

guptadeva · 2017-12-31, 15:55

Quote:

Originally Posted by science_man_88

That was not a condition given.

yes ... true - the original question was just the beginning and i am grateful for your mentioning the primorial function.

so let me continue with

do you know a formula for p(i) not including all p(j) with j<i ?

i would also be equally happy if you could come up with a formula for p(i) not including all p(k) witk k>n

legendre came up with a "quick" algorithm as to how to find p(i+1) knowing p(i) ... but, that's not what i ask.

science_man_88 · 2017-12-31, 16:03

Quote:

Originally Posted by guptadeva

yes ... true - the original question was just the beginning and i am grateful for your mentioning the primorial function.

so let me continue with

do you know a formula for p(i) not including all p(j) with j<i ?

i would also be equally happy if you could come up with a formula for p(i) not including all p(k) witk k>n

I believe I remember hearing about a degree 25 rational polynomial whose outputs were exactly the primes...http://mathworld.wolfram.com/Prime-G...olynomial.html

guptadeva · 2017-12-31, 16:28

Quote:

Originally Posted by science_man_88

I believe I remember hearing about a degree 25 rational polynomial whose outputs were exactly the primes...http://mathworld.wolfram.com/Prime-G...olynomial.html

yes, i remember the short original paper by jones just stating his polynomial without proof assuming that everbody can see that all quadratic terms must be 0 and that the terms represent a set of diophantine equations that have been known to number-theorists at that time

one of his following joint papers with sato, wada and wiens is more understandable and very insightful

https://www.maa.org/sites/default/fi...oWadaWiens.pdf

danaj · 2017-12-31, 18:18

For primality:

For 64-bit numbers, e.g. numbers less than 18446744073709551616, the BPSW test is deterministic and unconditionally correct. There are about 3 * log_2(n) steps, often less. It takes less than 200 steps (typically about 125) to give a correct answer for a 64-bit prime. Pi(n) is on the order of 400,000,000,000,000,000.

As I said a couple times, some tests meeting your requirements:

* AKS

* APR-CL

* ECPP

No lookup tables, no use of O(sqrt(n)) primes, results faster than trial division.

These aren't "simple formulas" but that's what we have.

It seems we've moved on to the ubiqutous "formula for nth prime" discussion. We have algorithms that are quite fast. See, for example:

https://math.stackexchange.com/a/961539/117584

https://math.stackexchange.com/a/775314/117584

People sometimes get upset that this isn't a "formula" or simple enough. Oh well.

guptadeva · 2017-12-31, 21:51

somehow i just stumbled upon another old paper by jones:
https://cms.math.ca/openaccess/cmb/v....0433-0434.pdf
containing a simple formula for p(n) proved on the base of wilsons theorem and bertrands postulate ... so i'm happy now

guptadeva · 2018-01-01, 03:45

and even more happy after having found:
https://oeis.org/wiki/Formulas_for_primes

yet the answer to the question if all p(j) with j<i are necessary to determine p(i) is probably: "we don't know" ?

guptadeva · 2018-01-01, 03:56

Quote:

Originally Posted by danaj

As I said a couple times, some tests meeting your requirements:

* AKS
* APR-CL
* ECPP

No lookup tables, no use of O(sqrt(n)) primes, results faster than trial division.

These aren't "simple formulas" but that's what we have.

i will certainly look more deeply into these tests - some ecpp variants look promising

CRGreathouse · 2018-01-02, 07:44

Quote:

Originally Posted by guptadeva

and even more happy after having found:
https://oeis.org/wiki/Formulas_for_primes

I wrote that page.

I'm working on a survey paper and that was my first cut.

George M · 2018-01-02, 07:57

Quote:

Originally Posted by CRGreathouse

I wrote that page.

I'm working on a survey paper and that was my first cut.

Apparently the Prime Gap Equation is an Equation that determines the following prime number from the (n + 1)st prime number.

$p_{n + 1} \ = \{2 \ + \ \sum_{k = 1}^n(p_{k + 1} \ - \ p_k) \ : \ p_m \ = \ m^{th} \ prime \ number\}$

I came across this on a Wikipedia Article an am trying to find a proof, but nonetheless, if this equation has its own article, then there must be a way of demonstrating the truth of this equation.

If this is true, then there is another equation for prime numbers, but this looks like it was derived from the Almansa and Prieto formulas, or the Willans Formula (in particular, the reduced version from Neill and Singer). But overall, nice job :)))

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Claimed proof of the ABC conjecture (Zha, 2009)	R.D. Silverman	Math	6	2019-04-22 00:03
Collatz Conjecture Proof	Steve One	Miscellaneous Math	21	2018-03-08 08:18
The Beal Conjecture Proof	Arxenar	Miscellaneous Math	1	2013-09-07 09:59
A proof for the Twin Prime Conjecture	Carl Fischbach	Miscellaneous Math	7	2009-06-24 05:52
Proof of Goldbach Conjecture	vector	Miscellaneous Math	5	2007-12-01 14:43

2017-12-31, 18:18	#61
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 3²×101 Posts	For primality: For 64-bit numbers, e.g. numbers less than 18446744073709551616, the BPSW test is deterministic and unconditionally correct. There are about 3 * log_2(n) steps, often less. It takes less than 200 steps (typically about 125) to give a correct answer for a 64-bit prime. Pi(n) is on the order of 400,000,000,000,000,000. As I said a couple times, some tests meeting your requirements: * AKS * APR-CL * ECPP No lookup tables, no use of O(sqrt(n)) primes, results faster than trial division. These aren't "simple formulas" but that's what we have. It seems we've moved on to the ubiqutous "formula for nth prime" discussion. We have algorithms that are quite fast. See, for example: https://math.stackexchange.com/a/961539/117584 https://math.stackexchange.com/a/775314/117584 People sometimes get upset that this isn't a "formula" or simple enough. Oh well.

2017-12-31, 21:51	#62
guptadeva Dec 2017 62₈ Posts	somehow i just stumbled upon another old paper by jones: https://cms.math.ca/openaccess/cmb/v....0433-0434.pdf containing a simple formula for p(n) proved on the base of wilsons theorem and bertrands postulate ... so i'm happy now

2018-01-01, 03:45	#63
guptadeva Dec 2017 2×5² Posts	and even more happy after having found: https://oeis.org/wiki/Formulas_for_primes yet the answer to the question if all p(j) with j<i are necessary to determine p(i) is probably: "we don't know" ?