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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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

    $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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prime Numbers formula
  1. Prime number formula (Replies: 6)

  2. Prime numbers (Replies: 12)

  3. Prime numbers (Replies: 8)

Loading...