mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-12-31, 15:39   #56
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by guptadeva View Post
step 1 implies the knowledge of all prime numbers <= sqr(x)
That was not a condition given.
science_man_88 is offline   Reply With Quote
Old 2017-12-31, 15:40   #57
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by guptadeva View Post
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 View Post
and yes, of cause i take my words back that the aks-test is a sieve in disgiuse
You’re learning!
CRGreathouse is offline   Reply With Quote
Old 2017-12-31, 15:55   #58
guptadeva
 
Dec 2017

3216 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
guptadeva is offline   Reply With Quote
Old 2017-12-31, 16:03   #59
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by guptadeva View Post
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

Last fiddled with by science_man_88 on 2017-12-31 at 16:11 Reason: Correcting typo/ fixed error in memory
science_man_88 is offline   Reply With Quote
Old 2017-12-31, 16:28   #60
guptadeva
 
Dec 2017

2·52 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
guptadeva is offline   Reply With Quote
Old 2017-12-31, 18:18   #61
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

32×101 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2017-12-31, 21:51   #62
guptadeva
 
Dec 2017

3216 Posts
Lightbulb

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 is offline   Reply With Quote
Old 2018-01-01, 03:45   #63
guptadeva
 
Dec 2017

2·52 Posts
Default

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 is offline   Reply With Quote
Old 2018-01-01, 03:56   #64
guptadeva
 
Dec 2017

2×52 Posts
Default

Quote:
Originally Posted by danaj View Post
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
guptadeva is offline   Reply With Quote
Old 2018-01-02, 07:44   #65
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by guptadeva View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2018-01-02, 07:57   #66
George M
 
Dec 2017

2×52 Posts
Post

Quote:
Originally Posted by CRGreathouse View Post
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
George M is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 19:06.


Fri May 27 19:06:31 UTC 2022 up 43 days, 17:07, 0 users, load averages: 1.67, 1.77, 1.75

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔