Eureka!

This is a discussion on Eureka! within the General Discussions forums, part of the Community Boards category; Okay, so I am absolutely obsessed with prime numbers, and for the past two years or so I've experimented with ...

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

    Lightbulb Eureka!

    Okay, so I am absolutely obsessed with prime numbers, and for the past two years or so I've experimented with various schemes for detecting them (much to no avail). Well, last night I fell asleep with my mind complete fixated on the problem (once again!). Suddenly, in the midst of a dream, an equation came to mind, and I instinctively plugged a few numbers into it. Each and every one I tried worked, and I became so excited that I woke up in a cold sweat! I brewed some coffee and got to work on a simple test program. Running the program, my heart sunk as it started spitting out values that failed the test. Damn! But then, as I looked closer at the numbers, I noticed something that caused my hair to literally stand up on end - 561, 1105, 1729, 2465, 2821...these were the first five Carmichael numbers! In other words, my equation was essentially equivalent to Fermat's primality test to every base!!!

    Here is the theorem, in detail:

    IFF gcd(s(N, N - 1) mod s(N, 1), N) = 1 then N is either a prime or a Carmichael number, where s(N, E) is the sum of powers (eg: 1^E + 2^E ... + N^E).

    From a practical viewpoint, I do realize that it may be inefficient to compute (although I haven't yet confirmed that), but nonetheless it does amount to a much more concise generalization of Fermat's Little Theorem.
    Last edited by Sebastiani; 07-22-2010 at 03:16 PM. Reason: typo fix, URL link added
    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
    Epy
    Epy is online now
    Fortran lover Epy's Avatar
    Join Date
    Sep 2009
    Location
    California, USA
    Posts
    994
    N - 1 is way too big of an exponent, I don't think that'd be good for any range of numbers...

    Code:
    MATLAB:
    sp=@ (n,e) sum((1:n).^e);
    
    octave-3.2.4.exe:13> sp(100,99)
    ans =  1.5812e+198

  3. #3
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by Epy View Post
    N - 1 is way too big of an exponent, I don't think that'd be good for any range of numbers...

    Code:
    MATLAB:
    sp=@ (n,e) sum((1:n).^e);
    
    octave-3.2.4.exe:13> sp(100,99)
    ans =  1.5812e+198
    Actually, you can use modular exponentiation to keep the result down to a manageable size (moreover, the modulus can be applied to the accumulated sum as well). The real problem is calculating the "sum of powers" efficiently. The technique that I used simply cycles through 1 -> N, which is slow, to say the least (even trial division would be a faster primality test!), but I'm investigating the possibility that there even exists a method to that efficiently. So for now, the equation has only theoretical significance, in that it compactly describes Fermat's Little Theorem to all number bases (comparably, Wilson's theorem is completely impractical, but nonetheless, it's the most concise definition of primality, to date).
    Last edited by Sebastiani; 07-22-2010 at 09:37 AM. Reason: URL fix
    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;
    }

  4. #4
    Epy
    Epy is online now
    Fortran lover Epy's Avatar
    Join Date
    Sep 2009
    Location
    California, USA
    Posts
    994
    Interesting. That still seems pretty intensive. I guess my question is, what is the advantage of your theorem over the other existing pseudoprime theorems?

  5. #5
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by Epy View Post
    Interesting. That still seems pretty intensive. I guess my question is, what is the advantage of your theorem over the other existing pseudoprime theorems?
    Essentially, it just amounts to a much stronger statement of the domain of N^E-1 mod E for any given N, whereas Fermat's Little Theorem requires much more complex definitions.

    Can my conjecture be used to construct a better Fermat primality test? Maybe, maybe not, but that's really beside the point. There are numerous tests that are much more accurate than Fermat's (Miller-Rabin, Solovay-Strassen, etc), and again, computing my equation may well be too expensive to be practical. The important point is that the generalization is (1) compact, and thus (2) may be helpful in generalizing existing mathematical principles, or in constructing completely new theories. At any rate, it's theoretical importance remains to be seen. I've already notified members of the math community, including a few friends of mine, but considering that my conjecture is just a few days old at this point, it could be a quite a while before any useful results arise from it.*


    *Okay, just for the record, it took less than 48 hours (see here).
    Last edited by Sebastiani; 07-23-2010 at 12:19 PM.
    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;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Eureka show
    By brewbuck in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 06-11-2009, 12:49 AM
  2. Keeping track of the player in a 2d numbered grid.
    By Shamino in forum C++ Programming
    Replies: 1
    Last Post: 03-25-2009, 06:39 PM
  3. ASCII to float
    By trucutu in forum C Programming
    Replies: 5
    Last Post: 11-14-2005, 06:25 PM
  4. Scroll bars.......
    By incognito in forum Windows Programming
    Replies: 5
    Last Post: 01-11-2004, 07:57 AM
  5. contradictory if statements
    By red_baron in forum C Programming
    Replies: 13
    Last Post: 05-04-2002, 07:52 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21