yet another 'proof' of the legendary conjecture
 

[URL]http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.310.4396&rep=rep1&type=pdf[/URL]

the common denominator of many recent 'proofs' floating around on the internet seem to be an inadequate use of the english language ... but ok, let the doubt be in favor of the 'accused' :unsure:

the pdf cited above becomes slightly more readable when substituting the word [B]'term' [/B]or [B]'expression' [/B]instead of the word [B]'equation'

[/B]other 'proofs' are either cyclic (the author assumes the validity of the conjecture in order to prove the conjecture) or simply blurred by chaotic or unrelated sets of equations.

however ... it is always interesting to see which tools or ideas are being presented in these 'proofs' - and since probably nobody today is honestly doubting the validity of the conjecture itself (?) it would be nice to have a real proof someday !

so ... what's the catch here ?

The first mistake I see is in (4) on page 2. floor((n+1)^2/m) - floor(n^2/m) is indeed at least floor((2n+1)/m), but that doesn't mean you can make the substitution -- you need to majorize/round *up* on terms you're subtracting (and minorize/round down on terms you're adding) if you want to prove a lower bound. Otherwise, just note that floor((n+1)^2/m) - floor(n^2/m) >= 0 and "conclude" that (3) is at least 2n+1.

This is a major, fundamental mistake at the heart of the proof, so it certainly doesn't hold.

[QUOTE]This is a major, fundamental mistake at the heart of the proof, so it certainly doesn't hold.[/QUOTE]exactly :smile:

somehow it's also good to see that the number of correct and insightful papers on this subject is > 0 like e.g. in the following example:

[URL]https://arxiv.org/pdf/1310.1323.pdf[/URL]

[QUOTE=guptadeva;475067]exactly :smile:

somehow it's also good to see that the number of correct and insightful papers on this subject is > 0 like e.g. in the following example:

[URL]https://arxiv.org/pdf/1310.1323.pdf[/URL][/QUOTE]

Many things can be interconnected. The twin prime conjecture, can be a statement about goldbach partitions. Goldbach's conjecture, restated as an equidistance conjecture on most of the natural number line.

[QUOTE=guptadeva;475067]exactly :smile:

somehow it's also good to see that the number of correct and insightful papers on this subject is > 0 like e.g. in the following example:

[URL]https://arxiv.org/pdf/1310.1323.pdf[/URL][/QUOTE]

The result in Remark 1 on Conjecture 1 (p. 3) could be improved using work carried out on this forum. :smile:

ok ... yet another fresh and original one:

[URL]https://justmathstuff.wordpress.com/2017/12/06/abridged-version-of-accommodation-with-proofs-of-legendres-brocards-and-andricas-conjectures/[/URL]

the author uses pi(x) to mean the conventinal pi(x)-1 not counting 2 as a prime

some statements are not correct as e.g. in the case x=4:

the pattern 3 a b 3 leading to the conclusion that 3 primes are needed to 'accomodate' a target set of four elements is wrong.

counter-example: the target set 11 13 15 17 needs 4 primes (11,13,3,17) to be 'accomodated'

hence without additional combinatorical arguments, the lemma and the main result are not proven ...

also the statement of the idea: 'each new prime discovered by the sieve is nothing more than the next number that the number 3 failed to accommodate' ... would lead to 35 being prime number :cry:

[QUOTE=guptadeva;475097]ok ... yet another fresh and original one:

[URL]https://justmathstuff.wordpress.com/2017/12/06/abridged-version-of-accommodation-with-proofs-of-legendres-brocards-and-andricas-conjectures/[/URL]

the author uses pi(x) to mean the conventinal pi(x)-1 not counting 2 as a prime

some statements are not correct as e.g. in the case x=4:

the pattern 3 a b 3 leading to the conclusion that 3 primes are needed to 'accomodate' a target set of four elements is wrong.

counter-example: the target set 11 13 15 17 needs 4 primes (11,13,3,17) to be 'accomodated'

hence without additional combinatorical arguments, the lemma and the main result are not proven ...

also the statement of the idea: 'each new prime discovered by the sieve is nothing more than the next number that the number 3 failed to accommodate' ... would lead to 35 being prime number :cry:[/QUOTE]

Ah, but for 4 consecutive natural numbers it is true it only takes 3 apply the pigeonhole principle. Okay it relies on positioning properly.

[QUOTE=science_man_88;475115]Okay it relies on positioning properly.[/QUOTE]

as much as i like the idea of counting the number of times some multiples of each prime p[SUB]i[/SUB] with i<=pi(n) falls into the interval [(n-1)^2 , n^2] - in order to actually give a proof of the legendre conjecture there is still an 'epsilon' missing in the argument ... any ideas how to fill the gap ?

[QUOTE=guptadeva;475097]ok ... yet another fresh and original one:

[URL]https://justmathstuff.wordpress.com/2017/12/06/abridged-version-of-accommodation-with-proofs-of-legendres-brocards-and-andricas-conjectures/[/URL]

the author uses pi(x) to mean the conventinal pi(x)-1 not counting 2 as a prime

some statements are not correct as e.g. in the case x=4:

the pattern 3 a b 3 leading to the conclusion that 3 primes are needed to 'accomodate' a target set of four elements is wrong.

counter-example: the target set 11 13 15 17 needs 4 primes (11,13,3,17) to be 'accomodated'

hence without additional combinatorical arguments, the lemma and the main result are not proven ...

also the statement of the idea: 'each new prime discovered by the sieve is nothing more than the next number that the number 3 failed to accommodate' ... would lead to 35 being prime number :cry:[/QUOTE]

Hello,

I noticed that you're citing my work...but coming to faulty conclusions. Your alleged "counter-example" is not a counter-example of my proof at all. The LEAST number of primes needed to accommodate a target set of four elements is indeed pi(4)+2=3. This is what my proof is concerned with: it answers the question regarding the LEAST number of primes needed. It is possible to find a set of four consecutive odd numbers requiring MORE than 3 primes to accommodate. Indeed, you found such a set with 11 13 15 17. Yet you will never find a set of four consecutive odd numbers that can be accommodated with LESS than 3 primes. Get it?

As for your statement on my discussion regarding the sieve, (a) it has nothing to do with my proof, as my discussion on the sieve was simply providing some background on the history of prime numbers; and (b) I feel you're being a bit too nitpicky. Obviously, what I was saying is that the FIRST odd number not captured by the sieve after running it with 3 (i.e. 5) becomes our next prime, and 5 then becomes the next number we use to run the sieve, etc. We all know how the sieve works. It's elementary. Attempting to use my short background discussion on it in an effort to discredit the remainder of my work is not productive.

Okay, that's the end of my rant. At the end of the day, I am THRILLED people are actually thinking about my work, and I am more than happy to address any questions, comments, concerns, etc. you have regarding my proofs of Legendre's, Brocard's, and Andrica's, as I am certain that my proofs are correct. I love math, I don't bite, and I'm a lawyer, so I believe my grasp of the English language is more than adequate.

Let's discuss!

Cheers,

Rob Taylor, Esq.

[QUOTE=robtaylor501;475249]I love math, I don't bite, and I'm a lawyer, so I believe my grasp of the English language is more than adequate.

Let's discuss![/QUOTE]

Let's.

Do you prefer to code in C, C++, Perl, Python, PHP, Go or C#?

[QUOTE=chalsall;475262]Let's.

Do you prefer to code in C, C++, Perl, Python, PHP, Go or C#?[/QUOTE]

That assumes I know how to code. I don't. :smile:

[QUOTE=robtaylor501;475249][U]We all know[/U] how the sieve works. It's elementary. [/QUOTE]
Alleged certainty is a fallacy. Don't expect us to do your proof or parts of it. Onus probandi.

[QUOTE=Batalov;475270]Alleged certainty is a fallacy. Don't expect us to do your proof or parts of it. Onus probandi.[/QUOTE]

The sieve of Eratosthenes is not an "alleged certainty"...it is a simple, ancient algorithm several 1000 years old, and not something I developed. It has nothing to do with any proof of mine or part of it. It was in my blog as background commentary leading up to my proof. Hence my prior comment.

Beyond that, I agree with your statement! I'm here to answer questions and clear up any areas of confusion, not to get others to do my work. :smile:

[QUOTE=robtaylor501;475273]The sieve of Eratosthenes is not an "alleged certainty"...it is a simple, ancient algorithm several 1000 years old, and not something I developed. It has nothing to do with any proof of mine or part of it. It was in my blog as background commentary leading up to my proof. Hence my prior comment.

Beyond that, I agree with your statement! I'm here to answer questions and clear up any areas of confusion, not to get others to do my work. :smile:[/QUOTE]

I'd say 2,200 years old...

[QUOTE=robtaylor501;475273]The sieve of Eratosthenes is not an "alleged certainty"...it is a si...[/QUOTE]
Another fallacy - replacing the subject.
What I said was '[U]We all know[/U].... bla-bla' (even underlined it for you) is an alleged certainty fallacy; such words don't belong in any proof. Avoid them.
What you switched was 'The sieve of Eratosthenes is not an "alleged certainty"'.

You must be a good lawyer! I'll give you that. Rhetoric of this kind must work like a charm on lay public.

[FONT=Courier New]happy for the opportunity to discuss directly :-)

for the sake of simpler arguments, i took the liberty
to give a different definition of 'assist' and also
merge your terms 'accomodation' and 'perfect accomodation'
but if you think that's not ok, then you should come up with
some other more adequate formal definitions:

pi(n) := the number of odd primes <= n
pi[n,m] := the number of odd primes in the interval [n,m]
= pi(m) - pi(n) ... when n is not a prime

assist[n, m] := number of distinct elements of the set
{ least prime factor p of a composite x with n <= x <= m] }

--> assist[n^2, (n+1)^2] <= pi(n+1)

set(odd,c) := { odd, odd+2, ... odd+2(c-1) }
= set of c consecutive odd numbers starting with the number odd

accomodate(odd,c) := number of distinct elements of the set
{ prime p ; p acommodates an element of set(odd,c) }
= number of distinct least prime factors of each of the
elements from set(odd,c)

now, your accomodation lemma states that
accomodate(n,c) = pi(c)+2 for c>=3 and all n

your 'proof' by induction relies *heavily* on the shape of the chosen patterns e.g.:

* * * * *
3 a b 3 5

so without any combinatorical proof as to
why your result is independent of the shape
of all possible patterns like e.g.

* * * * *
a b 3 c 5

or

* * * * * * * *
3 7 11 3 a 5 3 b ...

the proof of your lemma is not complete ...

also, as mentioned before we have
accomodate(11,4) = 4 and pi(4)+2 = 3
for the set(11,4)={11,13,15,17}

according to your opinion, is doesn't
matter as you would only need the relation
accomodate(n,c) >= pi(c)+2 for c>=3 and all n

but any other expression with '>=' would still
need a proof.

obvously the constant 2 in the above lemma is crucial for the conclusion ...
so please prove a correct relation
accomodate(n,c) >= pi(c)+x with x>0
and you will have

for odd n:
pi[n^2,(n+1)^2]
>= accomodate(n^2, n+1) - assist[n^2, (n+1)^2]
>= pi(n+1) + x - assist[n^2, (n+1)^2] ... lemma with '>='
>= pi(n+1) + x - pi(n+1)
= x

and for even n:
pi[n^2,(n+1)^2]
>= accomodate(n^2+1, n+1) - assist[n^2, (n+1)^2]
>= pi(n+1) + x - assist[n^2, (n+1)^2] ... lemma with '>='
>= pi(n+1) + x - pi(n+1)
= x[/FONT]

[QUOTE=Batalov;475302]Another fallacy - replacing the subject.
What I said was '[U]We all know[/U].... bla-bla' (even underlined it for you) is an alleged certainty fallacy; such words don't belong in any proof. Avoid them.
What you switched was 'The sieve of Eratosthenes is not an "alleged certainty"'.

You must be a good lawyer! I'll give you that. Rhetoric of this kind must work like a charm on lay public.[/QUOTE]

Ha! I see what you're saying. I think I'm starting to like it here!

[QUOTE=guptadeva;475305]happy for the opportunity to discuss directly :-)

for the sake of simpler arguments, ...[/QUOTE]

Two word come to mind [URL="https://en.m.wikipedia.org/wiki/Pigeonhole_principle"]pigeonhole priciple[/URL]

[QUOTE=robtaylor501;475249]...I am certain that my proofs are correct. [/QUOTE]

I don't come here very often, but this caught my attention. This is an incredibly bold claim, especially when many of the finest mathematicians of the last two centuries have tried to prove these conjectures without success.

Your "accommodation lemma" is false. In your notation, pi(19) = 7, so 9 primes should be needed to accommodate a set of 19 consecutive odd integers. But the 19 odd integers from 2163 to 2199 are accommodated by the 8 primes 3, 5, 7, 11, 13, 37, 41 and 2179.

guptadeva has pointed out the main issue with the proof: your induction assumes that your pattern is the only way a set can be accommodated by the required number of primes, when in fact there are other ways.

[QUOTE=guptadeva;475305][FONT=Courier New]happy for the opportunity to discuss directly :-)

for the sake of simpler arguments, i took the liberty
to give a different definition of 'assist' and also
merge your terms 'accomodation' and 'perfect accomodation'
but if you think that's not ok, then you should come up with
some other more adequate formal definitions:

pi(n) := the number of odd primes <= n
pi[n,m] := the number of odd primes in the interval [n,m]
= pi(m) - pi(n) ... when n is not a prime

assist[n, m] := number of distinct elements of the set
{ least prime factor p of a composite x with n <= x <= m] }

--> assist[n^2, (n+1)^2] <= pi(n+1)

set(odd,c) := { odd, odd+2, ... odd+2(c-1) }
= set of c consecutive odd numbers starting with the number odd

accomodate(odd,c) := number of distinct elements of the set
{ prime p ; p acommodates an element of set(odd,c) }
= number of distinct least prime factors of each of the
elements from set(odd,c)

now, your accomodation lemma states that
accomodate(n,c) = pi(c)+2 for c>=3 and all n

your 'proof' by induction relies *heavily* on the shape of the chosen patterns e.g.:

* * * * *
3 a b 3 5

so without any combinatorical proof as to
why your result is independent of the shape
of all possible patterns like e.g.

* * * * *
a b 3 c 5

or

* * * * * * * *
3 7 11 3 a 5 3 b ...

the proof of your lemma is not complete ...

also, as mentioned before we have
accomodate(11,4) = 4 and pi(4)+2 = 3
for the set(11,4)={11,13,15,17}

according to your opinion, is doesn't
matter as you would only need the relation
accomodate(n,c) >= pi(c)+2 for c>=3 and all n

but any other expression with '>=' would still
need a proof.

obvously the constant 2 in the above lemma is crucial for the conclusion ...
so please prove a correct relation
accomodate(n,c) >= pi(c)+x with x>0
and you will have

for odd n:
pi[n^2,(n+1)^2]
>= accomodate(n^2, n+1) - assist[n^2, (n+1)^2]
>= pi(n+1) + x - assist[n^2, (n+1)^2] ... lemma with '>='
>= pi(n+1) + x - pi(n+1)
= x

and for even n:
pi[n^2,(n+1)^2]
>= accomodate(n^2+1, n+1) - assist[n^2, (n+1)^2]
>= pi(n+1) + x - assist[n^2, (n+1)^2] ... lemma with '>='
>= pi(n+1) + x - pi(n+1)
= x[/FONT][/QUOTE]

Awesome! I like your spirit. Thanks for discussing directly with me. I'm not ready just yet to change my definitions or notation, but I'll take the suggestion to heart.

Now that I've had the opportunity to see your thoughts and comments, I see what you're saying and agree more is needed to fully prove the lemma. However, I do not think we need to go back to the drawing board entirely and consider all potential combinations at each set size. Really, there is only one final gap that needs to be filled.

Consider the inductive hypothesis again at the initial case (when the target set is x=3). The "shape" that I'm using (using your phrase here, but need to come up with a better word than shape) is [U]a[/U] perfect accommodation of the set when x=3 (note, I make no claim on uniqueness. I am not saying this shape is the only perfect accommodation, just that it exists within the set of potential perfect accommodations). As the shape makes use of pi(3)+2 primes, the inductive hypothesis holds true.

Next, carry forward the inductive hypothesis. Let my shape be a perfect accommodation where the target set is x=k-1. Then there are two cases to consider. Only the last case needs further consideration.

Case 1 (k is not prime): If k is not prime, then pi(k-1)+2 = pi(k)+2. Then the "shape" is also going to be a perfect accommodation for a set of size x=k, because this new target set has one more element than the k-1 case, and you cannot accommodate a bigger target set with less primes than the set before. Therefore, pi(k-1)+2 = pi(k)+2 primes are needed for the perfect accommodation.

Case 2 (k is prime): If k is prime, then pi(k-1)+2 is less than pi(k)+2. You are correct that in this case, it needs to be further established that the shape remains a perfect accommodation at the x=k level. i.e. it needs to be shown that no different "shape" exists that needs only pi(k-1)+2 primes to perfectly accommodate. Once established, everything else falls into place.

Thank you! Your insight is appreciated. I live in a rural place (and again a lawyer by trade...not many math minds in the bunch), so it is difficult to find people who even know what I'm talking about, let alone find people who can provide meaningful insight and criticism. I'll definitely need to take some time to consider this second case. Hopefully others working here will do the same. Look forward to any further insights or comments.

Cheers!

[QUOTE=10metreh;475316]I don't come here very often, but this caught my attention. This is an incredibly bold claim, especially when many of the finest mathematicians of the last two centuries have tried to prove these conjectures without success.

Your "accommodation lemma" is false. In your notation, pi(19) = 7, so 9 primes should be needed to accommodate a set of 19 consecutive odd integers. But the 19 odd integers from 2163 to 2199 are accommodated by the 8 primes 3, 5, 7, 11, 13, 37, 41 and 2179.

guptadeva has pointed out the main issue with the proof: your induction assumes that your pattern is the only way a set can be accommodated by the required number of primes, when in fact there are other ways.[/QUOTE]

Interesting. If there are counterexamples, then you may be right and it may be time to head back to the drawing board completely. Thanks!

another 'proof'

in the classic book
"an introduction to the theory of numbers" by hardy and wright
the authors prove theorem 20:

pi(n) >= ln(n) / 2ln(2) for n>=1

therefore one could naively and wrongly conclude:

pi((n+1)^2) - pi(n^2)
>= ln((n+1)^2) / 2ln(2) - ln(n^2) / 2ln(2) ... [B]:exclaim: the >= is WRONG[/B] :exclaim:
= (2 ln(n+1) / 2ln(2)) - (2 ln(n) / 2ln(2))
= (ln(n+1) - ln(n)) / ln(2)
> 0

[QUOTE=science_man_88;475314]Two word come to mind [URL="https://en.m.wikipedia.org/wiki/Pigeonhole_principle"]pigeonhole priciple[/URL][/QUOTE]

please elaborate how the pigeonhole principle may be applied in order to prove the conjecture ...
i am not able to see that clearly - maybe i am blind ? :cry:

That's a nice one. Thanks, guptadeva!

For the benefit of the people who have trouble with inequalities:
When confused, try to go from abstract to concrete.

Example: why is the highlighted error above an error?
Here is why: consider a concrete similar argument.
Predicates: a >= 7, b >= 6.
Does it follow that a-b >= 1? Of course not (e.g. take a=b=10; take a=10, b=100, etc)

Here is how the correct reasoning could flow:
Predicates: a >= 7, b [B]<=[/B] 6.
Conclusion: a-b >= 1. This argument is correct.

[QUOTE=robtaylor501;475325]... I'm not ready just yet to change my definitions or notation ...
[/QUOTE]

there is really no need doing that !
i really like the style and presentation on your blog.
the translation into some mathematical formalism was just a necessity for me to better understand your concepts and ideas ...

[QUOTE=guptadeva;475329]please elaborate how the pigeonhole principle may be applied in order to prove the conjecture ...
i am not able to see that clearly - maybe i am blind ? :cry:[/QUOTE]

Divisibility on any arithmetic progression is governed by it. Take the first r entries in any arithmetic progression, either r divides into one of them, or it divide into none of the values in the progression. It can then be generalized to be univariate polynomial remainder theorem. Even Euler's generalized version of Fermat's theorem can be deduced from it. Okay, it's general remainder.

[QUOTE=guptadeva;475332]there is really no need doing that !
i really like the style and presentation on your blog.
the translation into some mathematical formalism was just a necessity for me to better understand your concepts and ideas ...[/QUOTE]

Thank you! I enjoy the blog. It's a good way to at least get ideas out into the world. 10metreh's counterexample still has me floored. Now I'm wondering if there is any way to calculate a lower bound on the number of primes needed when accommodating sets. I guess the question isn't as valuable, as 10metreh shows perfect accommodations with less than pi(x)+2 primes exist, thus throwing my inequalities out the window and also throwing the takeaways on Legendre's, etc. out the window. Moreover, (what I thought was) a nice philosophical takeaway goes out the window, as if that "shape" did in fact perfectly accommodate all set sizes and we let x tend to infinity, then the end result would be the layout of the set of integers, meaning all numbers were arranged in a perfect accommodation. It had a nice zen feel to it. It made sense. Oh well. C'est la vie.

These prime numbers! So unruly.

[QUOTE=robtaylor501;475343]Thank you! I enjoy the blog. It's a good way to at least get ideas out into the world. 10metreh's counterexample still has me floored. Now I'm wondering if there is any way to calculate a lower bound on the number of primes needed when accommodating sets. I guess the question isn't as valuable, as 10metreh shows perfect accommodations with less than pi(x)+2 primes exist, thus throwing my inequalities out the window and also throwing the takeaways on Legendre's, etc. out the window. Moreover, (what I thought was) a nice philosophical takeaway goes out the window, as if that "shape" did in fact perfectly accommodate all set sizes and we let x tend to infinity, then the end result would be the layout of the set of integers, meaning all numbers were arranged in a perfect accommodation. It had a nice zen feel to it. It made sense. Oh well. C'est la vie.

These prime numbers! So unruly.[/QUOTE]

I think it goes back to post 6. That's because unlike part of what I stupidly just said, the pigeonhole principle, doesn't gaurantee that same remainder will be 0. I think you should use:

[TEX]\phi(n) + \Omega(n)[/TEX] where phi is Euler's totient function, and Omega is prime factors counted once each.

[QUOTE=robtaylor501;475343]These prime numbers! So unruly.[/QUOTE]

yet there is order in the chaos ... search and you will find ... :bounce wave:

[QUOTE=robtaylor501;475343]Thank you! I enjoy the blog. It's a good way to at least get ideas out into the world. 10metreh's counterexample still has me floored. Now I'm wondering if there is any way to calculate a lower bound on the number of primes needed when accommodating sets. I guess the question isn't as valuable, as 10metreh shows perfect accommodations with less than pi(x)+2 primes exist, thus throwing my inequalities out the window and also throwing the takeaways on Legendre's, etc. out the window. Moreover, (what I thought was) a nice philosophical takeaway goes out the window, as if that "shape" did in fact perfectly accommodate all set sizes and we let x tend to infinity, then the end result would be the layout of the set of integers, meaning all numbers were arranged in a perfect accommodation. It had a nice zen feel to it. It made sense. Oh well. C'est la vie.

These prime numbers! So unruly.[/QUOTE]

ok ... i will give you some hopefully fruitful hints:

in order to find an expression or inequality for your 'accomodation lemma' you really do not need to consider perfect accomodations for all different arrangements.
it is sufficient to consider perfect accomodations of the actual arrangements for/of the sets of all odd numbers between n^2 and (n+1)^2 for increasing n ...
if you start to see a pattern in these arrangements you would then maybe be able to find a form of the general 'shape' (we really need a better word for that) and then try to apply induction from there

you could also consider taking one step back and include the prime 2 and all even numbers back into your considerations :exclaim:

another approach could be to succesively sieve all numbers which can be accomodated by the primes 2,3,5,... out from [n^2, (n+1)^2] and see if you might be able to start to see some pattern in the sets remaining ...

alternatively you could also start with a proof of the oppermann conjecture instead :smile:

finally you could also step out of the box and attempt to find some new relation or pattern among the prime numbers themself :innocent:

[QUOTE=science_man_88;475344]I think it goes back to post 6. That's because unlike part of what I stupidly just said, the pigeonhole principle, doesn't gaurantee that same remainder will be 0. I think you should use:

[TEX]\phi(n) + \Omega(n)[/TEX] where phi is Euler's totient function, and Omega is prime factors counted once each.[/QUOTE]

honestly thanks for your suggestion ...

your mind seems to be as twisted or convoluted as the prime numbers are spread among the natural numbers :razz:

[QUOTE=guptadeva;475380]honestly thanks for your suggestion ...

your mind seems to be as twisted or convoluted as the prime numbers are spread among the natural numbers :razz:[/QUOTE]

Well the prime numbers above 3 are in one of 2 arithmetic progressions with constant difference 6.

[QUOTE=science_man_88;475390]Well the prime numbers above 3 are in one of 2 arithmetic progressions with constant difference 6.[/QUOTE]

well ... so far so good
do you happen to know some necessary and sufficient condition for a number to be a prime - other than a sieve ?
a [B]simple[/B] unconditional deterministic primality test would be fine :smile:

[QUOTE=guptadeva;475394]well ... so far so good
do you happen to know some necessary and sufficient condition for a number to be a prime - other than a sieve ?
a [B]simple[/B] deterministic primality test would be fine :smile:[/QUOTE]

Not sure it's simple but numberphile did a video on aks testing.

[YOUTUBE]HvMSRWTE2mI [/YOUTUBE]

[QUOTE=science_man_88;475398]Not sure it's simple but numberphile did a few videos on aks testing.[/QUOTE]

agree ... the aks test is astonishing as to the fact, that it exists,

yet as our mathematical knowledge increases it would be truelly wonderful to know somethig even more simple and beautiful than that ...
besides that, the aks test (ignoring their very nice contribution through appropriate polynomial division for a moment) is nothing than the trivial fact that p is prime iff p divides the all binomial coefficients (p over q) with 1 < q < p ... naively spoken it's a sieve in disguise.

(the terms simple and beautiful might not be defined properly, yet i believe we will know and recognize it as soon as we see it ?)

[QUOTE=guptadeva;475401]besides that, the aks test (ignoring their very nice contribution through appropriate polynomial division for a moment) is nothing than the trivial fact that p is prime iff p divides the all binomial coefficients (p over q) with 1 < q < p ... naively spoken it's a sieve in disguise.[/QUOTE]

I’m not sure I can agree. If it were a sieve in disguise I’d expect it to take at least as long as enumerating the primes in the relevant interval. But that’s not the case — it’s vastly faster. So while one might argue that it owes some heritage to sieves I certainly can’t agree that it’s a sieve (in disguise or otherwise).

[QUOTE=CRGreathouse;475503]I’m not sure I can agree. If it were a sieve in disguise I’d expect it to take at least as long as enumerating the primes in the relevant interval. But that’s not the case — it’s vastly faster. So while one might argue that it owes some heritage to sieves I certainly can’t agree that it’s a sieve (in disguise or otherwise).[/QUOTE]

[ATTACH]17431[/ATTACH]

step 3 of the aks-test (see attachment above) is in fact a classical sieve.
the reason for aks being vastly faster than a full sieve is the existence of the parameter r in step 2, so that the sieve only has to run until min(r,n-1) ...
yet in the (relatively rare) case, that r>=n-1 a full sieve is executed.
also the step 5 is relatively slow ...

the main contribution of agrawal, kayal and saxena was in fact the introduction of an appropriate polynomial division (with x^r -1) based on group-theoretical arguments and also to proove that their algorithm is complete.

Certainly we would want to read more about the AKS test rather than rely on that video. "the aks test [...] is nothing than the trivial fact that [...]" is what everyone thinks after watching that video, which is a disservice to the AKS paper, which the video rolls up in "well that's not quite the same" at 2:35-2:50.

It's like a video about the Lucas-Lehmer test spending almost all the time explaining Wilson's Theorem, then at the end saying "and then using some fiddly bits from Lucas, Lehmer did some twiddling to make it a bit faster, but we won't show that."

"yet in the (relatively rare) case, that r>=n-1 a full sieve is executed."

Once above tiny size numbers, r is *much* smaller than sqrt(n). The time taken in steps 1-4 is very small relative to step 5.

"also the step 5 is relatively slow ... "

Yes it is, but it's faster than trial division once past small inputs and clearly shows polynomial growth in empirical implementations. Much different than trial division.

[QUOTE=guptadeva;475394]a [B]simple[/B] unconditional deterministic primality test would be fine[/QUOTE]

At the last Pari/GP Atelier, I had a discussion with a number theorist who was genuinely mystified as to why anyone would think ECPP was at all complicated. It was quite obvious to him and his colleagues. Not that it was obvious in original conception of course, but given a short description of the complete method and a reference to a few papers, what would be any sort of hold up?

"simple" is relative.


I also assume you want "fast" added to your list of items. It's also relative, but without it there are quite a few useless choices. You can also get some not useless but not really fast tests like the BLS75 methods (partial factoring of n-1 and/or n+1). They're simple, unconditional, and deterministic. They're also a lot faster than trial division.

I do agree that, given the state of most programs / programmers, it'd be nice to have something else. Multiple Miller-Rabin tests is the height of most non-math programs. At least adding a strong Lucas test would be nice. APR-CL and ECPP do have open source libraries but certainly not many users.

[QUOTE=guptadeva;475376]ok ... i will give you some hopefully fruitful hints:

in order to find an expression or inequality for your 'accomodation lemma' you really do not need to consider perfect accomodations for all different arrangements.
it is sufficient to consider perfect accomodations of the actual arrangements for/of the sets of all odd numbers between n^2 and (n+1)^2 for increasing n ...
if you start to see a pattern in these arrangements you would then maybe be able to find a form of the general 'shape' (we really need a better word for that) and then try to apply induction from there

you could also consider taking one step back and include the prime 2 and all even numbers back into your considerations :exclaim:

another approach could be to succesively sieve all numbers which can be accomodated by the primes 2,3,5,... out from [n^2, (n+1)^2] and see if you might be able to start to see some pattern in the sets remaining ...

alternatively you could also start with a proof of the oppermann conjecture instead :smile:

finally you could also step out of the box and attempt to find some new relation or pattern among the prime numbers themself :innocent:[/QUOTE]

Thank you. Helpful hints indeed. :smile: Time for a pot of tea and a new perspective!

[QUOTE=danaj;475514]Certainly we would want to read more about the AKS test rather than rely on that video. "the aks test [...] is nothing than the trivial fact that [...]" is what everyone thinks after watching that video, which is a disservice to the AKS paper, which the video rolls up in "well that's not quite the same" at 2:35-2:50.
[/QUOTE]

yes - it is indeed a disservice to the aks-paper

[ATTACH]17432[/ATTACH]

to make such simplifying statements - yet sometimes simplification may improve understanding.

[QUOTE=danaj;475523]At the last Pari/GP Atelier, I had a discussion with a number theorist who was genuinely mystified as to why anyone would think ECPP was at all complicated. It was quite obvious to him and his colleagues. Not that it was obvious in original conception of course, but given a short description of the complete method and a reference to a few papers, what would be any sort of hold up?

"simple" is relative.


I also assume you want "fast" added to your list of items. It's also relative, but without it there are quite a few useless choices. You can also get some not useless but not really fast tests like the BLS75 methods (partial factoring of n-1 and/or n+1). They're simple, unconditional, and deterministic. They're also a lot faster than trial division.

I do agree that, given the state of most programs / programmers, it'd be nice to have something else. Multiple Miller-Rabin tests is the height of most non-math programs. At least adding a strong Lucas test would be nice. APR-CL and ECPP do have open source libraries but certainly not many users.[/QUOTE]

:goodposting:very informative ... THANKS

yet, honestly i'm not interested in "fast" algorithms at the moment - so which algorithms do you have in mind when when mentioning "quite a few useless choices" ?
maybe they are "beautiful" ?

[QUOTE=robtaylor501;475264]That assumes I know how to code. I don't. :smile:[/QUOTE]

Elementary is not trivial though.

[QUOTE=guptadeva;475525]to make such simplifying statements - yet sometimes simplification may improve understanding.[/QUOTE]

It would be a great intro if it were a bit clearer about what it was demonstrating, and then put a little more time in about what the rest of the paper did. I enjoy their videos, and it is a heck of a job to simplify enough to explain to a more general audience and make it very interesting. So I'd really wish it was clearer.

There are a lot of people posting on the internet who see that video then believe that lemma is the AKS test entirely. Sometimes with some confusion over what all the fuss was about or how it could be efficient, but sometimes just recommending people implement it to check 10 digit inputs because it is Moar Faster.


Wilson's theorem is quite elegant and simple, but not fast. Similarly the statement about binomials equaling zero, which is elegant though slower than simple trial division. Trial division itself, whether naive, wheel optimized, or using primes generated with a sieve. Miller's test using either n/4 or various proven reductions is pretty straightforward (getting all the way down to 2*log^2(n) requires the GRH). Underwood collects lots of oddball formulas in his 1983 paper [URL="https://www.maa.org/programs/faculty-and-departments/classroom-capsules-and-notes/formulas-for-primes"]Formulas for Primes[/URL], most of which devolve into either Wilson's Theorem or a sieve.

In practice one usually uses APR-CL and/or ECPP. Typically with BPSW used as a pre-test. Of course if the input is a special form with an efficient test we would use that.

[QUOTE=guptadeva;475510]step 3 of the aks-test (see attachment above) is in fact a classical sieve.
the reason for aks being vastly faster than a full sieve is the existence of the parameter r in step 2, so that the sieve only has to run until min(r,n-1) ...
yet in the (relatively rare) case, that r>=n-1 a full sieve is executed.[/QUOTE]

Ah — I understand — you’re not actually familiar with AKS. (Not a problem.)

Checking for primes up to r is nothing like sieving. Given a nice small number to prove prime, with just (say) 80 digits, r would almost surely be less than 50, while “sieving” (what you meant was trial division, I think) would require you to go to 10^40. That’s microseconds of effort on one core vs. all computers on earth calculating for the age of the universe. Big difference.

It’s actually more like checking that the base of a Fermat test is relatively prime to the number being tested: you’re just ruling out a few pathological cases.

[QUOTE=CRGreathouse;475544]Ah — I understand — you’re not actually familiar with AKS. (Not a problem.)

Checking for primes up to r is nothing like sieving. Given a nice small number to prove prime, with just (say) 80 digits, r would almost surely be less than 50, while “sieving” (what you meant was trial division, I think) would require you to go to 10^40. That’s microseconds of effort on one core vs. all computers on earth calculating for the age of the universe. Big difference.

It’s actually more like checking that the base of a Fermat test is relatively prime to the number being tested: you’re just ruling out a few pathological cases.[/QUOTE]

i am here to learn :smile:

what place is better to ask questions about primes as in a forum where the density of number theorists, mathematicians, computer gurus and prime number enthusiasts can be described by a dirac delta function ?

also according to the ancient saying of aristotleles (?):
better to ask a question, than to eternally remain in ignorance ...

let me ask:
[B][COLOR=Red]are there some known (exact) primality tests for a number n requiring less than pi(n) [U]steps[/U] other using a lookup table or wilsons theorem[/COLOR][/B][B][COLOR=Red]?[/COLOR]

[/B]please note that i'm not interested in speed or computational complexity just the number of steps needed.

what i'm looking for is some analogue idea to "the existence of an algorithm to find the n'th digit of the number pi written hexadecimally [U]without[/U] the knowledge of the previous digits".

[URL="https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula"]https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula[/URL]

truelly wonderful indeed - but the catch is, that determining the m'th 'corresponding' base 10 digit(s) would require the knowledge of the previous hexadecimal digits ...

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

[QUOTE=guptadeva;475555]let me ask:
[B][COLOR=Red]are there some known (exact) primality tests for a number n requiring less than pi(n) [U]steps[/U] other using a lookup table or wilsons theorem[/COLOR][/B][B][COLOR=Red]?[/COLOR]

[/B]please note that [U]i'm not interested in[/U] speed or [U]computational complexity[/U] just the number of steps needed.[/QUOTE]

My underline.

So basically, you ask a question, but you don't want the answer.:picard:

[QUOTE=axn;475567]
So basically, you ask a question, but you don't want the answer.:picard:[/QUOTE]

just forget the phrase "computational complexity" in context with "i'm not interested" for the moment - i am sorry to have formulated the question in a silly manner.

and yes i truelly want an answer and know that computational complexity is THE measure to describe computational steps needed - but i would like to know some answer in terms of [U]logical steps[/U] too if possible.

i believe, that you understand my question anyway:

[B][COLOR=Red]do you know a "simple", and possibly "beautiful" formula for p(i) not including all p(j) with j<i ?[/COLOR][/B]

if we take the resulting numbers left after applying the sieve of eratosthenes to be the "definition" of prime numbers, then the answer would be [B]no[/B] as we can prove, that such a formula can not exist on that base.

if on the other hand we stick with the original definition of a prime number, then i cannot see any arguments why such a formula should not exist ?

also you may drop the terms "simple" and "beautiful" from the question - any positive answer or existense of such a formula would automatically be beautiful and hopefully simple :smile:

[QUOTE=guptadeva;475568]just forget the phrase "computational complexity" in context with "i'm not interested" for the moment - i am sorry to have formulated the question in a silly manner.

and yes i truelly want an answer and know that computational complexity is THE measure to describe computational steps needed - but i would like to know some answer in terms of [U]logical steps[/U] too if possible.

i believe, that you understand my question anyway:

[B][COLOR=Red]do you know a "simple", and possibly "beautiful" formula for p(i) not including all p(j) with j<i ?[/COLOR][/B]

if we take the resulting numbers left after applying the sieve of eratosthenes to be the "definition" of prime numbers, then the answer would be [B]no[/B] as we can prove, that such a formula can not exist on that base.

if on the other hand we stick with the original definition of a prime number, then i cannot see any arguments why such a formula should not exist ?

also you may drop the terms "simple" and "beautiful" from the question - any positive answer or existense of such a formula would automatically be beautiful and hopefully simple :smile:[/QUOTE]
Gcd with sqrt(n)#, # meaning primoial.

[QUOTE=robtaylor501;475524]Thank you. Helpful hints indeed. :smile: Time for a pot of tea and a new perspective![/QUOTE]

maybe you can get some inspiration from the following illustrations

[ATTACH]17435[/ATTACH]

they are very simple and should be self-explanatory.
please also note, that the numbers are arranged according to

1 2
3 4

1 2 3
4 5 6
7 8 9

instead of

1 2
3 4

1 2 5
3 4 6
7 8 9

where all squares are positioned on the diagonal line

many number-theorists prefer the first set of arrangements because of the following reasons:

1) the legendre conjecture may be interpreted geometrically as
the last two lines contain at least one prime (red box)

2) the formulation of the oppermann conjecture may be interpreted as
the last line and the line following contain at least one prime each

3) in each illustration you can easily find the representation of a number x in the base n by simply looking at the column- and row-numbers of x

4) other "patterns" - each being some conjecture about the prime-numbers emerge automatically given some time :smile:

example: the conjecture that to each n and each i<n^2-n there is a prime between i+1 and i+n is wrong - as can be seen visually (counter-example: n=12 and i=113)
this illustrates the well-known gap of length > n between two consecutive primes < n^2

[QUOTE=science_man_88;475570]Gcd with sqrt(n)#, # meaning primoial.[/QUOTE]
"Surely You're Joking, Mr. Feynman!" - is a very good book

[QUOTE=guptadeva;475573]"Surely You're Joking, Mr. Feynman!" - is a very good book[/QUOTE]

You said steps not computational complexity.

[QUOTE=science_man_88;475574]You said steps not computational complexity.[/QUOTE]

"Surely You're Joking, Mr. Feynman!"
i actually had many discussions with richard feynman one or two years before he passed away ... what a true inspiration he was - he managed to make you grasp even the most complicated problems in his own brilliant way ...

[QUOTE=guptadeva;475575]"Surely You're Joking, Mr. Feynman!"
i actually had many discussions with richard feynman one or two years before he passed away ... what a true inspiration he was - he managed to make you grasp even the most complicated problems in his own brilliant way ...[/QUOTE]

Except it's one step maybe 2 if you count the comparison to 1. It may be complex if you assume no look up table. But it is definitely 2 steps. 1 do the computation, 2 compare the result to 1.

[QUOTE=science_man_88;475577]Except it's one step maybe 2 if you count the comparison to 1. It may be complex if you assume no look up table. But it is definitely 2 steps. 1 do the computation, 2 compare the result to 1.[/QUOTE]

step 1 implies the knowledge of [U]all[/U] prime numbers <= sqr(x)

[QUOTE=guptadeva;475579]step 1 implies the knowledge of [U]all[/U] prime numbers <= sqr(x)[/QUOTE]

That was not a condition given.

[QUOTE=guptadeva;475555][B][COLOR=Red]are there some known (exact) primality tests for a number n requiring less than pi(n) [U]steps[/U] other using a lookup table or wilsons theorem[/COLOR][/B][B][COLOR=Red]?[/COLOR][/quote]

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

[QUOTE=guptadeva;475555]and yes, of cause i take my words back that the aks-test is a sieve in disgiuse :innocent:[/QUOTE]

You’re learning!

[QUOTE=science_man_88;475580]That was not a condition given.[/QUOTE]

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

so let me continue with

[B][COLOR=Red]do you know a formula for p(i) not including all p(j) with j<i ?[/COLOR][/B]

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

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.

[QUOTE=guptadeva;475583]yes ... true - the original question was just the beginning and i am grateful for your mentioning the primorial function.

so let me continue with

[B][COLOR=Red]do you know a formula for p(i) not including all p(j) with j<i ?[/COLOR][/B]

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 :smile:[/QUOTE]

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

[QUOTE=science_man_88;475586]I believe I remember hearing about a degree 25 rational polynomial whose outputs were exactly the primes...[URL]http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html[/URL][/QUOTE]

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

[url]https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/JonesSatoWadaWiens.pdf[/url]

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:

[url]https://math.stackexchange.com/a/961539/117584[/url]

[url]https://math.stackexchange.com/a/775314/117584[/url]

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

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

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

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

[QUOTE=danaj;475617]
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.
[/QUOTE]

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

[QUOTE=guptadeva;475745]and even more happy after having found:
[url]https://oeis.org/wiki/Formulas_for_primes[/url][/QUOTE]

I wrote that page. :smile: I'm working on a survey paper and that was my first cut.

[QUOTE=CRGreathouse;475975]I wrote that page. :smile: I'm working on a survey paper and that was my first cut.[/QUOTE]

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

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

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

[QUOTE=George M;475977]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.
[/QUOTE]
It is trivial. For example with \(n=3\) as \(p_1=2\) we have
\[ p_4-p_3+p_3-p_2+p_2-p_1+p_1=p_4. \]

[QUOTE=CRGreathouse;475975]I wrote that page.[/QUOTE]

Very nice!

Helfgott finally published his sieve: [url]https://arxiv.org/abs/1712.09130[/url]

I like Dudley's 1983 Formulas for Primes paper, which is free online from MAA.

For sieves, Quesada and Van Pelt (1996) and Quesada (1992).

For primality proving, I think the BLS75 paper ([url]http://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf[/url]) is an important collection of state of the art methods in 1975, many of which are still used for special forms.

For primality testing there are lots of Frobenius variants:

general polynomial (Grantham)
standard quadratic (lower case q), Grantham and others including Crandall & Pomerance
standard cubic (Buell and Kimball outlined from Grantham)

^ the above don't specify the parameters, like Fermat and M-R have an unspecified base that's important in practice. I believe all the ones below include parameter selection so are more like BPSW in that the user doesn't add extra parameters.

QFT (upper case q) from Grantham with extra steps
EQFT, SQFT, MQFT variations on Grantham's QFT
Khashin (2013)
Underwood (2012, 2014, 2016?)

[QUOTE=danaj;476065]Helfgott finally published his sieve[/QUOTE]

I saw that two days ago, very exciting. He has much more detail than he gave in his talk.

[QUOTE=danaj;476065]

Helfgott finally published his sieve: [URL]https://arxiv.org/abs/1712.09130[/URL]
[/QUOTE]



Thanks for the link, very interesting.
About processing the primes it is faster to save the primes in to RAM, but if you want to work on the goldbach conjecture you will need at least a range of 10^12 per package. You can only use the segmented sieve, e.g. processing about 8 GB of primes, load them into RAM and after your memory is full you can create the goldbach partitions and prime gap analysis. Than you can proceed the next primes.
This is also way better for your SSD (if you would run this on SSD´s), the maximum write and read function is limited. (e.g. 728 Terabyte for an Hyper X 3K, 240 GB)
Such tasks can be done using the BOINC wrapper technology.