Results 1 to 12 of 12

Math Help - why is a prime squared + itself + 1 also a prime

  1. #1
    Member
    Joined
    Jul 2009
    From
    London
    Posts
    109

    why is a prime squared + itself + 1 also a prime

    if x is a prime and passed to f(x) = x^2 + x + 1, result is also a prime. why is this?

    I tested by writing a computer program to test all cases of x where x is a prime up to 999999 and result was a prime.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    x=70

    f(70)=70^2+70+1=4971=3*1657

    something better!

    x=10 f(x)=111
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Unknown008's Avatar
    Joined
    May 2010
    From
    Mauritius
    Posts
    1,260
    Um... x is not a prime in either cases...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by Also sprach Zarathustra View Post
    x=70

    f(70)=70^2+70+1=4971=3*1657

    something better!

    x=10 f(x)=111
    But those aren't prime...

    Angypangy, I don't know what kind of program you wrote, but this fails for the fourth prime, x=7.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by angypangy View Post
    if x is a prime and passed to f(x) = x^2 + x + 1, result is also a prime. why is this?

    I tested by writing a computer program to test all cases of x where x is a prime up to 999999 and result was a prime.

    7^2+7+1=3\cdot 19...piece of cake!

    Tonio

    Pd. Check your program at once!


    Oops! Didn't see Bruno's post...oh, well.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    769
    Quote Originally Posted by angypangy View Post
    if x is a prime and passed to f(x) = x^2 + x + 1, result is also a prime. why is this?

    I tested by writing a computer program to test all cases of x where x is a prime up to 999999 and result was a prime.
    This is the famous Euler equation for generating primes. It works for the first 41 numbers and is reputed to be the best equation for generating primes.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by wonderboy1953 View Post
    This is the famous Euler equation for generating primes. It works for the first 41 numbers and is reputed to be the best equation for generating primes.
    No! As pointed out above, this one fails terribly. Euler's prime generating polynomial is x^2+x+41.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jul 2009
    From
    London
    Posts
    109

    ah yes I made a v silly mistake.

    Quote Originally Posted by tonio View Post
    7^2+7+1=3\cdot 19...piece of cake!

    Tonio

    Pd. Check your program at once!


    Oops! Didn't see Bruno's post...oh, well.
    This code finds seven
    #include <iostream>


    bool isPrime(unsigned n)
    {
    bool prime(true);
    for(int i = 2; i < n; ++i)
    {
    if(n % i == 0)
    {
    prime = false;
    break;
    }
    }
    return prime;
    }


    int main()
    {
    for(int a = 2; a < 999999; ++a)
    {
    if(isPrime(a))
    {
    //ok so we have a prime now. So now pass to func to see if result is a prime
    if(!isPrime(a * a + a + 1))
    {
    std::cout << "prime used: " << a << " result of n * n + n + 1=" << a * a + a + 1 << std::endl;
    break;
    }
    }
    }
    return 0;
    }
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by angypangy View Post
    This code finds seven
    #include <iostream>


    bool isPrime(unsigned n)
    {
    bool prime(true);
    for(int i = 2; i < n; ++i)
    {
    if(n % i == 0)
    {
    prime = false;
    break;
    }
    }
    return prime;
    }


    int main()
    {
    for(int a = 2; a < 999999; ++a)
    {
    if(isPrime(a))
    {
    //ok so we have a prime now. So now pass to func to see if result is a prime
    if(!isPrime(a * a + a + 1))
    {
    std::cout << "prime used: " << a << " result of n * n + n + 1=" << a * a + a + 1 << std::endl;
    break;
    }
    }
    }
    return 0;
    }

    I don't have the faintest idea what "this code finds seven" can possibly mean within the context of this question.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by tonio View Post
    I don't have the faintest idea what "this code finds seven" can possibly mean within the context of this question.

    Tonio
    Apparently he fixed the code and now the program prints that the statement fails for the prime number 7.

    angypangy: I'd like to point out a detail there, which in this case is not relevant since you stop testing as early as by a = 7. When you do a*a , you can overflow the int roughly for a greater or equal than 10⁵ (since int goes from -2⁰ to 2 - 1), you'd have to switch to long long if you wanted to try for such numbers.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Here is an interesting link listing a bunch of "prime generating polynomials".
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Nov 2010
    Posts
    21
    Here are examples of a few prime number programs I've written in case you want to use them for reference. The first one tests primality of a Mersenne number using the Lucas-Leihmer test:

    #include <iostream>
    #include <cmath>

    using namespace std;

    uint64_t Prime_Test(uint64_t number, short I);
    uint64_t Prime_Test2(uint64_t number);

    main ()
    {
    do
    {
    cout << "This program will test if a Mersenne number is prime.\nEnter a number to test 2^n-1 for primality.\nEnter 0 to quit.\n";
    uint64_t n=2;
    short i, I;
    cin >> I;
    for (i=1; i!=I; i++)
    {
    n *= 2;
    }
    n--;
    cout << n;
    if (n==-1)
    return 0;
    if ((Prime_Test (n,I)) && (Prime_Test2 (I)))
    cout << " is prime.\n";
    else
    cout << " is not prime\n";
    system ("pause");
    system ("cls");
    } while (1);
    return 0;
    }

    uint64_t Prime_Test(uint64_t number, short I)
    {
    __hyper i;
    if (number == 3)
    return 1;
    for (i=2*I+1; i<= sqrt(number); i+=2*I)
    {
    if (number%i==0)
    return 0;
    }
    return 1;
    }

    uint64_t Prime_Test2(uint64_t number)
    {
    short i;
    if (number == 2)
    return 1;
    if ((number%2==0) || (number == 1))
    return 0;
    for (i=3; i<= sqrt(number); i+=2)
    {
    if (number%i==0)
    return 0;
    }
    return 1;
    }


    and this one generates primes and sends them too an outfile.


    #include <iostream.h>
    #include <math.h>
    #include <fstream.h>

    unsigned long long Prime_Test(unsigned long long number);

    main ()
    {
    ofstream outfile;
    outfile.open("Prime List2.dat", ios::app);
    outfile << 2 << ' ';
    if (!outfile)
    return 0;
    unsigned long long n;
    for (n=3; n!=99999999; n+=2)
    {
    if (n==0)
    break;
    if (Prime_Test (n))
    outfile << n << ' ';
    }
    outfile.close();
    return 0;
    }

    unsigned long long Prime_Test(unsigned long long number)
    {
    unsigned long long i;
    if (number%2==0)
    return 0;
    for (i=3; i<= sqrt(number); i+=2)
    {
    if (number%i==0)
    return 0;
    }
    return (1);
    }
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. Replies: 1
    Last Post: June 19th 2011, 12:56 PM
  3. Replies: 3
    Last Post: February 17th 2011, 07:51 AM
  4. Replies: 6
    Last Post: August 27th 2010, 11:44 PM
  5. if ((2^n) -1 ) is prime, prove n is prime ?! >.<
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 18th 2009, 01:47 PM

Search Tags


/mathhelpforum @mathhelpforum