#include #include #include #include #include using namespace std; bool IsPrime(unsigned long int x); unsigned long int ChernickFirst(unsigned int p); int main() { cout << "Chernick’s first formula of Carmichael’s Pseudo-Prime Numbers (up to 242000):\n\n" << "In his paper on Fermat’s small theorem, Jack Chernick formulated some equations, to find several series of Carmichael’s Pseudo-Prime Numbers.\n\n" << "Chernick’s first equation is:\n" << "(6M + 1) * (12M+1) * (18M+1) When all 3 elements are Prime Numbers = Carmichael’s Pseudo-Prime Number.\n\n" << "I.e. if we replace M with 1 , we get:\n" << "6 * 1 + 1 = 7 (A Prime Number)\n" << "12 * 1 + 1 = 13 (A Prime Number)\n" << "18 * 1 + 1 = 19 (A Prime Number)\n\n" << "7 * 13 * 19 = 1729 (A Carmichael’s Pseudo-Prime Number)\n\n" << "But if we replace M with any number between 2 and 5, we don’t get Prime Numbers, thus the multiplication will not produce a Carmichael’s Pseudo-Prime Number.\n\n" << "A 6 will yield: 37 * 73 * 109 = 294409 .\n\n" << "In fact, 1 and 6 are the only one-digit parameters of Chernick’s first equation.\n\n" << "You can use this little program to test any number (between 1 and 242000) if it fits the first Chernick’s equation to produce a Carmichael’s Pseudo-Prime Number.\n\n\n"; string MyInput; unsigned int x; regex myExp; myExp = ("\\D"); cout << "Enter a positive number, less then 242000: "; cin >> MyInput; /* A validator that doesn't run well on this compiler - TNX Ina. */ /* while (regex_search(MyInput, myExp) || stoi(MyInput) > 242000) { cout << MyInput << " is NOT a positive number less then 242000\nEnter a positive number, less then 242000: "; cin >> MyInput; } */ x = stoi(MyInput); if (ChernickFirst(x) !=0) cout << endl << x << " yieldes " << ChernickFirst(x) << " which is a Carmichael's Number." << endl; else cout << endl << x << " does not yield a Carmichael's Number that fits in Chernick's firt equation." << endl; // To list all possiable numbers, uncoment the following for loop. /* for (int i = 1; i < 242000; i++) { if (ChernickFirst(i) != 0) cout << i << ": " << ChernickFirst(i) << endl; } */ return 0; } /******************************************************************************************** * The IsPrime function, takes an unsigned (long) integer as an argument, and checkes wether * * this integer is a Prime Number or not. * * Tha function returns (boolian) true if the integer passed to it is a Prime number, * * and (boolian) false if it is a composite number. * * The function will returm (boolian) false if the argument is 0 or 1 as well, since 0 and 1 * * are not Prime Numbers and not composite numbers. * ********************************************************************************************/ bool IsPrime(unsigned long int x) { if (x <= 4) { switch (x) { case 2: case 3: return true; break; case 0: case 1: case 4: default: return false; break; } } else if (x % 2 == 0) return false; // An even number bigger then 2. else { unsigned long int i; for (i=3; i<=sqrt(x); i++) { if (x % i == 0) return false; } return true; } } /************************************************************************************************* * The ChernickFirst function, test an Integer between 1 and 242000 (passed to it as a parameter) * * to see if it fits Chernick's first equation, to produce a Carmichael's Pseudo-Prime Number. * * The function returns 0 if the test fails, and the Pseudo-Prime Number if the test passes. * *************************************************************************************************/ unsigned long int ChernickFirst(unsigned int p) { unsigned long int K1 = 6 * p + 1; unsigned long int K2 = 12 * p + 1; unsigned long int K3 = 18 * p + 1; unsigned long int CarmichelNum = (K1 * K2 * K3); if (IsPrime(K1) && IsPrime(K2) && IsPrime(K3)) return CarmichelNum; else return 0; }

Chernicks First equation on Carmichaels Pseudo-Prime Numbers.cpp