Thread: 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.

x=70

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

something better!

x=10 f(x)=111

Um... x is not a prime in either cases...

Originally Posted by Also sprach Zarathustra

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.

Originally Posted by angypangy

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.

...piece of cake!

Tonio

Pd. Check your program at once!


Oops! Didn't see Bruno's post...oh, well.

Originally Posted by angypangy

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.

Originally Posted by wonderboy1953

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 .

Originally Posted by tonio

...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;
}

Originally Posted by angypangy

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

Originally Posted by tonio

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.

Here is an interesting link listing a bunch of "prime generating polynomials".

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);
}