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.

Printable View

- Nov 15th 2010, 10:57 AMangypangywhy 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. - Nov 15th 2010, 11:58 AMAlso sprach Zarathustra
x=70

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

something better!

x=10 f(x)=111 - Nov 15th 2010, 12:14 PMUnknown008
Um... x is not a prime in either cases...

- Nov 15th 2010, 12:18 PMBruno J.
- Nov 15th 2010, 01:41 PMtonio
- Nov 15th 2010, 02:01 PMwonderboy1953
- Nov 15th 2010, 02:53 PMBruno J.
- Nov 16th 2010, 05:02 AMangypangyah yes I made a v silly mistake.
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;

} - Nov 16th 2010, 07:24 AMtonio
- Nov 16th 2010, 07:44 AMPaulRS
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. - Nov 19th 2010, 11:18 AMchiph588@
Here is an interesting link listing a bunch of "prime generating polynomials".

- Nov 19th 2010, 08:03 PMbrowni3141
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);

}