mersenneforum.org yet another 'proof' of the legendary conjecture
 Register FAQ Search Today's Posts Mark Forums Read

2017-12-31, 15:39   #56
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 Originally Posted by guptadeva step 1 implies the knowledge of all prime numbers <= sqr(x)
That was not a condition given.

2017-12-31, 15:40   #57
CRGreathouse

Aug 2006

3·1,993 Posts

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!

2017-12-31, 15:55   #58

Dec 2017

2×52 Posts

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.

Last fiddled with by guptadeva on 2017-12-31 at 16:04 Reason: including legendre algorithm

2017-12-31, 16:03   #59
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

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 jn
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

Last fiddled with by science_man_88 on 2017-12-31 at 16:11 Reason: Correcting typo/ fixed error in memory

2017-12-31, 16:28   #60

Dec 2017

2×52 Posts

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

 2017-12-31, 18:18 #61 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 32×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 628 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×52 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
2018-01-01, 03:56   #64

Dec 2017

1100102 Posts

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

2018-01-02, 07:44   #65
CRGreathouse

Aug 2006

3×1,993 Posts

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.

2018-01-02, 07:57   #66
George M

Dec 2017

628 Posts

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 :)))

Last fiddled with by George M on 2018-01-02 at 08:03

 Similar Threads Thread Thread Starter Forum Replies Last Post R.D. Silverman Math 6 2019-04-22 00:03 Steve One Miscellaneous Math 21 2018-03-08 08:18 Arxenar Miscellaneous Math 1 2013-09-07 09:59 Carl Fischbach Miscellaneous Math 7 2009-06-24 05:52 vector Miscellaneous Math 5 2007-12-01 14:43

All times are UTC. The time now is 08:27.

Thu May 26 08:27:47 UTC 2022 up 42 days, 6:29, 0 users, load averages: 1.13, 1.27, 1.37