1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A Prime Numbers formula

  1. Oct 19, 2015 #1
    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
     
  2. jcsd
  3. Oct 19, 2015 #2
    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.
     
  4. Oct 19, 2015 #3
    That is definitely not true. There are currently no useful such formulas though.
     
  5. Oct 19, 2015 #4
    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 [Broken] from the Electronic Frontier Foundation.[3] https://www.physicsforums.com/javascript:void(0) [Broken] 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.
     
    Last edited by a moderator: May 7, 2017
  6. Oct 19, 2015 #5
    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?
     
  7. Oct 19, 2015 #6
    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).
     
  8. Oct 19, 2015 #7
    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.
     
    Last edited by a moderator: May 7, 2017
  9. Oct 19, 2015 #8
  10. Oct 19, 2015 #9
    Thank you. I will send email to EFF for details.
     
  11. Oct 19, 2015 #10
    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.
     
  12. Oct 19, 2015 #11
    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?
     
  13. Oct 20, 2015 #12
    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.
     
  14. Oct 23, 2015 #13
  15. Oct 24, 2015 #14
    (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.
     
  16. Oct 24, 2015 #15
    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.
     
  17. Oct 24, 2015 #16
    You're not going to learn programming for $50000? Weird choice but ok...
     
  18. Oct 24, 2015 #17

    Vanadium 50

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2017 Award

    $400,000, as it turns out.
     
  19. Oct 24, 2015 #18
    @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 in to 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.
     
  20. Oct 24, 2015 #19
    Hello aikismos please check your inbox.
     
  21. Oct 24, 2015 #20
    I'm willing to vouch that a1call has graduate-level mathematical skills and clearly has a command of number theory.
     
  22. Oct 25, 2015 #21

    Vanadium 50

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2017 Award

    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.
     
  23. Oct 25, 2015 #22
    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.
     
  24. Oct 25, 2015 #23
    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.
     
  25. Oct 25, 2015 #24
    So essentially, it's about performing a big-O between the algorithm and what sieve theory has to offer?
     
  26. Oct 25, 2015 #25
    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook