Thread: ++Eureka!!!

  1. #1
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708

    Exclamation ++Eureka!!!

    Well folks, I've really done it now!

    In an earlier thread, I put forward a conjecture that generalized Fermat's Little Theorem. Using a related concept, I can now make a statement that generalizes *all* prime numbers!

    Here it is:

    For all N > 2, IFF ((s(N, N - 1) mod s(N, 1)) + 1) mod N = 0 then N is definitely prime, where s(N, E) is the sum of powers (eg: 1^E + 2^E ... + N^E).

    AFAIK, the only other theorem that achieves a similar level of concision is Wilson's Theorem, so the implications of this equation may be quite significant (eg: may lead to much better primality tests).
    Last edited by Sebastiani; 07-24-2010 at 02:06 AM. Reason: reclarification
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    It turns out that one of those terms is completely unnecessary. A simplified description of both conjectures:

    Define g(N) = 1^N-1 + 2^N-1 ... + N^N-1.

    Conjecture #1:

    Iff (g(N) + 1) mod N = 0, then N is prime.

    Conjecture #2:

    Iff gcd(g(N), N) = 1, then N is either prime or an absolute Fermat pseudoprime (Carmichael number).
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  3. #3
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    Even though I haven't posted on either thread, I find this very interesting and would like to hear more about it. Are you close to having a proof of any of your conjectures?
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by pianorain View Post
    Even though I haven't posted on either thread, I find this very interesting and would like to hear more about it. Are you close to having a proof of any of your conjectures?
    Unfortunately, no - producing mathematical proofs is not a strength of mine. But I am working on it.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  5. #5
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    Define g(N) = 1^N-1 + 2^N-1 ... + N^N-1.
    The "N^N-1" term is never useful by definition and the most expensive in practice; get rid of it.

    (And if you actually write code to test it, don't forget to eliminate the majority using the trivial (+1/-1) mod 6 cases.)

    [Edit]
    O_o

    I wonder if the trivially "definitely not prime" test can be used on the other terms as well?!
    [/Edit]



    Are you close to having a proof of any of your conjectures?
    I think this qualifies as a generalization of a test by summation. If so, the proof is exactly the same as Fermat's Little Theorem. (He is basically running every relevant "Fermat Primality Test" at the "same time".) Then again, I have a terrible headache and may have completely misunderstood what he is doing. ;_;

    Soma

  6. #6
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by phantomotap View Post
    The "N^N-1" term is never useful by definition and the most expensive in practice; get rid of it.
    Yep, you're right. Good point.

    Quote Originally Posted by phantomotap View Post

    (And if you actually write code to test it, don't forget to eliminate the majority using the trivial (+1/-1) mod 6 cases.)
    Another good point.

    Quote Originally Posted by phantomotap View Post

    I wonder if the trivially "definitely not prime" test can be used on the other terms as well?!
    Could you elaborate on that?

    Quote Originally Posted by phantomotap View Post
    I think this qualifies as a generalization of a test by summation. If so, the proof is exactly the same as Fermat's Little Theorem. (He is basically running every relevant "Fermat Primality Test" at the "same time".) Then again, I have a terrible headache and may have completely misunderstood what he is doing. ;_;
    Hmm...
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  7. #7
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    Could you elaborate on that?
    *shrug*

    Not really; it was just a little "bing" that... "binged" while I wrote my post.

    I'm basically wondering if some of the other factors couldn't be "omitted" because they either contribute nothing or result in a term that naturally requires the sum to not be "mod P".

    Soma

  8. #8
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by Sebastiani View Post
    It turns out that one of those terms is completely unnecessary. A simplified description of both conjectures:

    Define g(N) = 1^N-1 + 2^N-1 ... + N^N-1.

    Conjecture #1:

    Iff (g(N) + 1) mod N = 0, then N is prime.

    Conjecture #2:

    Iff gcd(g(N), N) = 1, then N is either prime or an absolute Fermat pseudoprime (Carmichael number).
    I can prove it one way... Euler's theorem - Wikipedia, the free encyclopedia
    a^phi(n) = 1 (mod n) iff a and n are relative prime. So if p is prime, since phi(p) = p - 1:
    a^(p-1) = 1 (mod n)
    So g(n), when n is prime, is 1 + 1 + ... + 1 (mod n) = n-1 (mod n).

    The other way around... Not sure if it's really true, to be honest. I doubt it ;-).

    And it's of course very unlikely for g(N) = 1 (mod N) for any other number (1 in N) if it's distributed equally, so it's quite difficult to find a counterexample probably as well. But I think there is a counter example.


    Edit: Note that g(N) (mod N) = 2*(1^(N-1) + 2^(N-1) + ... + ((N-1)/2)^(N-1)) (mod N)
    Last edited by EVOEx; 07-27-2010 at 01:26 AM.

  9. #9
    Make Fortran great again
    Join Date
    Sep 2009
    Posts
    1,413
    If you were really serious about this, why post it in the public eye? Just about everything in mathematics had already been figured out by the 1920s, it's really unwise to share so much about your new theorem.

  10. #10
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    Quote Originally Posted by Epy View Post
    Just about everything in mathematics had already been figured out by the 1920s.
    This is an odd thing to say considering that Paul Erdős was born in 1913.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  11. #11
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by pianorain View Post
    This is an odd thing to say considering that Paul Erdős was born in 1913.
    He was just very talented...

    Really, it's a load of crap, though. There are infinitely many unknown things in mathematics, even important thing that we don't know or can be improved. And once we know more, there is more that we need as it only begs more questions.
    For instance, take the poincare conjecture. It's been solved only fairly recently. And there are MANY more unsolved questions. For a small selection: Unsolved Problems -- from Wolfram MathWorld

  12. #12
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    Quote Originally Posted by Epy View Post
    If you were really serious about this, why post it in the public eye? Just about everything in mathematics had already been figured out by the 1920s, it's really unwise to share so much about your new theorem.
    On the contrary, if you're really serious about this, why don't you start writing an academic paper, get it published, and have a mathematics professor either co-author it or just at least be nice enough to look over it for you to make sure it's fool proof?
    Last edited by DavidP; 07-27-2010 at 03:00 PM. Reason: grammar correction
    My Website

    "Circular logic is good because it is."

  13. #13
    Make Fortran great again
    Join Date
    Sep 2009
    Posts
    1,413
    Quote Originally Posted by DavidP View Post
    On the contrary, if you're really serious about this, why don't you start writing an academic paper, get it published, and have a mathematics professor either co-author it or just at least be nice enough to look over it for you to make sure it's fool proof?
    That statement doesn't really make any sense, you're forming it as if you're disagreeing with me but you're really not. He should write a paper, not post every detail to a forum. He's counting on all of us being slackers.

  14. #14
    Make Fortran great again
    Join Date
    Sep 2009
    Posts
    1,413
    Quote Originally Posted by pianorain View Post
    This is an odd thing to say considering that Paul Erdős was born in 1913.
    Never read anything he's done. Everything I've ever looked at has been by Euler, Poincare, Gauss, Ramanujan, Fermat, etc. The foundations of mathematics were certainly done before the 1900s, in my opinion. (Yes, I know that Ramanunjan was active into the early 1900s, but he was all number theory stuff anyway)

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by Epy
    Just about everything in mathematics had already been figured out by the 1920s
    Quote Originally Posted by Epy
    The foundations of mathematics were certainly done before the 1900s, in my opinion.
    There is a difference between "just about everything in mathematics" and "the foundations of mathematics". That the former "had already been figured out by the 1920s" is either a gross exaggeration or a statement made in sheer ignorance, whereas one might reasonably agree that the latter "were certainly done before the 1900s".
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Eureka!
    By Sebastiani in forum General Discussions
    Replies: 4
    Last Post: 07-22-2010, 02:10 PM
  2. Eureka show
    By brewbuck in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 06-10-2009, 11:49 PM
  3. Keeping track of the player in a 2d numbered grid.
    By Shamino in forum C++ Programming
    Replies: 1
    Last Post: 03-25-2009, 05:39 PM
  4. ASCII to float
    By trucutu in forum C Programming
    Replies: 5
    Last Post: 11-14-2005, 06:25 PM
  5. Scroll bars.......
    By incognito in forum Windows Programming
    Replies: 5
    Last Post: 01-11-2004, 07:57 AM