Is there a formula for generating prime numbers and proving their primality?

[a1call]

I have figured out a formula that generates prime numbers along with the proof that all such generated numbers are primes.
The way it works is that you have to input consecutive prime numbers staring from 2 and ending at some Pn. And no it's not primorial minus or plus 1.
Is this of any value?
Is this novel, or are there already similar formulas?

Thanks in advance

 

[aikismos]

No, you haven't. No algebraic formula can exist for generating primes. :D The Sieve of Eratosthenes conceptually demonstrates that primes are a residue of the naturals after multiples of one prime are removed, but since any prime is a residue of it's cumulative precursors, to predict a prime requires starting at the beginning and calculating onwards ad infinitum. That's my understanding as a non-number theorist. Of course, you can always describe your process to have it peer reviewed.

 

[micromass]

No algebraic formula can exist for generating primes.

That is definitely not true. There are currently no useful such formulas though.

 

[a1call]

Thank you aikismos for the reply.
There are several prizes offered by the Electronic Frontier Foundation for record primes.[3]

The record passed one million digits in 1999, earning a $50,000 prize.[4] In 2008 the record passed ten million digits, earning a $100,000 prize and a https://en.wikipedia.org/w/index.php?title=Cooperative_Computing_Award&action=edit&redlink=1 from the Electronic Frontier Foundation.[3] https://www.physicsforums.com/javascript:void(0) called it the 29th top invention of 2008.[5] Additional prizes are being offered for the first prime number found with at least one hundred million digits and the first with at least one billion digits.[3]

from
https://en.wikipedia.org/wiki/Largest_known_prime_number

Any idea how this works?
Can someone just submit the proof to EFF, or do you have to be published and then they decide to award or somehow else?
Thanks in advance.

 

[aikismos]

That is definitely not true. There are currently no useful such formulas though.

Oh... I wasn't aware there was a proof that an algebraic formula existed for the primes. Can you point me in the right direction, @micromass?

 

[micromass]

Oh... I wasn't aware there was a proof that an algebraic formula existed for the primes. Can you point me in the right direction, @micromass?

Here are some nice formulas, especially Mills' formula is amazing (and useless): https://en.wikipedia.org/wiki/Formula_for_primes It also contains a nice discussion on some current results on polynomials generating prime numbers (or the lack there-of).

 

[micromass]

Thank you aikismos for the reply.
There are several prizes offered by the Electronic Frontier Foundation for record primes.[3]

The record passed one million digits in 1999, earning a $50,000 prize.[4] In 2008 the record passed ten million digits, earning a $100,000 prize and a https://en.wikipedia.org/w/index.php?title=Cooperative_Computing_Award&action=edit&redlink=1 from the Electronic Frontier Foundation.[3] https://www.physicsforums.com/javascript:void(0) called it the 29th top invention of 2008.[5] Additional prizes are being offered for the first prime number found with at least one hundred million digits and the first with at least one billion digits.[3]

from
https://en.wikipedia.org/wiki/Largest_known_prime_number

Any idea how this works?
Can someone just submit the proof to EFF, or do you have to be published and then they decide to award or somehow else?
Thanks in advance.

I think they won't be happy with a formula, you'll actually need to compute a large prime number. Which means the formula alone isn't enough, it also needs to provide efficient computations. For more information, you'll have to ask the EFF. But I would try to contact somebody who is working in this field.

 

[a1call]

Thank you micromass for the reply.
aikismos just google prime number formulas,

Probably the most algebraic on the web is:
https://en.wikipedia.org/wiki/Formula_for_primes#Mills.27_formula

 

[a1call]

I think they won't be happy with a formula, you'll actually need to compute a large prime number. Which means the formula alone isn't enough, it also needs to provide efficient computations. For more information, you'll have to ask the EFF. But I would try to contact somebody who is working in this field.

Thank you. I will send email to EFF for details.

 

[aikismos]

My apologies. The article you posted said "It is known that no non-constant polynomial function P(n) with integer coefficients exists that evaluates to a prime number for all integers n." This was my interpretation of algebraic formulas. Obviously I was thinking way too narrowly.

 

[aikismos]

I'm familiar with the dependence on public key encryption schemes requiring substantial computation power to find two prime (and very large) factors used in the bit twiddling, so I presumed no formula exists to quickly do so (otherwise the algorithmic demands would be obviated), but I'm getting a sense of the other ways of generating sequences of prime numbers; however, they are essentially subsets of the set of all primes, and vary in not only their computational demands, but in their utility given the size and somewhat unpredictable distribution. I'm trying to formulate a statement that would be acceptable and as such I offer:

"No polynomial-time formula exists for generating a complete sequence of prime numbers from any arbitrary value."

Is this an acceptable summary?

 

[a1call]

With existing formulas (including computer routines and codes) you are right even if you omit "complete sequence" (you have to add large primes) either way. There are formulas (some very old) which generate first few primes in sequence.
There are also probabilistic methods which generate probable primes in quick operations. However they are not guaranteed to be primes.
However there are no proofs that such formulas can't exist. In fact as I mentioned earlier, I'm certain I have figured one out.
I'm not going to disclose it here, because I am attempting at publishing them.
Thank you for the discussions.

 

[a1call]

I started this thread in the Mersenne forum:http://www.mersenneforum.org/showthread.php?t=20568

 

[aikismos]

I started this thread in the Mersenne forum:
http://www.mersenneforum.org/showthread.php?t=20568

(Okay, to summarize for other readers)

Essentially the recommendation from the community was as follows:

1. First, test your formula on a small set of probable prime numbers to generate 1,000 digit primes and using software such as pfgw (See http://www.mersennewiki.org/index.php/PFGW) or the more powerful primo (See http://www.mersennewiki.org/index.php/Primo) which is based on elliptical curve primality proof (See https://en.wikipedia.org/wiki/Elliptic_curve_primality) to test your candidate primes (https://en.wikipedia.org/wiki/Probable_prime). The suggestion seems to be if and only if you have a legitimate algorithm which can reliably generate a set of PRPs which turn out to be prime, people will take you seriously.

2. Repeat this process for a collection of 1,000,000 digit primes.

3. Have at your goal of generating a prime of ## 10^9 ## digits, run it through peer-review, and collect your prize.

I poked around to see what I see, and you should know you and your pencil and paper are up against some serious resources. For instance PrimeGrid (See https://en.wikipedia.org/wiki/PrimeGrid) which runs atop a rather power distributed platform (BOINC).

You also say that "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"

I'm going to recommend that for a project like this, you're probably going to work in something a little more powerful than JavaScript and more customizable than Wolfram Alpha. If you want fast and powerful, it's probably going to have to be C or something similar. JavaScript, for instance, is a scripting language for web-applications and is interpreted, not compiled, and doesn't even have pointers. It passes everything by reference.

 

[a1call]

Thank you Aikismos
My programs skills are too rusty for C programming. I probably will not do any programming just to prove a point on a forum. If anyone or any party offers to assist me with generating the code, I will submit my theorem with the proof for their use. Else I will simply submit it for publication to a few journals. They will either publish it or it will the end my attempts.

 

[micromass]

You're not going to learn programming for $50000? Weird choice but ok...

 

[Vanadium 50]

You're not going to learn programming for $50000?

$400,000, as it turns out.

 

[aikismos]

$400,000, as it turns out.

@a1call , if you really think you have a solution which meets the criteria, I'll crank out some C for you. (God knows it's a much nicer medium than Visual Basic which I use at work.) The challenge in this problem is not really one of programming, it's the design of a number theoretic algorithm; instantiating the design in a code base is relatively trivial, and diving into tests of generating PRP's and primality wouldn't be hard because the tools have already been engineered (and to boot are open source!). I think the real issue here is whether you actually have a technique for generating 1,000-digit primes or think you have one. Of course, any computer scientist is obliged to inform you that the proof is in the pudding. If you provide a system and it fails to live up to the specification (in this case generation of primes according to the aforementioned criteria), then it becomes evidence stacked against your claim. And as a general rule, the burden of proof lies on the claimant. Even if we were able to achieve the first step, that's only a preliminary engineering results that moves us towards a second generation prototype (not to mention the third).

You obviously have an interest in mathematics, and don't seem particularly inspired by fiscal gain, so let me ask you questions. In any technical community, certain evidential processes are at play in building a consensus of truth, and the first of them are discriminatory in nature:

1) What formal and informal education do you have in number theory? What about the theory of computation? Computer science and mathematical logic are relevant too.
2) What makes you so sure you can reliably generate hundred-digit primes, if not billion-digit ones? How do you know that they are prime? That in itself a challenge. Numbers that large aren't conducive to pencil and paper verification.
3) As you seem to be a lone wolf, do you have a special gift for mathematics? Most of us who dabble or even work in the field are mere mortals who work vigorously to understand and do math well. But there are men like Euler, Gauss, and Ramanunjan who have a psychological advantage in that they were essentially biological computers with abilities we mortals can only dream of. It is said of Euler that he could do thousands of calculations and could keep them in his head for days. Do you have gifts like that?

I'm going to be rather blunt when I say that your claim will continue to be met with skepticism until you have convincing answers to these sorts of questions or are able to provide the proof as required in the first step.

 

[a1call]

Hello aikismos please check your inbox.

 

[aikismos]

I'm willing to vouch that a1call has graduate-level mathematical skills and clearly has a command of number theory.

 

[Vanadium 50]

Against my better judgement...

I don't think I understand point of this thread: "I have a new algorithm for generating primes, and I will neither show you the algorithm nor provide an example of its output" doesn't leave much to discuss. It's also typical of the argument crackpots make, and if the OP doesn't want to be lumped in with them, he should argue from a different position. The easiest would be to give a smallish prime, or better still, a few smallish primes.

EFF wants to see a specific example of a billion-digit prime. It's not enough to say "The 10^billion-th prime has at least a billion digits", even though it's true. It's to avoid trivial claims like the one I just made, Besides, it's their money and they can set the rules any way they like.

A billion is a big number. Adding two one-billion digit numbers will probably take a substantial fraction of a second on a modern PC. Multiplying them will take even longer. A Lucas-Lehmer test would take about a century.

 

[aikismos]

Against my better judgement...

I don't think I understand point of this thread: "I have a new algorithm for generating primes, and I will neither show you the algorithm nor provide an example of its output" doesn't leave much to discuss. It's also typical of the argument crackpots make, and if the OP doesn't want to be lumped in with them, he should argue from a different position. The easiest would be to give a smallish prime, or better still, a few smallish primes.

Curiousity trumps reason again, eh? Well, I'd argue that the real point of this thread is generate traffic to increase visibility and increase advertising revenues. :D But besides that, this thread is a chance for people who are unarguably in the know about these matters (like you and micromass) to offer insights to lesser math entities like a1call and myself. To wit, many of us denizens who dwell on lower planes of academia or are allowed to visit it infrequently don't really know the best way to take our passion for mathematics and develop it in a particular direction.

As for the OP's reluctance to share, that stems from not knowing what he doesn't know. Very Dunning-Krueger. So here's some more information.

First, he's from Middle East and English isn't his first language, and obviously he's culturally removed from the ivy-covered walls of Boston or Cambridge, and he's really trying to advance his knowledge and experience in number theory, but he lacks the context of relating his algorithm (yes he does have one which generates primes) to the greater effort of coming up with a novel advancement in number theory. It's been my perception that a number of moderators and contributors here are active in academia and take for granted the fact that theories in mathematics are socially constructed and therefore to participate in the dialogue requires a certain cultural knowledge that we lower dwellers in math discourse may not have access to. There's a Kahn Academy for learning Calculus. There isn't one for producing novel mathematical theses. So, to address the OPs situation in this thread more to your satisfaction and to grow my own skills:

Yes. He does have an algorithm for generating incomplete finite and infinite sequences of primes from complete finite sequences of primes. Given the interval ## [p_1, p_n] \forall px \in ℙ ## he can generate primes up to ## p_n^2 ## reliably (he has a proof) and then an infinite number of primes thereafter with a certain degree of probability. He does it by partitioning the sequence and then performing a series of operations resulting in sum/difference pairs. I took a quick look at the combinatorics and found that for ## S_{p_5} ## that there were 15 base combinations of partitions which resulted in 30 candidates, 100% were prime up to ## p_n^2 ## and the remainder being 65% prime. I also took a look and the combinations of partitions grow ## 2^{n-1} - 1 : n = | S_{p_n} | ## for finite sequences.

I think you and I know it's unlikely he's the next Ramanujan, however, until he's persuaded otherwise he's in a pickle. But on his behalf, some questions:

1) Instead of building software from scratch, what are the best package for number theoretical exploration? What software can handle permorials, statistical analysis of sets, exploratory construction of primes. Obviously a non-distributed application won't have the FLOPS to compete with GIMPS or PrimeGrid, but it would probably be conducive to gaining some experience in computational constraints of prime generation, factoring of primes, and primality testing.

2) I looked up the 48th Mersenne which has about 17.4 million digits (far shy of ## 10^9 ##) and GIMPS seems to have a monopoly on largest-primes. Is there even a point of trying to attack a problem like this from another angle? How does one go learning how to gauge the efficacy of various attacks on the problem?

3) Generally, how does someone with a prepubescent knowledge of number theory (relative to the doc/postdoc world) go about determining if work that is done is even novel? Obviously graduate students at MIT don't post to PF; how do they do it? His algorithm, for instance, may be well known. How would he go about checking? Obviously he's better off hanging on the Mersenne board since it's dedicated to this sort of discussion, but is that his only real option?

4) My questions cover a broad range of ideas, so the last question is, what's the best resource to find resources for this particular problem?

Lastly, I'd just like to thank your and micromass for bothering to examine this question. Obviously the two of you have a rather good command of mathematics in general, and you certainly don't have to spend your time sharing your knowledge. For someone like me who works in a corporate setting on inherently less challenging processes, online fora are my only real connection to allow me to learn and hone skills.

 

[micromass]

OK, if he really does have a valid algorithm, then the next thing he should do is to count the operations. How many additions/substractions, multiplications and divisions are necessary. That will be the real decider for whether he has something useful or not.

 

[aikismos]

OK, if he really does have a valid algorithm, then the next thing he should do is to count the operations. How many additions/substractions, multiplications and divisions are necessary. That will be the real decider for whether he has something useful or not.

So essentially, it's about performing a big-O between the algorithm and what sieve theory has to offer?

 

[micromass]

So essentially, it's about performing a big-O between the algorithm and what sieve theory has to offer?

Not entirely, there might be other aspects to it. For example, you can have a larger operation count than another algorithm, but your algorithm can be implemented using parallel computing. Then it might happen that your algorithm wins out anyway. But a first step is doing the operation count.

 

[a1call]

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:

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

Theorem 1:For the set A of n consecutive prime numbers staring from 2 and ending at Pn.

Let:

B⊂A & C=A-BLet the number b be equal to multiples of any-integer-power greater-than 0 of all-the-elements of B.Let the number c be equal to multiples of any-integer-power greater-than 0 of all-the-elements of C.Then d = |±b±c| is a prime number,

∀d: d < Pn2

Proof:
d is not divisible by any elements of A, because

(I) if there are any a such that:

a ∈ A & (a ∈ B ⊕a ∈ B) & a∣d ⇒ ( d/a = m & m ∈ ℤ)

Then

d/a = m ⇒ |±b±c|/a = m ⇒ |b|/a ± |c|/a = m (ii) ∵ (a ∈ B ⊕a ∈ C) ∴ (|b|/ a ∈ ℤ ⊕ |c|/ a ∈ ℤ )Since |b|/a ± |c|/a is an integer and either |b|/a or |c|/a 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 (ii) which states that either |b|/a or |c|/a is an integer exclusively. Thus statement (i) is false.

Since d < Pn2 and d is not divisible by any prime number less than or equal to Pn , then d is a prime number.

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

* Take any set S of consecutive positive primes starting from 2 and ending at some Pn.
* Write a code routine to try either random combinations, or ordered trial combinations of all of 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² - 7² 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.

Here is the thread on the Merssene Forum:
http://www.mersenneforum.org/showthread.php?t=20568

Thank you to all for your time and replies.

 

[Vanadium 50]

Given the interval [p1,pn]∀px∈P [p_1, p_n] \forall px \in ℙ he can generate primes up to p2n p_n^2 reliably (he has a proof)

Then this is far, far, far too computationally intense to be useful. He won't be able to generate a billion digit prime this way. He won't be able to generate a 25 digit prime this way.

 

[Edwin McCravy]

The original poster seems to be talking about something that sounds like proof that there are infinitely many primes.
If 2*3*5*7*...*p(n) is the product of the first n primes, then either there is a prime between [2*3*5*7*...*p(n-1)] and [2*3*5*7*...p(n)] or else [2*3*5*7*...*p(n)]+1 is a prime.

 

[Allin]

I don't think a single algorithm can be a fundamental theorem for determining any prime number. A few renown mathematicians have invented formulas that seemed working pretty well, but others persons later on found conterexamples. Similarly to the The Gunness, some are engaged in a contest. Finding the everlasting operational formula /algorithm ISN'T A MATHEMATICAL PROBLEM, since every mathematical problem has at least one solution. Sorry to be rude.

 

[Edwin McCravy]

At least there is no POLYNOMIAL function f(n) of degree > 0 that can give only prime numbers for positive integer n. Suppose f(n) were such, then f(1) would be the sum of the coefficients and it would be a prime, say p. Then f(1+p) would be the sum of terms of the form c*(1+p)^m. Each such binomial expansion consists of c*(1+ a multiple of p) or c+c*(a multiple of p). Therefore f(1+p) = (sum of the coefficients c) + (a multiple of p) = p + (a multiple of p) = a multiple of p, which isn't prime.

 

[zinq]

"The original poster seems to be talking about something that sounds like proof that there are infinitely many primes.
If 2*3*5*7*...*p(n) is the product of the first n primes, then either there is a prime between [2*3*5*7*...*p(n-1)] and [2*3*5*7*...p(n)] or else [2*3*5*7*...*p(n)]+1 is a prime."

Actually, there is always a prime p satisfying

N < p ≤ 2N​

for any positive integer N. (This fact is called Bertrand's postulate, and its proof is trickier than one might guess. See https://en.wikipedia.org/wiki/Proof_of_Bertrand's_postulate.)

So, the first alternative in the quoted either-or statement always holds.

 

[zinq]

This thread has included several mentions of an "algebraic" formula for primes (or the nonexistence of such a formula).

I think it would be a good idea to be very precise about just what type of formula is being referred to, whether it's one that generates primes or one that cannot do so.

Obviously we can generate an infinite sequence of distinct primes with the evident formula P(n) for all n ≥ 1 as follows:

P(1) = 2;​

P(n+1) = the smallest prime factor of P(1) P(2) ... P(n) + 1.
​

But surely it is a more interesting formula that we're concerned with here.

 

[pbuk]

Hi,

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

* Take any set S of consecutive positive primes starting from 2 and ending at some Pn.
* Write a code routine to try either random combinations, or ordered trial combinations of all of 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 112 - 72 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.

Against my better judgement, here's a counter-example:
S = {2, 3, 5, 7, 11, 13, 17, 19}
A = {2}, B = {3, 5, 7, 11, 13, 17, 19}
a = 2, b = 4,849,845
b - a = 4,849,843 = 43 x 167 x 450473

 

[a1call]

z < Pn²
The pasting dropped the superscript tags. In your example the sum should be less than 361.
There can not be any counter examples for z less than square of Pn.

 

[pbuk]

z < Pn²

That's quite a limitation - if I have consecutive primes up to Pn then testing ANY integer less than P(n)² for primality is trivial - or indeed generating every prime less than P(n)².