Ormiston triples: Difference between revisions
Content added Content deleted
(New post.) |
(New post which does not use external libraries. In addition to an existing post which uses the "Boost" library.) |
||
Line 215: | Line 215: | ||
Number of Ormiston triples < 1000000000: 368 |
Number of Ormiston triples < 1000000000: 368 |
||
Number of Ormiston triples < 10000000000: 4925 |
Number of Ormiston triples < 10000000000: 4925 |
||
</pre> |
|||
===Without external libraries=== |
|||
This example uses a segmented prime iterator, and therefore does not require any external libraries. |
|||
<syntaxhighlight lang="c++"> |
|||
#include <algorithm> |
|||
#include <cmath> |
|||
#include <cstdint> |
|||
#include <iomanip> |
|||
#include <iostream> |
|||
#include <vector> |
|||
class SegmentedPrimeIterator { |
|||
public: |
|||
SegmentedPrimeIterator(uint64_t aLimit) { |
|||
square_root = std::sqrt(aLimit); |
|||
index = 0; |
|||
low = 0; |
|||
high = square_root; |
|||
small_sieve(square_root); |
|||
} |
|||
uint64_t next() { |
|||
if ( index == primes.size() ) { |
|||
index = 0; |
|||
segmented_sieve(); |
|||
} |
|||
return primes[index++]; |
|||
} |
|||
private: |
|||
void segmented_sieve() { |
|||
low += square_root; |
|||
high += square_root; |
|||
std::vector<bool> marked_prime(square_root, true); |
|||
for ( uint64_t i = 0; i < small_primes.size(); ++i ) { |
|||
uint64_t low_limit = ( low / small_primes[i] ) * small_primes[i]; |
|||
if ( low_limit < low ) { |
|||
low_limit += small_primes[i]; |
|||
} |
|||
for ( uint64_t j = low_limit; j < high; j += small_primes[i] ) { |
|||
marked_prime[j - low] = false; |
|||
} |
|||
} |
|||
primes.clear(); |
|||
for ( uint64_t i = low; i < high; ++i ) { |
|||
if ( marked_prime[i - low] ) { |
|||
primes.emplace_back(i); |
|||
} |
|||
} |
|||
} |
|||
void small_sieve(const uint32_t& square_root) { |
|||
std::vector<bool> marked_prime(square_root + 1, true); |
|||
for ( uint32_t p = 2; p * p <= square_root; ++p ) { |
|||
if ( marked_prime[p] ) { |
|||
for ( uint32_t i = p * p; i <= square_root; i += p ) { |
|||
marked_prime[i] = false; |
|||
} |
|||
} |
|||
} |
|||
for ( uint32_t p = 2; p <= square_root; ++p ) { |
|||
if ( marked_prime[p] ) { |
|||
primes.emplace_back((uint64_t) p); |
|||
} |
|||
} |
|||
small_primes.insert(small_primes.end(), primes.begin(), primes.end()); |
|||
} |
|||
uint32_t index, square_root; |
|||
uint64_t low, high; |
|||
std::vector<uint64_t> primes; |
|||
std::vector<uint64_t> small_primes; |
|||
}; |
|||
std::vector<uint32_t> digits(uint64_t number) { |
|||
std::vector<uint32_t> result; |
|||
while ( number > 0 ) { |
|||
result.emplace_back(number % 10); |
|||
number /= 10; |
|||
} |
|||
std::sort(result.begin(), result.end()); |
|||
return result; |
|||
} |
|||
bool haveSameDigits(uint64_t first, uint64_t second) { |
|||
return digits(first) == digits(second); |
|||
} |
|||
int main() { |
|||
const uint64_t limit = 10'000'000'000; |
|||
SegmentedPrimeIterator primes(limit); |
|||
std::vector<uint64_t> ormistons; |
|||
uint64_t lower_limit = limit / 10; |
|||
uint32_t count = 0; |
|||
std::vector<uint32_t> counts; |
|||
uint64_t p1 = 0, p2 = 0, p3 = 0; |
|||
while ( p3 < limit ) { |
|||
p1 = p2; p2 = p3; p3 = primes.next(); |
|||
if ( ( p2 - p1 ) % 18 != 0 || ( p3 - p2 ) % 18 != 0 ) { |
|||
continue; |
|||
} |
|||
if ( ! haveSameDigits(p1, p2) ) { |
|||
continue; |
|||
} |
|||
if ( haveSameDigits(p2, p3) ) { |
|||
if ( count < 25 ) { |
|||
ormistons.emplace_back(p1); |
|||
} |
|||
if ( p1 >= lower_limit ) { |
|||
counts.emplace_back(count); |
|||
lower_limit *= 10; |
|||
} |
|||
count += 1; |
|||
} |
|||
} |
|||
counts.emplace_back(count); |
|||
std::cout << "The smallest member of the first 25 Ormiston triples:" << std::endl; |
|||
for ( uint64_t i = 0; i < ormistons.size(); ++i ) { |
|||
std::cout << std::setw(10) << ormistons[i] << ( i % 5 == 4 ? "\n" : "" ); |
|||
} |
|||
std::cout << std::endl; |
|||
lower_limit = limit / 10; |
|||
for ( uint64_t i = 0; i < counts.size(); ++i ) { |
|||
std::cout << counts[i] << " Ormiston triples less than " << lower_limit << std::endl; |
|||
lower_limit *= 10; |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
The smallest member of the first 25 Ormiston triples: |
|||
11117123 12980783 14964017 32638213 32964341 |
|||
33539783 35868013 44058013 46103237 48015013 |
|||
50324237 52402783 58005239 60601237 61395239 |
|||
74699789 76012879 78163123 80905879 81966341 |
|||
82324237 82523017 83279783 86050781 92514341 |
|||
368 Ormiston triples less than 1000000000 |
|||
4925 Ormiston triples less than 10000000000 |
|||
</pre> |
</pre> |
||