Introduction
In number theory, Pierpont primes are of great interest. By the name of James Pierpont, these primes are given as 2^u ⋅ 3^v +1, where u ≥ 0 and v ≥ 0. It is common and quite acceptable to call such primes irrevocable. They are particularly intriguing in the context of constructible polygons and their relation to the roots of unity. Let us define Pierpont primes as prime numbers that can be expressed as P(u, v) = 2^u ⋅ 3^v +1, where u, v are any non-negative integers. This article will restate Pierpont's problem, describe an algorithm for finding values of the form P(u, v), and demonstrate a solution in C++ .
Problem Statement:
The objective is to find Pierpont primes in a specified range. To be more specific, we aim at:
- To determine numbers of the form 2^u.3^v+1 where u and v take non-negative integral values.
- Checking whether the resulting numbers are prime.
- Giving out a list of all Pierpont primes up to a certain number N.
This problem requires and considers parallel multiplication and prime verification, which makes it a perfect candidate for the improvement of skills related to algorithm designing and perfecting.
Example 1:
Let us take an example to illustrate the Pierpont Prime in C++.
Example
#include <iostream>
#include <vector>
#include <cmath>
#include<bits/stdc++.h>
// Function to check if a number is prime
bool isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i <= std::sqrt(n); ++i) {
if (n % i == 0) return false;
}
return true;
}
// Function to find Pierpont primes up to a given limit
std::vector<int> findPierpontPrimes(int limit) {
std::vector<int> pierpontPrimes;
for (int u = 0; ; ++u) {
long long powerOfTwo = 1LL << u; // Compute 2^u
if (powerOfTwo > limit) break;
for (int v = 0; ; ++v) {
long long powerOfThree = static_cast<long long>(std::pow(3, v)); // Compute 3^v
long long candidate = powerOfTwo * powerOfThree + 1;
if (candidate > limit) break;
if (isPrime(candidate)) {
pierpontPrimes.push_back(candidate);
}
}
}
return pierpontPrimes;
}
int main() {
int limit;
std::cout << "Enter the upper limit: ";
std::cin >> limit;
std::vector<int> primes = findPierpontPrimes(limit);
sort(primes.begin(),primes.end());
std::cout << "Pierpont primes up to " << limit << ":\n";
for (int prime : primes) {
std::cout << prime << " ";
}
std::cout << std::endl;
return 0;
}
Output:
Output
Enter the upper limit: 1000
Pierpont primes up to 1000:
2 3 5 7 13 17 19 37 73 97 109 163 193 257 433 487 577 769
Explanation of the Code:
- Prime Checking: The isPrime function uses a simple trial division up to the square root of the number for efficiency.
- Power Iteration: The outer loop iterates over powers of 2, while the inner loop handles powers of 3. Both loops terminate once their respective powers exceed the limit.
- Dynamic Range Check: The program ensures that numbers exceeding the limit are not computed further, keeping the execution efficient.
- Time Constraints: The complexity in proper prime determination will depend on the unresolved factors in any unit in the range of u and v. Essentially, the number of these computations determines the time set for the present T(n). The time bound runs O(√n) for every candidate of the primality.
- Computation Space Strain: The previously mentioned O(k) type space is employed in the program depending on the number of Pierpont-defined primes generated.
Complexity Analysis:
Example 2:
Let us take another example to illustrate the Pierpont Prime in C++.
Example
#include <iostream>
#include <vector>
#include <cmath>
#include <thread>
#include <mutex>
#include <future>
#include <algorithm>
#include <chrono>
// Mutex for thread-safe access to shared resources
std::mutex resultMutex;
// Function to perform modular exponentiation (a^b % mod)
long long modularExponentiation(long long base, long long exp, long long mod) {
long long result = 1;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp /= 2;
}
return result;
}
// Miller-Rabin primality test
bool isPrimeMillerRabin(long long n, int iterations = 5) {
if (n < 2) return false;
if (n <= 3) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
int r = 0;
while (d % 2 == 0) {
d /= 2;
++r;
}
auto millerTest = [&](long long a) -> bool {
long long x = modularExponentiation(a, d, n);
if (x == 1 || x == n - 1) return true;
for (int i = 1; i < r; ++i) {
x = (x * x) % n;
if (x == n - 1) return true;
}
return false;
};
for (int i = 0; i < iterations; ++i) {
long long a = 2 + std::rand() % (n - 3);
if (!millerTest(a)) return false;
}
return true;
}
// Worker function for generating Pierpont primes
void generatePierpontPrimes(long long limit, int startU, int endU, std::vector<long long>& result) {
for (int u = startU; u <= endU; ++u) {
long long powerOfTwo = 1LL << u; // Compute 2^u
if (powerOfTwo > limit) break;
for (int v = 0;; ++v) {
long long powerOfThree = static_cast<long long>(std::pow(3, v)); // Compute 3^v
long long candidate = powerOfTwo * powerOfThree + 1;
if (candidate > limit) break;
if (isPrimeMillerRabin(candidate)) {
std::lock_guard<std::mutex> lock(resultMutex);
result.push_back(candidate);
}
}
}
}
// Function to parallelize Pierpont prime generation
std::vector<long long> findPierpontPrimesParallel(long long limit, int numThreads) {
std::vector<long long> results;
std::vector<std::thread> threads;
int maxU = static_cast<int>(std::log2(limit));
int range = maxU / numThreads;
for (int i = 0; i < numThreads; ++i) {
int startU = i * range;
int endU = (i == numThreads - 1) ? maxU : (i + 1) * range - 1;
threads.emplace_back(generatePierpontPrimes, limit, startU, endU, std::ref(results));
}
for (auto& thread : threads) {
thread.join();
}
std::sort(results.begin(), results.end());
results.erase(std::unique(results.begin(), results.end()), results.end());
return results;
}
// Main function
int main() {
long long limit;
int numThreads;
std::cout << "Enter the upper limit for Pierpont primes: ";
std::cin >> limit;
std::cout << "Enter the number of threads to use: ";
std::cin >> numThreads;
auto start = std::chrono::high_resolution_clock::now();
std::vector<long long> pierpontPrimes = findPierpontPrimesParallel(limit, numThreads);
auto end = std::chrono::high_resolution_clock::now();
std::cout << "Pierpont primes up to " << limit << ":\n";
for (long long prime : pierpontPrimes) {
std::cout << prime << " ";
}
std::cout << "\n";
std::chrono::duration<double> elapsed = end - start;
std::cout << "Execution time: " << elapsed.count() << " seconds\n";
return 0;
}
Output:
Output
Enter the upper limit for Pierpont primes: 1000000
Enter the number of threads to use: 4
Pierpont primes up to 1000000:
2 3 5 7 13 17 19 37 73 97 109 163 193 257 433 487 577 769 1153 1297 1459 2593 2917 3457 3889 10369 12289 17497 18433 39367 52489 65537 139969 147457 209953 331777 472393 629857 746497 786433 839809 995329
Execution time: 0.00244984 seconds
Features of This Code:
- Miller-Rabin Primality Test: A more efficient probabilistic primality test that can handle large numbers. It provides accuracy suitable for most practical applications.
- Multithreading: It uses threads to split the workload by dividing the range of u values among multiple threads. It ensures that results are collected thread-safely using a mutex.
- Dynamic Resource Allocation: The user can specify the number of threads, enabling optimal usage of available CPU cores.
- Performance Optimization: It combines bitwise operations (1<<u) for powers of 2 with dynamic range checks for efficiency. It eliminates duplicate results and sorts the final output.
- A more efficient probabilistic primality test that can handle large numbers.
- It provides accuracy suitable for most practical applications.
- It uses threads to split the workload by dividing the range of u values among multiple threads.
- It ensures that results are collected thread-safely using a mutex.
- The user can specify the number of threads, enabling optimal usage of available CPU cores.
- It combines bitwise operations (1<<u) for powers of 2 with dynamic range checks for efficiency.
- It eliminates duplicate results and sorts the final output.
- Time Complexity: Miller-Rabin test: O(k⋅log3(n)), where k is the number of iterations and n is the candidate number. Overall complexity depends on the range of u and v as well as the parallelization.
- Space Complexity: The size of the result vector and thread stack size determines memory usage.
- Miller-Rabin test: O(k⋅log3(n)), where k is the number of iterations and n is the candidate number.
- Overall complexity depends on the range of u and v as well as the parallelization.
- The size of the result vector and thread stack size determines memory usage.
Complexity Analysis:
Conclusion:
This article presented efficient algorithms that can be used to find Pierpont pr imes. In this article, C++ is used to illustrate how the theoretical concept could be translated into functional frameworks. Not only are Pierpont primes an interesting mathematical notion, but they are also a tool for delving into even more complex number theory concepts.