mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   The "one billion minus 999,994,000" digits prime number (https://www.mersenneforum.org/showthread.php?t=20568)

 a1call 2015-10-23 17:53

The "one billion minus 999,994,000" digits prime number

Hi,
I am looking for a partner/team to try and find a billion digits prime for the EFF prize.
I am certain that it can be done using the formula and the proof that all outputs within a range are guaranteed to be primes that I have developed but have not published yet.
The computation does not involve any primality tests since all outputs within the range are primes but some variables will need to be fine tuned to make the output within the range.
My email address is overwhelmed so the best way to communicate would be to post to this thread.

 Batalov 2015-10-23 18:30

Run your algorithm and give us a toy example of a tiny 1-[I]million[/I]-digit prime.

No need to fine-tune the parameters - anything from 1- to 3-5- million digits will be fine and convincing; it doesn't have to be exactly [URL="http://primes.utm.edu/primes/page.php?id=111603"]1,000,000-digits[/URL]. Such a prime is indeed tiny compared to what you are trying to achieve.

 Mark Rose 2015-10-23 18:42

:popcorn:

 a1call 2015-10-23 18:43

I think that's a fair challenge. I am probably a bit old an impatient to write codes myself which is why I thought I would partner with expert programmers on the field. But I should be able to come up with a relatively large prime using Wolfram Alpha or JavaScript (will take much longer to set up my old computers and libraries).

Anyone know if Wolfram Alpha can be set up to run routines and try list of variables?

 rogue 2015-10-23 19:53

Also, any number you find needs to be proven prime with other software. pfgw will be able to do a PRP test on anything, but there is no quick way to prove primality on most PRPs.

I suggest that you start smaller, about 1,000 decimal digits. If it is relatively easy to find PRPs of that size and they can be proven prime using Primo if pfgw can't handle them. You will need to show that all numbers of that size that you generate with your code are both PRP and prime before anyone takes you seriously.

 R.D. Silverman 2015-10-23 21:34

[QUOTE=a1call;413480]Hi,
I am looking for a partner/team to try and find a billion digits prime for the EFF prize.
I am certain that it can be done using the formula and the proof that all outputs within a range are guaranteed to be primes that I have developed but have not published yet.
The computation does not involve any primality tests since all outputs within the range are primes but some variables will need to be fine tuned to make the output within the range.
My email address is overwhelmed so the best way to communicate would be to post to this thread.

ROTFLMAO

 a1call 2015-10-23 21:41

Thank you [B]Rogue[/B] for introducing me to Primo and PFGW.

Can any of them run any sort of routines off the shelf? Or they only take in integers?

 Gordon 2015-10-23 21:41

[QUOTE=a1call;413480]Hi,
I am looking for a partner/team to try and find a billion digits prime for the EFF prize.
I am certain that it can be done using the formula and the proof that all outputs within a range are guaranteed to be primes that I have developed but have not published yet.
The computation does not involve any primality tests since all outputs within the range are primes but some variables will need to be fine tuned to make the output within the range.
My email address is overwhelmed so the best way to communicate would be to post to this thread.

you're the CEMPLLA guy and I claim my prize :razz:

 rogue 2015-10-23 22:02

[QUOTE=a1call;413514]Thank you [B]Rogue[/B] for introducing me to Primo and PFGW.

Can any of them run any sort of routines off the shelf? Or they only take in integers?[/QUOTE]

They only take in integers.

 alpertron 2015-10-23 22:19

[QUOTE=a1call;413480]
I am looking for a partner/team to try and find a billion digits prime for the EFF prize.
I am certain that it can be done using the formula and the proof that all outputs within a range are guaranteed to be primes that I have developed but have not published yet.
The computation does not involve any primality tests since all outputs within the range are primes but some variables will need to be fine tuned to make the output within the range.
My email address is overwhelmed so the best way to communicate would be to post to this thread.

There are too many people who claim to be able to generate primes of any size, because of the prizes. A decade ago, other people claimed that they could factorize a number of 1000 digits, or so, thus trying to get the money from the RSA challenge.

So if you think that your algorithm always generate huge primes, you should post the algorithm in order to be analyzed. There are some people in this forum that can check very quickly whether you are losing your time or you have something that hundreds of number theorists have not found in centuries.

 a1call 2015-10-23 22:41

[QUOTE=Gordon;413515]you're the CEMPLLA guy and I claim my prize :razz:[/QUOTE]

That thread is too long for my time availability.
Was it based on a proof based on number ranges or was it something else?
Are there any similar proofs that fail on large numbers due to element divergence?

To make it clear.

|P[SUB]7[/SUB]#/2-2[SUP]n[/SUP]| can be proven to be prime for all results less than 49. No primality testing is required.
Of course this will become useless for larger numbers when the two sides fail to diverge.

 R.D. Silverman 2015-10-23 22:46

[QUOTE=a1call;413527]That thread is too long for my time availability.
Was it based on a proof based on number ranges or was it something else?
Are there any similar proofs that fail on large numbers due to element divergence?

To make it clear.

P[SUB]7[/SUB]#/2-2[SUP]n[/SUP] can be proven to be prime for all results less than 49. No primality testing is required.
Of course this will become useless for larger numbers when the two sides fail to diverge.[/QUOTE]

Idiot

 a1call 2015-10-23 23:18

[QUOTE=alpertron;413523]There are too many people who claim to be able to generate primes of any size, because of the prizes. A decade ago, other people claimed that they could factorize a number of 1000 digits, or so, thus trying to get the money from the RSA challenge.

So if you think that your algorithm always generate huge primes, you should post the algorithm in order to be analyzed. There are some people in this forum that can check very quickly whether you are losing your time or you have something that hundreds of number theorists have not found in centuries.[/QUOTE]

As mentioned I am hoping to submit my theorems for publication at some point, so I am not going to disclose them here in the open.
However, I am perfectly willing to share the theorems along with their proofs to any large-integer-computation-savvy entities that would be willing to assist me.

 alpertron 2015-10-23 23:23

[QUOTE=a1call;413527]That thread is too long for my time availability.
Was it based on a proof based on number ranges or was it something else?
Are there any similar proofs that fail on large numbers due to element divergence?

To make it clear.

|P[SUB]7[/SUB]#/2-2[SUP]n[/SUP]| can be proven to be prime for all results less than 49. No primality testing is required.
Of course this will become useless for larger numbers when the two sides fail to diverge.[/QUOTE]

This type of sequences f(n) where f(n) is a polynomial or n is located also in the exponent cannot generate prime numbers for all n.

For polynomials this is very easy to see: suppose that f(n) = p where n is an integer, p a prime number and f() is not constant. Then f(n+kp) is always multiple of p. At most deg(f) values of k will make f(n+kp) equal to p, so there are infinite values for the integer k for which the value of that polynomial f(n+kp) is not prime.

If you want someone to program your algorithm, this person should be completely sure that the algorithm is sound. He will not necessarily believe you, so you will need to publish it somewhere with peer review before the coding start. In general this problem does not exist, because the mathematician can also program the algorithms.

 a1call 2015-10-23 23:46

Hello [B]alpertron[/B],
I am aware of the proof for impossibility of regular as well as irregular polynomials generating prime numbers for all values of n.
However there are no proofs that other formulas will fail as well. An example would be Mills' formula, which is generally accepted to generate primes if the constant can be calculated.
To be clear my theorem has nothing to do with Mills' formula. My theorem is very similar to the example I posted above and you quoted(but can be made to diverge for large n).
It obviously does work for n= 6 and n= 7 and it can be proven that it would work for any results less than 49 which happen to be 41 and 23.
A quick proof would be that the two sides do not have a common divisor and thus their sum can not divide any of their prime factors which are all the positive primes less than or equal to 7. Thus any sum that is less than 7[SUP]2[/SUP] has to be prime. No primality testing is required.

 alpertron 2015-10-24 00:10

With respect to Mills, it is clear that the constant was computed from prime numbers, so it cannot be used to generate prime numbers.

It is like saying that the sequence N(10[SUP]n[/SUP]) generates always prime numbers (where N(k) means the next prime after k). The sequence exists because of [URL="https://en.wikipedia.org/wiki/Bertrand%27s_postulate"]Bertrand's postulate[/URL]. But it is not easily computable, especially in the billion-digit range.

Your example does not generalize to higher primorials: for example 11*7*5*3-2[SUP]n[/SUP] = 1155 - 2[SUP]n[/SUP]. You get 1155-1024 > 121, so you get no primes using your method.

 a1call 2015-10-24 00:30

[QUOTE=alpertron;413536]With respect to Mills, it is clear that the constant was computed from prime numbers, so it cannot be used to generate prime numbers.

It is like saying the the sequence N(10[SUP]n[/SUP]) generates always prime numbers (where N(k) means the next prime after k). The sequence exists because of [URL="https://en.wikipedia.org/wiki/Bertrand%27s_postulate"]Bertrand's postulate[/URL]. But it is not easily computable, especially in the billion-digit range.

Your example does not generalize to higher primorials: for example 11*7*5*3-2[SUP]n[/SUP] = 1155 - 2[SUP]n[/SUP]. You get 1155-1024 > 121, so you get no primes using your method.[/QUOTE]

I only mentioned Mills' formula to point out formulas can generate all primes and there is no proof that no formula will do so. Not knowing the constant is irrelevant to the the fact that there is no proof that there can be no formula that can generate all primes.
There are other formulas as well. Regardless my theorem as mentioned has nothing to do with Mills' formula.

Your sum should be 131 and 131 is not less than 11[SUP]2[/SUP] and does not apply to the proof I made. Your examples fails to diverge to less than 121. But I already pointed that out before. The example is not my theorem but is similar. The difference is that my theorem can be made to diverge to [B]less than[/B] the largest prime factor squared.

 Uncwilly 2015-10-24 00:31

[QUOTE=a1call;413531]As mentioned I am hoping to submit my theorems for publication at some point, so I am not going to disclose them here in the open.[/QUOTE]
Posting here gives you a time stamp on your work. It will establish that you were the first to bring your method to light. And there are enough reliable people in the field that frequent this board that any claims otherwise can be dismissed.
:popcorn:

 a1call 2015-10-24 00:42

[QUOTE=Uncwilly;413538]Posting here gives you a time stamp on your work. It will establish that you were the first to bring your method to light. And there are enough reliable people in the field that frequent this board that any claims otherwise can be dismissed.
:popcorn:[/QUOTE]

That is true and I planned to submit the theorems for publication. Until I came across the EFF prize. The official rules explicitly disqualify any theorems from winning the prize and require a specific prime. I find it idiotic to publish a thereon which will almost immediately enable someone with the right computing power to claim the EFF prize. Still if there are no takers I will go with the submit for publication option.

 alpertron 2015-10-24 00:45

[QUOTE=a1call;413537]I only mentioned Mills' formula to point out formulas can generate all primes and there is no proof that no formula will do so. Not knowing the constant is irrelevant to the the fact that there is no proof that there can be no formula that can generate all primes.
There are other formulas as well. Regardless my theorem as mentioned has nothing to do with Mills' formula.

131 so 131 is not less than 11[SUP]2[/SUP] and does not apply to the proof I made. Your examples fails to diverge to less than 121. But I already pointed that out before. The example is not my theorem but is similar. The difference is that my theorem can be made to diverge to [B]less than[/B] the largest prime factor squared[/QUOTE]
You have a strange definition of divergence. But I can say that for larger primorials, it will be more difficult to find "divergence". Since p# is about e[SUP]n[/sup], you are trying to find a difference of two numbers of about n/log(10) digits to be less than n[SUP]2[/SUP]. For big values of n this is very difficult to find.

Since your prime is bounded by n[SUP]2[/SUP], in order to find the billion-digit prime number, you will need to find the difference of two numbers of about 10[SUP]5*10^8[/SUP]/log(10) digits. Forget it.

 a1call 2015-10-24 00:54

[QUOTE=alpertron;413542]You have a strange definition of divergence. But I can say that for larger primorials, it will be more difficult to find "divergence". Since p# is about e[SUP]n[/sup], you are trying to find a difference of two numbers of about n/log(10) digits to be less than n[SUP]2[/SUP]. For big values of n this is very difficult to find.[/QUOTE]

My apologies. By divergence I mean divergence of a sum to less than a value (largest prime factor squared in this case).
The example that I provided is not only difficult to diverge, but virtually impossible. That is why I posted it on the open forum, since it will not make anyone claim any prizes.
However, my theorem can result in a formula that will diverge to a value where the associated proof confirms the output number is prime.

 a1call 2015-10-24 00:57

I meant [B]converge[/B]. Sorry about that

 VBCurtis 2015-10-24 06:03

[QUOTE=a1call;413543]My apologies. By divergence I mean divergence of a sum to less than a value (largest prime factor squared in this case).
The example that I provided is not only difficult to diverge, but virtually impossible. That is why I posted it on the open forum, since it will not make anyone claim any prizes.
However, my theorem can result in a formula that will diverge to a value where the associated proof confirms the output number is prime.[/QUOTE]

You seem deaf to both RDS' usual insults (translation: You're a crackpot) and the gentler efforts of others to point out that you've done nothing whatsoever to make your claim believable. Since you are stubborn and wish to not discuss your algorithm, your best path is to produce a 1M digit prime right quick. Since you have no code with which to do that, and no interest in having your process/formula/whatever reviewed, your claims have *nothing* whatsoever to support them, and nobody in their right mind on this forum is going to offer to help you except perhaps to hear what the supposed process is.

So, since your arguments are so far leading us nowhere, you ought to decide how you might convince someone skilled enough in mathematics to check your work and skilled enough in coding to implement your process that you're not a crackpot. You may wish to read the crackpot index guidelines, composed by one of my colleagues John Baez (found at [url]http://math.ucr.edu/home/baez/crackpot.html[/url]). A non-crackpot will be able to realize which of the listed items applies to this thread, and will be able to decide how to go about reducing one's score.

Good luck.

 a1call 2015-10-24 06:46

[QUOTE=VBCurtis;413571]Since you have no code with which to do that, and no interest in having your process/formula/whatever reviewed, your claims have *nothing* whatsoever to support them, and nobody in their right mind on this forum is going to offer to help you except perhaps to hear what the supposed process is.

[/QUOTE]

I have already mentioned that I am quite willing to disclose my theorem in confidence along with the mathematical proof that it is true to any party who would be willing to assist me and has the resources to generate and run the code to produce prize winning primes. I'm just not going to post it on the open forum.
The following is not relevant to your post.

 Gordon 2015-10-24 09:33

[QUOTE=VBCurtis;413571]You seem deaf to both RDS' usual insults (translation: You're a crackpot) and the gentler efforts of others to point out that you've done nothing whatsoever to make your claim believable. Since you are stubborn and wish to not discuss your algorithm, your best path is to produce a 1M digit prime right quick. Since you have no code with which to do that, and no interest in having your process/formula/whatever reviewed, your claims have *nothing* whatsoever to support them, and nobody in their right mind on this forum is going to offer to help you except perhaps to hear what the supposed process is.

So, since your arguments are so far leading us nowhere, you ought to decide how you might convince someone skilled enough in mathematics to check your work and skilled enough in coding to implement your process that you're not a crackpot. You may wish to read the crackpot index guidelines, composed by one of my colleagues John Baez (found at [url]http://math.ucr.edu/home/baez/crackpot.html[/url]). A non-crackpot will be able to realize which of the listed items applies to this thread, and will be able to decide how to go about reducing one's score.

Good luck.[/QUOTE]

I reckon he's on about 50 points.

 rogue 2015-10-24 13:32

I have already mentioned that I am quite willing to disclose my theorem in confidence along with the mathematical proof that it is true to any party who would be willing to assist me and has the resources to generate and run the code to produce prize winning primes. I'm just not going to post it on the open forum.
The following is not relevant to your post.[/QUOTE]

Even if you do not know how to program, I would think you could produce some relatively small prime numbers by hand since you know the formulae used to generate them.

 R.D. Silverman 2015-10-24 14:45

[QUOTE=a1call;413531]As mentioned I am hoping to submit my theorems for publication at some point, so I am not going to disclose them here in the open.

[/QUOTE]

Crank behavior.

 R.D. Silverman 2015-10-24 14:47

[QUOTE=a1call;413535]Hello [B]alpertron[/B],
I am aware of the proof for impossibility of regular as well as irregular polynomials generating prime numbers for all values of n.
However there are no proofs that other formulas will fail as well. An example would be Mills' formula, which is generally accepted to generate primes if the constant can be calculated.
[/QUOTE]

Which it can't.

 Mark Rose 2015-10-24 14:52

I have already mentioned that I am quite willing to disclose my theorem in confidence along with the mathematical proof that it is true to any party who would be willing to assist me and has the resources to generate and run the code to produce prize winning primes. I'm just not going to post it on the open forum.
The following is not relevant to your post.[/QUOTE]

I am not one of the resident math heads, so I have no business there. However, I am curious if you have done any algorithmic runtime analysis, e.g. how many individual calculations are required for finding a prime of a desired size. That number will determine if there is a realistic possibility of completing the algorithm in a reasonable time. As a mathematician you should be able to express this number as a formula. Show how many additions, subtractions, multiplications, divisions, etc., there are.

Afterwards, the next step would be breaking down those individual calculations into to small chunks that a computer is capable of executing. There are many known algorithms for that depending on the calculation, but they may also take a very long time to run.

Only if the required run time is small enough would a sane person begin to program. I think coming up with that formula would be the first step in showing you have something without revealing the exact details, plus let a programmer know if it's possible to actually finish the calculations in a lifetime.

 R.D. Silverman 2015-10-24 14:55

[QUOTE=a1call;413537]I only mentioned Mills' formula to point out formulas can generate all primes and there is no proof that no formula will do so. Not knowing the constant is irrelevant to the the fact that there is no proof that there can be no formula that can generate all primes.
[/QUOTE]

Idiot. "no proof that there can be no formula". Double negative.

Such formulae are well known. See, e.g. Paulo Ribenboim's book.
But they are useless for computational purposes.

Stop making ridiculous claims that you can not support. You are exhibiting classic crank behavior.

 a1call 2015-10-24 15:27

To the party who sent me a private message.
Message received. I leave in Eastern time zone. I will reply to your message later today, likely in the evening.
Thank you.

 a1call 2015-10-24 16:22

[QUOTE=Mark Rose;413629]I am not one of the resident math heads, so I [SUP][/SUP]have no business there. However, I am curious if you have done any algorithmic runtime analysis, e.g. how many individual calculations are required for finding a prime of a desired size. That number will determine if there is a realistic possibility of completing the algorithm in a reasonable time. As a mathematician you should be able to express this number as a formula. Show how many additions, subtractions, multiplications, divisions, etc., there are.

Afterwards, the next step would be breaking down those individual calculations into to small chunks that a computer is capable of executing. There are many known algorithms for that depending on the calculation, but they may also take a very long time to run.

Only if the required run time is small enough would a sane person begin to program. I think coming up with that formula would be the first step in showing you have something without revealing the exact details, plus let a programmer know if it's possible to actually finish the calculations in a lifetime.[/QUOTE]

I have not done any calculations for the run time. However for the sake of argument, suppose that there is a mathematical expression made of numbers and mathematical operators (example: 2 + 3) that is guaranteed to be a prime if it is less than 10[SUP]10000000000[/SUP]. Then you won't need to try and calculate every digit of the mathematical expression. A scientific notation form it would be enough to show that it is smaller than 10[SUP]10000000000[/SUP]. Still when you are talking about a billion+ digits the expression will be lengthy and run time long. But based on an educated guess it would still be quicker than what already has been done with relatively smaller large primes.
But that's just a guesstimate.

 Gordon 2015-10-24 17:39

[QUOTE=a1call;413638]I have not done any calculations for the run time. However for the sake of argument, suppose that there is a mathematical expression made of numbers and mathematical operators (example: 2 + 3) that is guaranteed to be a prime if it is less than 10[SUP]10000000000[/SUP]. Then you won't need to try and calculate every digit of the mathematical expression. A scientific notation form it would be enough to show that it is smaller than 10[SUP]10000000000[/SUP. Still when you are talking about a billion+ digits the expression will be lengthy and run time long. But based on an educated guess it would still be quicker than what already has been done with relatively smaller large primes.
But that's just a guesstimate.[/QUOTE]

As per the CEMPLLA charlatan, it's time to

[SIZE="5"]PUT UP OR PUSH OFF[/SIZE]

I call this a steaming pile of :poop:

 alpertron 2015-10-24 17:52

[QUOTE=a1call;413638]I have not done any calculations for the run time. However for the sake of argument, suppose that there is a mathematical expression made of numbers and mathematical operators (example: 2 + 3) that is guaranteed to be a prime if it is less than 10[SUP]10000000000[/SUP]. Then you won't need to try and calculate every digit of the mathematical expression. A scientific notation form it would be enough to show that it is smaller than 10[SUP]10000000000[/SUP. Still when you are talking about a billion+ digits the expression will be lengthy and run time long. But based on an educated guess it would still be quicker than what already has been done with relatively smaller large primes.
But that's just a guesstimate.[/QUOTE]
From this text I highly doubt that you will find someone to program your algorithm, except if you pay his/her services in advance.

 science_man_88 2015-10-24 19:45

[QUOTE=alpertron;413648]From this text I highly doubt that you will find someone to program your algorithm, except if you pay his/her services in advance.[/QUOTE]

Too late, but it's not really the newest idea. Or the fastest.edit never mind that pm was a test of my programming skills.

 VBCurtis 2015-10-24 20:06

[QUOTE=a1call;413638]I have not done any calculations for the run time. However for the sake of argument, suppose that there is a mathematical expression made of numbers and mathematical operators (example: 2 + 3) that is guaranteed to be a prime if it is less than 10[SUP]10000000000[/SUP]. Then you won't need to try and calculate every digit of the mathematical expression. A scientific notation form it would be enough to show that it is smaller than 10[SUP]10000000000[/SUP. Still when you are talking about a billion+ digits the expression will be lengthy and run time long. But based on an educated guess it would still be quicker than what already has been done with relatively smaller large primes.
But that's just a guesstimate.[/QUOTE]

Do. It. Produce small primes. 20 digits with pencil and paper, use pari/wolfram to check your output. Your "educated guess" is uneducated until you demonstrate otherwise. Find a prime of length 100 digits, by hand or by wolfram alpha or whatever via your algorithm. To find one of 1000 digits, the algorithm should take 1000 times longer. Each zero you add for digit length, 1000 times longer to find a prime. How many zeroes longer is 1 billion digits?

My educated guess is that your method would take longer than our lifetime to calculate an actual 1 million digit prime. Your claims so far amount to "I have a formula, but I don't know how complicated it is for big numbers. Computers are fast, so I just need a programmer to make my formula on a computer, and it'll turn out primes fast. Easy!"

 a1call 2015-10-24 20:06

[QUOTE=science_man_88;413657]Too late, but it's not really the newest idea. Or the fastest.edit never mind that pm was a test of my programming skills.[/QUOTE]

Not to mention elementary school arithmetic.

 alpertron 2015-10-25 12:17

[QUOTE=VBCurtis;413659]Do. It. Produce small primes. 20 digits with pencil and paper, use pari/wolfram to check your output. Your "educated guess" is uneducated until you demonstrate otherwise. Find a prime of length 100 digits, by hand or by wolfram alpha or whatever via your algorithm. To find one of 1000 digits, the algorithm should take 1000 times longer. Each zero you add for digit length, 1000 times longer to find a prime. How many zeroes longer is 1 billion digits?

My educated guess is that your method would take longer than our lifetime to calculate an actual 1 million digit prime. Your claims so far amount to "I have a formula, but I don't know how complicated it is for big numbers. Computers are fast, so I just need a programmer to make my formula on a computer, and it'll turn out primes fast. Easy!"[/QUOTE]

If the method produced only prime numbers as the OP claims, there would be no need to check the output for primality. So the method could run a lot faster than O(n[SUP]3[/SUP]). Anyway, it appears that this is material for a Math-fiction book.

 a1call 2015-10-26 00:12

Hi,
Since someone let the cat out of the bag (with good intentions no doubt) I might as well let it out properly and 1st hand.
However, the following statement is likely to be overlooked by a few members and in order of not having to repeat myself, please forgive the text format:

[SIZE=5][B][COLOR=Red]The following is not what I had in mind when I decided to tackle the one-billion+ prime challenge. That theorem and its associated approach is still safe and will only be disclosed to a party with the right computing credentials which would be willing to assist me in this endeavor.
[/COLOR][/B][/SIZE]
Anyone who is not pleased with that then, though.

One more note: This is a first draft of the proof and I have not proofread it. So should you find an i not dotted or a t not crossed, then good for you. A real mathematician would not need a proof and would instantly see that the statement is true (I know there are a few of them around).

[COLOR=#2E74B5][FONT=&quot]Theorem 1: [/FONT][/COLOR]
[FONT=Calibri]For the set [/FONT][B][FONT=&quot]A[/FONT][/B][FONT=Calibri] of [B][I]n[/I][/B] [U]consecutive[/U] prime numbers staring from [B]2[/B] and ending at [B]Pn[/B].[/FONT]
[FONT=Calibri]Let:[/FONT]
[B][FONT=&quot]B[/FONT][/B][B][FONT=&quot]⊂[/FONT][/B][B][FONT=&quot]A &[/FONT][/B][FONT=&quot] [B]C=A-B[/B][/FONT]
[FONT=Calibri] [/FONT]
[FONT=Calibri]Let the number [B]b[/B] be equal to multiples of any-integer-power greater-than [B]0[/B] of all-the-elements of [/FONT][B][FONT=&quot]B[/FONT][/B][FONT=Calibri].[/FONT]
[FONT=Calibri] [/FONT]
[FONT=Calibri]Let the number [B]c[/B] be equal to multiples of any-integer-power greater-than [B]0[/B] of all-the-elements of [/FONT][B][FONT=&quot]C[/FONT][/B][FONT=Calibri].[/FONT]
[FONT=Calibri] [/FONT]
[FONT=Calibri]Then [B]d = [/B][/FONT][B]|±[/B][B][FONT=Calibri]b[/FONT]±[/B][B][FONT=Calibri]c[/FONT]|[/B] [FONT=Calibri] is a [B][U]prime number[/U],[/B][/FONT]
[B][FONT=&quot]∀[/FONT][/B][B][FONT=Calibri]d: d < Pn2[/FONT][/B][FONT=Calibri] [/FONT]
[B][FONT=&quot]Proof:[/FONT][/B]

[B][FONT=Calibri]d[/FONT][/B][FONT=Calibri] is not divisible by any elements of [/FONT][B][FONT=&quot]A[/FONT][/B][FONT=Calibri], because [/FONT]
[B][I][FONT=Calibri](I) [/FONT][/I][/B][FONT=Calibri]if there are any [/FONT][B][I]a [/I][/B][I]such that[/I][FONT=Calibri]:[/FONT]
[B][I] a [/I][/B][B][FONT=&quot]∈[/FONT][/B][B][FONT=&quot] A &[/FONT][/B][FONT=&quot] [B] ([/B][/FONT][B][I]a [/I][/B][B][FONT=&quot]∈[/FONT][/B][B][FONT=&quot] B [/FONT][/B][B][FONT=&quot]⊕[/FONT][/B][B][FONT=&quot] [/FONT][I]a [/I][/B][B][FONT=&quot]∈[/FONT][/B][B][FONT=&quot] B) &[/FONT][/B][FONT=&quot] [B] [/B][/FONT][B][I]a[/I][/B][B][FONT=&quot][I]∣[/I][/FONT][/B][B][FONT=Calibri]d [/FONT][/B][B][FONT=&quot]⇒[/FONT][/B][B][FONT=Calibri] ( d/[/FONT][I]a[/I][I] = m & m [/I][/B][B][FONT=&quot]∈ ℤ)[/FONT][I][/I][/B]
[I]Then[/I]
[B][FONT=Calibri]d/[/FONT][I]a[/I][I] = m [/I][/B][B][FONT=&quot]⇒ [/FONT]|±[/B][B][FONT=Calibri]b[/FONT]±[/B][B][FONT=Calibri]c[/FONT]|[/B][B][FONT=Calibri]/[/FONT][I]a[/I][I] = m [/I][/B][B][FONT=&quot]⇒ [/FONT]|[/B][B][FONT=Calibri]b[/FONT]|/[I]a [/I] ± |[/B][B][FONT=Calibri]c[/FONT]|[/B][B][FONT=Calibri]/[/FONT][I]a[/I][I] = m [/I][/B]
[B][FONT=&quot] [/FONT][/B]
[B][I][FONT=&quot](ii) [/FONT][/I][/B][B][FONT=&quot]∵[/FONT][/B][B][FONT=&quot] ([/FONT][I]a [/I][/B][B][FONT=&quot]∈[/FONT][/B][B][FONT=&quot] B [/FONT][/B][B][FONT=&quot]⊕[/FONT][/B][B][FONT=&quot] [/FONT][I]a [/I][/B][B][FONT=&quot]∈[/FONT][/B][B][FONT=&quot] C) [/FONT][/B][FONT=&quot]∴ [B]([/B][/FONT][B]|[/B][B][FONT=Calibri]b[/FONT]|/[I] a [/I][/B][B][FONT=&quot]∈ ℤ[/FONT][/B][B][FONT=&quot] [/FONT][/B][B][FONT=&quot]⊕ [/FONT]|c|/[I] a [/I][/B][B][FONT=&quot]∈ ℤ[/FONT][/B][B][FONT=&quot] )[/FONT][/B]
[B][FONT=&quot] [/FONT][/B]
[FONT=&quot]Since [/FONT][B]|[/B][B][FONT=Calibri]b[/FONT]|/[I]a [/I] ± |[/B][B][FONT=Calibri]c[/FONT]|[/B][B][FONT=Calibri]/[/FONT][I]a [/I][/B][I]is an integer and either [/I][B]|[/B][B][FONT=Calibri]b[/FONT]|/[I]a [/I] [/B]or [B] |[/B][B][FONT=Calibri]c[/FONT]|[/B][B][FONT=Calibri]/[/FONT][I]a [/I][/B][I]is an integer, then the other has to be an integer since the sum of an integer number with a non integer number cannot be an integer. This conflicts with statement [B][I](ii)[/I][/B] which states that either [/I][B]|[/B][B][FONT=Calibri]b[/FONT]|/[I]a [/I][/B][I]or [/I][B]|c|/[I]a[/I][/B][I] is an integer exclusively. Thus statement [B][I](i)[/I][/B] is false.[/I]
[I]Since [/I][B][FONT=Calibri]d < Pn2[/FONT][/B][FONT=Calibri] and [B] d[/B] is not divisible by any prime number less than or equal to [B]Pn[/B] , then [B]d [/B]is a [B]prime number[/B].[/FONT]
[FONT=&quot][I]∎[/I][/FONT][I][/I]

The following is the routine that I have forwarded to the 2 people who have offered to assist me.

[QUOTE]* Take any set S of [B]consecutive[/B] positive primes starting from 2 and ending at some Pn.
* Write a code routine to try either random combinations, or ordered trial combinations of [B]all of[/B] the above primes and generate a sum of the form z = a - b where a and b have no common prime factors
* a and b each, are multiplications of positive integer powers of any distinct and non empty subsets of A and B such that A + B = S
** Any sum z < Pn2 that your routine comes up with id's guaranteed to be a prime.

Here is a small integer example for clarification:
z = 13 x 11[SUP]2[/SUP] - 7[SUP]2[/SUP] x 5 x 3 x 2 = 103
Here S is the set of first consecutive primes from 2 to Pn = 13
A = {11,13}
B = {2,3,5,7}
Note: sets A and B do not need to be made of consecutive elements.
[/QUOTE]

Here is the thread on the Physics Forum:

Thank you to all for your time and replies.

 alpertron 2015-10-26 00:49

Although the method generates primes as expected, the minuend and subtrahend are almost as big as in the previous version. For more interesting ranges, you should subtract extremely huge numbers and the timing would be worse than trial division.

You could use modular arithmetic in order to speed up your algorithm, but again this will be worse than trial division. Why? The union of the sets A and B must include all prime numbers below n. So you need to perform about n/log(n) multiplications mod prime greater than n[SUP]2[/SUP]. So the number of steps is the same as the worst case of trial division. Notice also that to find a prime p<n[SUP]2[/SUP] first you will need to compute a prime larger than n[SUP]2[/SUP] in order to use it as the modulus. So again this is not useful at all.

1 Attachment(s)
Is this Phase [STRIKE]1[/STRIKE] 2 of [STRIKE][URL="https://en.wikipedia.org/wiki/We%27re_Only_in_It_for_the_Money"]Lumpy Gravy[/URL][/STRIKE] [URL="http://www.mersenneforum.org/showthread.php?t=19507"]Kathegetes[/URL]? :smile:

 science_man_88 2015-10-26 01:11

so that wasn't just a test of my programming skills ? edit: is that better Batalov.

 Batalov 2015-10-26 01:16

[QUOTE=a1call;413772][code]* Take any set S of [B]consecutive[/B] positive primes starting from 2 and ending at some P[SUB]n[/SUB].
* ...
* ...
* Any sum z < P[SUB]n[/SUB]2 that your routine comes up with id's guaranteed to be a prime.
* PROFIT!!!!!!!!![/code][/QUOTE]
So, you are saying that for you method to work you need to store somewhere [B]all primes[/B] up to 10[SUP]500000000[/SUP], right?
Good luck with that.
This universe is not equipped to store all primes up to 10[SUP]1000[/SUP], is it?

 Batalov 2015-10-26 01:22

[QUOTE=science_man_88;413777]so that wasn't just a test of my programming skills ?[/QUOTE]
A rhetorical question if there ever was one.

[SPOILER]Not seeing your messages saves so much of my page space!
You really needed to quote the whole message to ask [I]that[/I]?[/SPOILER]

 science_man_88 2015-10-26 01:27

[QUOTE=Batalov;413779]A rhetorical question if there ever was one.

[SPOILER]Not seeing your messages saves so much of my page space!
You really needed to quote the whole message to ask [I]that[/I]?[/SPOILER][/QUOTE]

the reason I asked it because they very slightly mentioned something in PM that was supposed to speed it up at very least.

 a1call 2015-10-26 01:31

[QUOTE=alpertron;413775]Although the method generates primes as expected, the minuend and subtrahend are almost as big as in the previous version. For more interesting ranges, you should subtract extremely huge numbers and the timing would be worse than trial division.

You could use modular arithmetic in order to speed up your algorithm, but again this will be worse than trial division. Why? The union of the sets A and B must include all prime numbers below n. So you need to perform about n/log(n) multiplications mod prime greater than n[SUP]2[/SUP]. So the number of steps is the same as the worst case of trial division. Notice also that to find a prime p<n[SUP]2[/SUP] first you will need to compute a prime larger than n[SUP]2[/SUP] in order to use it as the modulus. So again this is not useful at all.[/QUOTE]
I agree
I don't think it is necessarily worse than trial division in general though. There should be a medium range where less trials than trial division would result in primes specially if you write the routine intelligently by keeping the sums as low as possible but for very large primes the sums will diverge very rapidly.
You don't really need to calculate the base primes either. you can use the theorem to come up with solutions to that such as using double factorials of a composite odd integer, rather than primes multiplied. the double factorial can be calculated using product of sequence formula.
To further keep the sum from diverging you can factor out large number of known primes.
But all this would not do for a billion plus digits. As I mentioned before there are better approaches to this.
BTW, thank you for being one of the few intelligent posters to this thread.

 a1call 2015-10-26 01:34

[QUOTE=Batalov;413778]So, you are saying that for you method to work you need to store somewhere [B]all primes[/B] up to 10[SUP]500000000[/SUP], right?
Good luck with that.
This universe is not equipped to store all primes up to 10[SUP]1000[/SUP], is it?[/QUOTE]
Please read the red comment in my earlier post. I thought it was distinct enough. Obviously I was wrong.

 Batalov 2015-10-26 02:05

[QUOTE=a1call;413782]Obviously I was wrong.[/QUOTE]
Good, we are in agreement then.

 a1call 2015-10-26 02:31

[QUOTE=Batalov;413783]Good, we are in agreement then.[/QUOTE]
There are 3 types of people in the world. There are those who can count, and there are those who can't.:smile:

 axn 2015-10-26 03:07

[QUOTE=a1call;413781]But all this would not do for a billion plus digits.[/QUOTE]

Understatement of the century. Your method will not scale to 20 digit primes, never mind a billion digits.

 danaj 2015-10-26 05:42

This makes me think of Maurer or Shawe-Taylor methods for generating proven primes. There we get to double or triple the bits every round. One could do something similar with other BLS75 theorems (Maurer's algorithm can be seen as a case of theorem 3) or even ECPP. Just build up the proof backwards to get larger and larger numbers. It makes nice large proven primes, but I seriously doubt it would scale well to millions of digits.

 ewmayer 2015-10-26 07:28

[QUOTE=a1call;413772][COLOR=#2E74B5][FONT=&quot]Theorem 1: [/FONT][/COLOR]
[FONT=Calibri]For the set [/FONT][B][FONT=&quot]A[/FONT][/B][FONT=Calibri] of [B][I]n[/I][/B] [U]consecutive[/U] prime numbers staring from [B]2[/B] and ending at [B]Pn[/B].[/FONT]
[FONT=Calibri]Let:[/FONT]
[B][FONT=&quot]B[/FONT][/B][B][FONT=&quot]⊂[/FONT][/B][B][FONT=&quot]A &[/FONT][/B][FONT=&quot] [B]C=A-B[/B][/FONT]
[FONT=Calibri] [/FONT]
[FONT=Calibri]Let the number [B]b[/B] be equal to multiples of any-integer-power greater-than [B]0[/B] of all-the-elements of [/FONT][B][FONT=&quot]B[/FONT][/B][FONT=Calibri].[/FONT]
[FONT=Calibri] [/FONT]
[FONT=Calibri]Let the number [B]c[/B] be equal to multiples of any-integer-power greater-than [B]0[/B] of all-the-elements of [/FONT][B][FONT=&quot]C[/FONT][/B][FONT=Calibri].[/FONT]
[FONT=Calibri] [/FONT]
[FONT=Calibri]Then [B]d = [/B][/FONT][B]|±[/B][B][FONT=Calibri]b[/FONT]±[/B][B][FONT=Calibri]c[/FONT]|[/B] [FONT=Calibri] is a [B][U]prime number[/U],[/B][/FONT][/QUOTE]

False. Here is a pair of simple counterexamples:

Counter #1: A = {2,3}, B = 2, C = 3. Let b = 2^1, c = 3^3. Then b+c = 29 is prime, but -b+c = 25 is not.

Counter #2: A = {2,3,5,7,11}, B = 2, C = {3,5,7,11}. Let b = 2^1, c = 3*5*7*11 = 1155. Then -b+c = 1153 is prime, but b+c = 1157 = 13*89 is not.

 LaurV 2015-10-26 07:39

[QUOTE=ewmayer;413801]False. Here is a pair of simple counterexamples:

Counter #1: A = {2,3}, B = 2, C = 3. Let b = 2^1, c = 3^3. Then b+c = 29 is prime, but -b+c = 25 is not.

Counter #2: A = {2,3,5,7,11}, B = 2, C = {3,5,7,11}. Let b = 2^1, c = 3*5*7*11 = 1155. Then -b+c = 1153 is prime, but b+c = 1157 = 13*89 is not.[/QUOTE]
Won't suffice, both are higher than n^2 (in the first case 9, second case 121). What he calls "Pn2". His theorem is true, but not useful to generate primes, as Serge said, it will need to store primes to 10^500M.

 axn 2015-10-26 07:48

[QUOTE=ewmayer;413801]False. Here is a pair of simple counterexamples:[/QUOTE]

You've accidentally left out a critical part of the theorem (because of poor typography on OP's part, mind you)

[QUOTE]Then d = |±b±c| is a prime number,
[COLOR="Red"]∀d: d < Pn2[/COLOR][/QUOTE]

 R.D. Silverman 2015-10-26 09:44

[QUOTE=Batalov;413778]So, you are saying that for you method to work you need to store somewhere [B]all primes[/B] up to 10[SUP]500000000[/SUP], right?
Good luck with that.
This universe is not equipped to store all primes up to 10[SUP]1000[/SUP], is it?[/QUOTE]

BTW, the idea of partitioning a set of primes into two sets and looking at combinations of products
is hardly new. See the paper "Primes at a Glance" by John Selfridge et.al.

 R.D. Silverman 2015-10-26 11:16

[QUOTE=LaurV;413802]Won't suffice, both are higher than n^2 (in the first case 9, second case 121). What he calls "Pn2". His theorem is true, but not useful to generate primes, as Serge said, it will need to store primes to 10^500M.[/QUOTE]

One also needs to look at the computational complexity of FINDING a partition that
satisfies the condition on d. It is non-trivial.

BTW, a similar scheme was looked at and rejected a number of years ago in this very forum.....

 R.D. Silverman 2015-10-26 14:51

[QUOTE=R.D. Silverman;413811]One also needs to look at the computational complexity of FINDING a partition that
satisfies the condition on d. It is non-trivial.

BTW, a similar scheme was looked at and rejected a number of years ago in this very forum.....[/QUOTE]

I see that a couple of my posts have been deleted.

However, doing so exemplifies the typical hypocrisy of this group, since whoever did it allowed the
following comment from the crank who started this thread

"BTW, thank you for being one of the few intelligent posters to this thread. "

in response to a (correct!) comment from alpertron.

 R.D. Silverman 2015-10-26 14:55

[QUOTE=axn;413803]You've accidentally left out a critical part of the theorem (because of poor typography on OP's part, mind you)[/QUOTE]

Yes.

However this correct observation also shows another deficiency in the OP's 'algorithm'.

His method fails to present a method for partitioning the set of primes such that d HAS
the required property.....

Can you say "combinatorial search"?????

 ewmayer 2015-10-26 18:52

[QUOTE=LaurV;413802]Won't suffice, both are higher than n^2 (in the first case 9, second case 121). What he calls "Pn2". His theorem is true, but not useful to generate primes, as Serge said, it will need to store primes to 10^500M.[/QUOTE]

Ah, gotcha (thx to axn, as well). So we're left with another 'mathematically true, but practically useless' scheme of the kinds discussed in e.g. Crandall & Pomerance or any similar NT reference which includes computational-feasibility analyses.

 jasong 2015-10-28 23:30

I understand very little of this thread, but I think it would be helpful for the people who still have a level head to review the thread on the other forum that led to this one. I know next to nothing about number theory, but at the bottom of the first page of that thread is an interesting statement seeming to vouch for a1call's credentials. Maybe it's faked, I have no idea, but it's something to consider.

 a1call 2015-10-28 23:58

the credentials are based on the Theorem 1 That I disclosed to one of the members. That's what the vouch is about. The same theorem has since been posted here and has been judged useless for the most part on this board.
The thread on the other board has progressed further on the topic though. Thank you for note [B]jasong[/B].
If anyone is interested in my credentials I am mechanical designer by trade (specializing in Parametric CAD design) but have had computer maintenance and programming as well electronic design experience through my decades of work experience.
I am a semi-regular member on the cosmoquest board which might be an indication of my interests.

My CV is available for all to see here:

 R.D. Silverman 2015-10-29 00:15

[QUOTE=a1call;414139]the credentials are based on the Theorem 1 That I disclosed to one of the members. That's what the vouch is about. The same theorem has since been posted here and has been judged useless for the most part on this board.
The thread on the other board has progressed further on the topic though. Thank you for note [B]jasong[/B].
If anyone is interested in my credentials I am mechanical designer by trade (specializing in Parametric CAD design) but have had computer maintenance and programming as well electronic design experience through my decades of work experience.
I am a semi-regular member on the cosmoquest board which might be an indication of my interests.

My CV is available for all to see here:

Keeps piling on the crankometer points.......

 ewmayer 2015-10-29 00:39

[QUOTE=a1call;414139]My CV is available for all to see here:[/QUOTE]

I think I speak for just about everyone here when I say that no one cares about your bragsheet credentials, only whether your proposed method is potentially useful. The latter point has been settled to the satisfaction of everyone who has replied to this thread and is also not a known crank or ignoramus. Time for you to shut up and go read any of the references which have been mentioned, about various other 'prime finding' methods with similar properties to yours. Or add 'too credentialed to ever again undertake learning anything new' to your CV, if you prefer.

 LaurV 2015-10-29 07:48

@OP: Man, with so much programming skill, why the fruit you need somebody to program the algorithm for you? Large integer and FFT float libraries are plenty, for free, you just "#include <bhahblah>" and start computing.

P.S. I am in full agreement with the two guys who posted just before.

 a1call 2015-10-31 20:44

The following 183 digit prime was found using formulation using the Theorem 1, without scripting and programming.
Is that of any significance considering the method?
Are there any other formulas which can give comparable results without programming?

The number of digits is about a dozen less than the maximum of what the free version of Wolfram Alpha accepts.

268247424057311445389468276509855422892624146761442207989329055956776521156436821116123624436462260510842892838582894073662704750945426649505938377042214898386145890456554863200575291

[URL]http://www.wolframalpha.com/input/?i=268247424057311445389468276509855422892624146761442207989329055956776521156436821116123624436462260510842892838582894073662704750945426649505938377042214898386145890456554863200575291+prime%3F[/URL]

Credits to Wolfram Alpha for doing the arithmetic.

Thank you for your time and replies.

 Batalov 2015-10-31 21:07

[QUOTE=a1call;414450]The following 183 digit prime was found using formulation using the Theorem 1, without scripting and programming.
Is that of any significance considering the method?
[/QUOTE]
Nope. You have shown no proof that it was in fact found by "this method", "without scripting and programming"
[QUOTE=a1call;414450]
Are there any other formulas which can give comparable results without programming?
[/QUOTE]
Of course, yes.
Press [URL="http://factordb.com/index.php?query=1777171*2^n-1&use=n&n=800&VP=on&VC=on&EV=on&OD=on&PR=on&PRP=on&U=on&perpage=20&format=1&sent=Show"]here[/URL] and you will find a few primes that were not known a few seconds ago, because nobody cared for primes this small.
Here is the link, spelled out:
1777171*2^2369-1
1777171*2^2519-1
1777171*2^5841-1
1777171*2^7137-1
are prime, too, and are a little larger.
And just as many with almost [I]any random[/I] k value (above, k=1777171, -- a random number that I pulled out of my (r)ear).

 a1call 2015-10-31 21:22

[/B]What is the largest number of digits that can be generated using the tool that you linked to?

Any idea on the maximum number of input digits for the Wolfram Alpha Pro?

 Batalov 2015-10-31 21:32

Factordb is a (free) webservice that its owner periodically adjusts and tunes. The limits may be variable, but as this link shows, [URL="http://factordb.com/index.php?query=%2810^10000001-1%29%2F9"]10 million digits[/URL] are not forbidden by size: http://factordb.com/index.php?query=%2810^10000001-1%29%2F9 (iirc, the limits were lower before, perhaps at 1 million digits)

There is no one single limit. [URL="http://factordb.com/res.php"]There are limits[/URL]: by size, by computation time that the server spend on "you" (which it defines by your IP address), on a number of queries that you can run in any given hour, etc. Once any of these are exceeded, the server will let you know.

 a1call 2015-10-31 21:44

Thank you, Can't get the 1st link but it doesn't matter. 10^7 is just too big, I doubt it if any online/offline calculator, free or pro can do arithmetic in that range and attest to the evaluated number being prime.
Would appreciate if someone let's me know if there is though.

 Batalov 2015-10-31 21:49

If we also consider the deeper level of your question (even if you didn't mean it) --

The tool(s) for searching for large Riesel primes are hidden behind the factordb.com facade. The largest currently known Riesel prime is at the moment has 3,580,969 decimal digits, and as for its cousin with the '+' sign (the Proth primes), the largest one has 3,918,990 digits and the next ones can be soon found in the area of above 9 million digits. These searches are limited only by time, not by tool's limitations as it were (those technical limits are comfortably far for years to come).

 danaj 2015-10-31 23:30

Both gwnum and GMP can do arithmetic on million digit numbers, and there is one or more open source or freely available LLR code using each library. gwnum is much faster at that size, but GMP (or Pari) could certainly be used to double check something if it was desired.

 a1call 2015-10-31 23:59

Thank you [B]danaj[/B],

I will look into your suggestions. I am not a linux guru though have used it fairly enough in the past. I have installed PARI/gp on an Ubuntu virtual machine. Not sure how to run it though. It seems to be the engine behind Mathomatic but last time I checked (very superficially) it seemed to give the message the integer is too long or something.
Anywho Thank you for the suggestions.

 jasong 2015-11-04 04:26

I'm not an expert at this by any means, but I think you need to install and figure out the "libraries" that have been suggested in one or two posts of this thread.

I put quotes around libraries because I'm not certain I'm using the term correctly. I'm post-noob(amateur?) when it comes to Linux, but it's been years.

off-topic: Been intending to buy a cheap Linux box and only use my Win 10 pc for gaming. Haven't gotten around to it, though.

 Xyzzy 2015-11-04 12:26

[QUOTE=jasong;414901]off-topic: Been intending to buy a cheap Linux box and only use my Win 10 pc for gaming. Haven't gotten around to it, though.[/QUOTE][URL]https://www.debian.org/CD/live/[/URL]

:mike:

 a1call 2015-11-05 02:45

Thank You [B]jasong [/B]and [B]Xyzzy[/B],

I think I found a path of less resistance than Linux (for me).

[QUOTE=rogue;413493]Also, any number you find needs to be proven prime with other software. pfgw will be able to do a PRP test on anything, but there is no quick way to prove primality on most PRPs.

I suggest that you start smaller, about 1,000 decimal digits. If it is relatively easy to find PRPs of that size and they can be proven prime using Primo if pfgw can't handle them. You will need to show that all numbers of that size that you generate with your code are both PRP and prime before anyone takes you seriously.[/QUOTE]

The following [B]1073 digit prime[/B] was found using Theorem 2 as a prime candidate (Not converging) and limited programming (loops are limited by time on free accounts of Wolfram Development Platform Beta) and verified by this tool (Thank you MFB) in 18m 21s:
[URL]http://www.alpertron.com.ar/ECM.HTM[/URL]

Not meant as a stepping stone to Billion digits, but I am hooked on finding primes:

[CODE]17301304951032760979391540193063942238627682268484375059657797614141421418495209718498044122698756352618538497495820651532862095140913836791275751603224329708365511386845438457428416851015999781499739435257993030575395521148456370126973589861926447884890905040895142783915003661035159229205944992835893864590602509263424611416123644256541090152154512730215021789569325707624767626996064050083616852868906332140134344237134396002824248209935006343957263114330913889773184009113859258418819604265270733786352915204992280741674163394608327544357353928253505413942752531277381920544376012570452429112062991939767408636679110093897812817626397868615203488782193665960754503922109247702751732229582159545932429202012497327629174354607890117512658337229246677699256833499748867690239242308519052661350031566032280211872532743075445338450341469721741259844914418473536208488402577491114597561265849781778899521612711411589991576446341769618521815120994972553526447111347234336226114001576307246794751766320656024207911756851820233499473255290178571719920249186095508547296580127621[/CODE]
ETA You will have to scroll right to see the whole number.

 danaj 2015-11-05 11:51

The nice thing about Maurer and Shawe-Taylor random prime generation is that they construct a primality certificate as they create the prime. The certificate is a chain of BLS theorem 3 or Pocklington steps respectively. 1073 digit primes [i]with certificates[/i] are produced in 2-6 seconds by my code, which is not particularly fast at this.

Standard random prime generation is a bit faster, but then leaves one having to do a proof, which was the problem with large primes -- our current general form methods are only computationally feasible to 30k digits or so. So of course your method would need to do something similar to the Maurer or Shawe-Taylor methods, where you have a solid theorem that proves that the larger number is prime if the smaller number is prime (or some other similar condition such as the appropriate variables of theorem 1 that allow its duplication).

 a1call 2015-11-05 17:03

[QUOTE=danaj;415011]The nice thing about Maurer and Shawe-Taylor random prime generation is that they construct a primality certificate as they create the prime. The certificate is a chain of BLS theorem 3 or Pocklington steps respectively. 1073 digit primes [i]with certificates[/i] are produced in 2-6 seconds by my code, which is not particularly fast at this.

Standard random prime generation is a bit faster, but then leaves one having to do a proof, which was the problem with large primes -- our current general form methods are only computationally feasible to 30k digits or so. So of course your method would need to do something similar to the Maurer or Shawe-Taylor methods, where you have a solid theorem that proves that the larger number is prime if the smaller number is prime (or some other similar condition such as the appropriate variables of theorem 1 that allow its duplication).[/QUOTE]

Your method is faster than mine which basically is a very short routine which takes in 2 relatively small variables (<100 in this case) that I have to try inputting manually due to free account limitation (no random function is used). A thereon such as theorem 1 is of value for finding primes even when it does not converge to less than the square since it can be used to construct routines which yield primes with astronomically higher probability than random trials. For example odd numbers are twice as likely to be primes than integers in general. Factor out divisible by 3s and you improve your odds substantially more.
As for billion digits, computation limitation is a big problem. So a mathematical approach is probably the practical approach.
For a very simplified example:
p=x!!-2^y , p<x^2
Can be easily shown/proven to have a solution with more than one billion decimal digits (or any other number of digits) which is guaranteed to be a prime.
However getting numeric solutions for x and y are virtually impossible.
My Thereon 1 and to a greater degree Theorem 2 (undisclosed so far) has a much more probable solution. Obviously my mathematical skills have not sufficed to find a solution yet. But I am convinced that such a solution is feasible given proper mathematical skills (much better than mine).

 science_man_88 2015-11-05 17:27

Your method is faster than mine which basically is a very short routine which takes in 2 relatively small variables (<100 in this case) that I have to try inputting manually due to free account limitation (no random function is used). A thereon such as theorem 1 is of value for finding primes even when it does not converge to less than the square .[/QUOTE]

product of prime -product of primes using all primes less than [TEX]p_{n} [/TEX] in only one place will be prime up to [TEX]({p_{n+1}})^2[/TEX]as I already told you based on it having no factor to divide out ( which you came to)

 a1call 2015-11-05 19:45

Regarding the simplified example on my reply 77, the double factorial must be of an odd number so for the sake of correctness:

p=(2x-1)!!-2^y , p<(2x-1)^2
For integers x and y.

 science_man_88 2015-11-05 20:45

[QUOTE=a1call;415060]Regarding the simplified example on my reply 77, the double factorial must be of an odd number so for the sake of correctness:

p=(2x-1)!!-2^y , p<(2x-1)^2
For integers x and y.[/QUOTE]

it's less than (nextprime(2x-1))^2 example find the numbers that are between 9 and 25 and don't divide by 2 3 answer 11,13, 17,19,23 because 10,12,14,16,18,20,22,and 24 all divide by 2 which our product sum does not, 15,and 21 both divide by 3 which our product sum can not.

 danaj 2015-11-05 23:33

[QUOTE=a1call;415039]Your method is faster than mine [...][/quote]Maybe -- it's hard to compare directly, as my code is in Perl calling GMP functions, while yours is in some Mathematica system. I'm sure the performance characteristics are very different. But it does give some idea of the time for existing methods that generate random proven primes.

[quote]A thereon such as theorem 1 is of value for finding primes even when it does not converge to less than the square since it can be used to construct routines which yield primes with astronomically higher probability than random trials. For example odd numbers are twice as likely to be primes than integers in general. Factor out divisible by 3s and you improve your odds substantially more.[/quote]

Checking for small factors is quite fast however. The main problem is typically that one is consuming randomness. This may be a non-issue (if we don't care about crypto or are using a very fast CSPRNG with high-delay reseeding), but it can be huge if we want good entropy on embedded or isolated devices without entropy hardware.

I recommend reading the paper: [URL="http://eprint.iacr.org/2011/481"]"Close to Uniform Prime Number Generation With Fewer Random Bits"[/URL] by Pierre-Alain Fouque and Mehdi Tibouchi, 2011. It gives a good overview of some earlier methods, then shows their technique. It is targeted to a different situation than your goal, but I think it gives a good understanding of current methods for random prime generation. They also point out how one can easily skip results with small divisors. My modified A1 algorithm of course doesn't generate evens, and skips anything with factors 3-19 with simple native integer calculations -- so constructing the large integer is only done when we know the result has no tiny factors.

Maurer's method will double or triple the number of bits at each step. Doubling is pretty common, using Pocklington or BLS theorem 3. Tripling is possible using BLS theorem 5 or similar. [URL="http://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf"]BLS75[/URL] theorem 3 says:[INDENT]Let N-1 = mp, where p is an odd prime such that 2p + 1 > sqrt(N). If there exists an a for which a^((N-1)/2) = -1 mod N, but a^(m/2) != -1 mod N, then N is prime.[/INDENT]So we work backwards, starting with a small prime [i]p[/i] verified with some deterministic method (e.g. trial division, deterministic M-R, or BPSW). Then select a random m of size such that the 2p+1> sqrt(N) holds, and N isn't obviously composite (simple divisibility checks). At this point I think it's best to do a strong pseudoprime test on N -- one modular power will verify whether we should proceed. At the sizes we're looking at, if it succeeds then we almost certainly pass the next step. Search for an [i]a[/i] that works with the final two conditions, trying just a few values (e.g. 3 to 5) -- if we found one, then N is prime, otherwise go back to selecting a different random m. It should be clear how we can do this repeatedly to build up N to our desired size.

Shawe-Taylor does a similar process. My code does the pedantic implementation from FIPS 186-4, which defines very specific methods for using SHA256 to generate a pseudo-random stream from the seed and how to construct the candidates. It also defines the method for searching for [i]a[/i] values and uses the Pocklington test.

One thing I did with my implementation of both was add a BPSW test before returning N. With a correct implementation this is a waste of time, but I've seen a different implementation goof up one of the conditions and return composites in very rare cases. The extra BPSW test is just there to catch anything like that (I'd much rather than the code assert than return a composite, and I'm willing to spend a tiny bit of extra time on it). For a billion digits you wouldn't want that :). There are other modifications one could make to speed things up for generating a large prime quickly vs. a random prime. Maurer's method, for instance, doesn't always use the largest m possible, as it is trying to take into account the factor distribution of uniformly random N-1 values, hence often chooses something smaller.

The main problem is that as the size grows, we spend more and more time selecting random [i]m[/i] values that don't result in N being prime. This could be sped up some, e.g. (I haven't implemented it) we could sieve N-1=(m+j)p for some range of j, which would be faster than choosing random [i]m[/i] and checking each one for divisibility.

[quote]My Thereon 1 and to a greater degree Theorem 2 (undisclosed so far) has a much more probable solution. Obviously my mathematical skills have not sufficed to find a solution yet. But I am convinced that such a solution is feasible given proper mathematical skills (much better than mine).[/QUOTE]Definitely keep working on it. I do think it's good to get at least some idea of previous work in the field. Even if it doesn't result in a billion digit prime, another method for random proven primes sounds interesting.

 a1call 2015-11-06 00:47

Thank you [B]danaj[/B] for your expert and kind opinion. I will look into your recommended reads but doubt very much that my mathematical background is advanced enough to get understand/get much out of it.

Now for my new hobby of finding primes this is the largest so far.

A [B]2947 digit prime[/B]:

[CODE]1805466980889895444152083705580546438904586504024677600165535188575543429685794077960505989625214808524915116303899705491315603164094343044084813795581043757530995487552235487902523723086567740452893727595719880372980597935541450742314924709084464477805706347801215564892828477742072237573906563782370272100579388686003721262122865977590597671663276817313957626949815633164020079618129756124758514473258952668713086668728327275687891046096802123432511845769670152445319814829069235728684165231695321332342334367088705269590536527660092629353864957805226857372134492239182271773319271671060039879398708305623924423944843161074165034154548690879881017033937390305637610815820841838308524829591690956013832210832989143539340531227350566275290758441812554637924971005663040725834078658718911848208299986651450324251660389891917952141142210279447598049220945655658626052995732959245011919822884830765020739809511578315007267171708637682291056185797473317747764366344004828507106666721146537504910198413255887344019105030885272695106644022148170279957406811811911585778607600739191941607919630180234280031608973517046509793449110316428492468696779825270101530626635344218034017307575001966882491611934891738871974963517180137793058469000240528839225740256912452059160288057505444198500439633240583962147605681672854210974037353231750759224515933944959499070415928622085379698744189526577111698223307107665376762465818342167706880502158694017253486016700231248897694374400855441474197730980037468658876592266138720858442852935844690619167220560914289672460090283731271531544337770738859857007393568030507020182480999526498540545600903227122621230800437089885978984230703506985324720816164021613478285374762602855643139663257847197959455588902981428173235460646940557633065072026465549146471366173033516852539147433182479114301404886920957104251678805504412494200796533347564550660712562917738939205873028504412308575509495761954814647711657139410849691685321052885903832951506346892246167734326681830599628039736287055861356443181022534485795392105080607228795912012553024445415098038410720044479890661532850673130219375779899531376107672518236277402316679487610396175030330672991287042582145245368628067527664022783999883065155230024645864740144778843763548011487620955941889185683824851653206897896900747451378467342402311606349922692725297663302384680026620955340896805371466046084505923777439953896738500215013385523653896095796144761307282761834587963060324115970111770272476498848789114830467810498345867446037192452020756530749047624747739018468419463872849159279940652772445668411860820516407239704696025418086495779571719406376523548257847350367035686315656048518163977035026758194250214340115912569626831728654997932815440375880817644385932476040941555231541267305721707269170287184587787567356129062681652484241589553874347773466273391056360920384479015168760367513723387661000831706805133731080182032638806917395759284450399866107468081950321[/CODE]Is there a number of digits below a million that I can come up with that would qualify moving this thread out of the Crackpot section?

 axn 2015-11-06 04:22

[QUOTE=a1call;415087]Is there a number of digits below a million that I can come up with that would qualify moving this thread out of the Crackpot section?[/QUOTE]

You can start by finding a Top 5000 prime. Currently the entry criteria is 388341 digits ([url]http://primes.utm.edu/primes/status.php[/url]).

 Batalov 2015-11-06 04:39

Yep, that will work.

 axn 2015-11-06 05:39

[QUOTE=axn;415099]You can start by finding a Top 5000 prime. Currently the entry criteria is 388341 digits ([url]http://primes.utm.edu/primes/status.php[/url]).[/QUOTE]

[QUOTE=Batalov;415101]Yep, that will work.[/QUOTE]

A more aesthetically pleasing target is to beat GIMPS's 1st ([url]http://primes.utm.edu/primes/page.php?id=5[/url]), which, at 420921 digits is a mere 10% bigger. This was the #1 prime in 1996, and is very much dear and near to this forum :smile:

 a1call 2015-11-06 18:52

Thank you for the reply [B]axn.
[/B]The 1073 digit was checked in 18 minutes on a windows 10 desktop with this tool:

[url]http://www.alpertron.com.ar/ECM.HTM[/url]

The 2947 digit is still running at more than 15 hours. A few more digits make a big difference and prove the above tool not appropriate for large primes.

Fortunately the Wolfram server can confirm both in seconds.

 R.D. Silverman 2015-11-06 18:54

[QUOTE=a1call;415148]Thank you for the reply [B]axn.
[/B]The 1073 digit was checked in 18 minutes on a windows 10 desktop with this tool:

[url]http://www.alpertron.com.ar/ECM.HTM[/url]

The 2947 digit is still running at more than 15 hours. A few more digits make a big difference and prove the above tool not appropriate for large primes.

Fortunately the Wolfram server can confirm both in seconds.[/QUOTE]

??? Are you sure that the Wolfram server is yielding PROOF?

 danaj 2015-11-06 19:11

At 2947 digits, you'll probably want to use Primo (which means a Linux machine or VM). Pari's isprime will work as well, but Primo is probably noticeably faster and gives a progress indication. Pari/GP took 4.5 minutes on your 1073 digit number on my laptop. Using BPSW on the 2947 digit number takes under a second using Pari/GP or Perl/ntheory.

Wolfram uses a BPSW variant for PrimeQ, not a proof. You'd have to use ProvablePrimeQ for a proof. Wolfram Alpha doesn't support that command so I'm not sure if your tool does or not. It returns what it claims is an ECPP certificate that its checker can parse.

 a1call 2015-11-06 19:33

1 Attachment(s)
Please see the attached screenshot along with the command documentation.
It takes less than 2 seconds.

 chalsall 2015-11-06 19:39

[QUOTE=a1call;415157]Please see the attached screenshot along with the command documentation.[/QUOTE]

What you are forgetting is empirical time is different than computational time.

 a1call 2015-11-06 19:42

Which means it actually takes a fraction of a second on the server, right or am I missing something.

 chalsall 2015-11-06 19:50

[QUOTE=a1call;415159]Which means it actually takes a fraction of a second on the server, right or am I missing something.[/QUOTE]

It means you are missing a lot!

Sure, in our modern age, we just "throw hardware at the problem". And that might make some sense. Machines and energy are cheap(ish). Programmers are expensive.

BUT... Some actually want to optimize the equations.

That also makes sense....

 science_man_88 2015-11-06 20:13

[QUOTE=a1call;415159]Which means it actually takes a fraction of a second on the server, right or am I missing something.[/QUOTE]

I think what is being pointed out is that:

this code takes 4 milliseconds for this single computation isn't necessarily useful ( though I do that a lot myself) because without knowing how the time scales people won't be sure if it's worth putting in the time it would take for other inputs for example two inputs a and b=2*a;

if for input of b we double the time then the algorithm may be linear time complexity, if it quadruples the time it may be exponential, if b=a^2 and time doubles then maybe the algorithm may be logarithmic. same with number of operations if you say this algorithm takes 4 operations okay is that 4 additions, 4 multiplications, 4 divisions ( divisions are typically slow for computations unless they use a way of dividing that doesn't use much if any actual dividing). that and that it takes time to display an answer.

 danaj 2015-11-07 00:20

The point is that you're comparing two [I]completely[/I] different operations.

PrimeQ is similar to Pari/GP's ispseudoprime, Perl/ntheory's is_prime, or mpz_prp's mpz_bpsw_prp (used by Python's gmpy 2.0). It runs very fast. It is a [B]probable prime[/B] test. Nobody really knows what the Wolfram / Mathematica implementation really is (Pinch noted their "Lucas test" was not what the rest of the world calls a Lucas test and was strictly weaker than what BPSW should use, but that was 22 years ago). BPSW is great test, but I'm not sure how it applies here. It's meaningless in the EFF challenges. I have an [URL="http://sti15.com/nt/primality.cgi"]old web page[/URL] that does similar tests, though not factoring. It runs on the slow web host server rather than the browser, so the proof size is pretty limited.

The test you're running with alpertron is a proof. APR-CL I believe (but could be wrong). That would be similar to Pari/GP's isprime, mpz_aprcl's mpz_aprcle, or FLINT's new APRCL code (not in master yet). Comparable to the ECPP methods of Primo or Perl/ntheory's is_provable_prime. They take massively longer to run than the probable prime test. A certificate (ECPP, Pratt, etc.) would work for EFF, but you can't just give a general form number of 1M digits to Primo and expect it to ever produce something. Hence the idea of building up the certificate, which at least isn't loony with today's resources (I was going to say practical, but that's stretching it).

 a1call 2015-11-07 00:54

There is nothing in the documentation about the command being a probable prime test.
For the record none of these has anything to do with the EFF challenge. I think that can only be satisfied with mathematical proof and without calculating the the digits of the prime.

 danaj 2015-11-07 03:56

[QUOTE=a1call;415199]There is nothing in the documentation about the command being a probable prime test.[/QUOTE]

Under "Implementation notes":

[URL]http://reference.wolfram.com/language/tutorial/SomeNotesOnInternalImplementation.html#6849[/URL]

It states that PrimeQ does trial division with small primes (typical for performance), then M-R bases 2 and 3, then a Lucas test. M-R base 2 plus a proper Lucas test makes the BPSW test. Adding base 3 is either to add more certainty over just BPSW, or (the cynical view) to mask an improper Lucas test.

It points out you need to use ProvablePrimeQ to get a proof.

 a1call 2015-11-07 04:42

[QUOTE=danaj;415217]Under "Implementation notes":

[URL]http://reference.wolfram.com/language/tutorial/SomeNotesOnInternalImplementation.html#6849[/URL]

It states that PrimeQ does trial division with small primes (typical for performance), then M-R bases 2 and 3, then a Lucas test. M-R base 2 plus a proper Lucas test makes the BPSW test. Adding base 3 is either to add more certainty over just BPSW, or (the cynical view) to mask an improper Lucas test.

It points out you need to use ProvablePrimeQ to get a proof.[/QUOTE]

I stand corrected.
Thank you again for your insight [B]danaj[/B].

All times are UTC. The time now is 20:30.