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