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

• November 15th 2010, 10:57 AM
angypangy
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.
• November 15th 2010, 11:58 AM
Also sprach Zarathustra
x=70

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

something better!

x=10 f(x)=111
• November 15th 2010, 12:14 PM
Unknown008
Um... x is not a prime in either cases...
• November 15th 2010, 12:18 PM
Bruno J.
Quote:

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.
• November 15th 2010, 01:41 PM
tonio
Quote:

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.

$7^2+7+1=3\cdot 19$...piece of cake!(Giggle)

Tonio

Pd. Check your program at once!

Oops! Didn't see Bruno's post...oh, well.
• November 15th 2010, 02:01 PM
wonderboy1953
Quote:

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.
• November 15th 2010, 02:53 PM
Bruno J.
Quote:

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 $x^2+x+41$.
• November 16th 2010, 05:02 AM
angypangy
ah yes I made a v silly mistake.
Quote:

Originally Posted by tonio
$7^2+7+1=3\cdot 19$...piece of cake!(Giggle)

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;
}
• November 16th 2010, 07:24 AM
tonio
Quote:

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
• November 16th 2010, 07:44 AM
PaulRS
Quote:

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.
• November 19th 2010, 11:18 AM
chiph588@
Here is an interesting link listing a bunch of "prime generating polynomials".
• November 19th 2010, 08:03 PM
browni3141
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);
}