Rosetta Code

Ormiston triples: Difference between revisions

Page Discussion

Ormiston triples (view source)

Revision as of 00:55, 3 March 2024

6,965 bytes added ,  2 months ago
Added FreeBASIC
(New post.)
(Added FreeBASIC)
 
(13 intermediate revisions by 4 users not shown)
Line 215:
Number of Ormiston triples < 1000000000: 368
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(const 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(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>
 
Line 692 ⟶ 844:
</pre>
 
 
=={{header|EasyLang}}==
<syntaxhighlight>
fastfunc isprim num .
if num mod 3 = 0
return 0
.
i = 5
while i <= sqrt num
if num mod i = 0
return 0
.
i += 2
if num mod i = 0
return 0
.
i += 4
.
return 1
.
func nextprim n .
repeat
n += 2
until isprim n = 1
.
return n
.
func digs n .
while n > 0
r += pow 10 (n mod 10)
n = n div 10
.
return r
.
print "Smallest member of the first 25 Ormiston triples:"
b = 2
a = 3
repeat
c = b
dc = db
b = a
db = da
a = nextprim a
until a > 1000000000
da = digs a
if da = db and da = dc
cnt += 1
if cnt <= 25
write c & " "
.
.
.
print "Ormiston triples before 1 billion: " & cnt
</syntaxhighlight>
 
=={{header|F_Sharp|F#}}==
Line 708 ⟶ 914:
<1 billion: 368
</pre>
 
=={{header|FreeBASIC}}==
{{trans|XPLo}}
<syntaxhighlight lang="vbnet">Function GetSig(Byval N As Uinteger) As Uinteger 'Return signature of N
'A "signature" is the count of each digit in N packed into a 32-bit word
Dim As Uinteger Sig = 0
Do While N > 0
Sig += 1 Shl (N Mod 10)
N \= 10
Loop
Return Sig
End Function
 
Dim As Uinteger limite = 1e9
Dim Shared As Boolean Sieve(limite)
 
Sub MakeSieve(Size As Uinteger) 'Make prime number sieve
Dim As Uinteger Prime, i, K
Size \= 2 'ignore even numbers
For i = 0 To Size 'set Sieve flags all true
Sieve(i) = True
Next
For i = 0 To Size
If Sieve(i) Then 'found a prime, which is equal to
Prime = i * 2 + 3 ' twice the index + 3
K = i + Prime 'first multiple to strike off
While K <= Size 'strike off all multiples
Sieve(K) = False
K += Prime
Wend
End If
Next
End Sub
 
MakeSieve(limite)
Print "Smallest members of first 25 Ormiston triples:"
Dim As Uinteger Cnt = 0, N0 = 0, N1 = 0, Sig0 = 0, Sig1 = 0, N = 3, Sig
Dim As Double t0 = Timer
Do
If Sieve(N \ 2 - 1) Then ' is prime
Sig = GetSig(N)
If Sig = Sig0 Andalso Sig = Sig1 Then
Cnt += 1
If Cnt <= 25 Then
Print Using "#,###,###,###"; N0;
If Cnt Mod 5 = 0 Then Print
End If
End If
Sig0 = Sig1: Sig1 = Sig
N0 = N1: N1 = N
End If
If N >= limite Then Print Cnt; " Ormiston triples before one billion." : Exit Do
N += 2
Loop
 
Sleep</syntaxhighlight>
 
=={{header|Go}}==
{{trans|Wren}}
Line 866 ⟶ 1,129:
 
=={{header|Java}}==
This example uses a segmented prime iterator to complete the stretch task in 7560 seconds, without external libraries.
<syntaxhighlight lang="java">
import java.util.ArrayList;
Line 908 ⟶ 1,171:
counts.add(count);
System.out.println("The smallest membersmember of the first 25 Ormiston triples:");
for ( int i = 0; i < ormistons.size(); i++ ) {
System.out.print(String.format("%10d%s", ormistons.get(i), ( i % 5 == 4 ? "\n" : "" )));
Line 1,009 ⟶ 1,272:
{{ out }}
<pre>
The smallest membersmember of the first 25 Ormiston triples:
11117123 12980783 14964017 32638213 32964341
33539783 35868013 44058013 46103237 48015013
Line 1,966 ⟶ 2,229:
25 Ormiston triples before one hundred million
368 Ormiston triples before one billion</pre>
=={{header|Ruby}}==
<syntaxhighlight lang="ruby" line>
require 'prime'
 
def all_anagram?(arr)
sorted = arr.first.digits.sort
arr[1..].all?{|a| a.digits.sort == sorted}
end
 
res = Prime.each.each_cons(3).lazy.filter_map{|ar| ar.first if all_anagram?(ar)}.first(25)
res.each_slice(5){|slice| puts slice.join(", ")}
 
n = 1E9
res = Prime.each(n).each_cons(3).count {|ar| all_anagram?(ar)}
puts "\nThere are #{res} Ormiston triples below #{n}"
</syntaxhighlight>
{{out}}
<pre>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
 
There are 368 Ormiston triples below 1000000000.0
</pre>
 
=={{header|Wren}}==
Line 1,973 ⟶ 2,261:
 
Limiting the search to a billion, takes about 73 seconds (68 seconds using our 'standard' sieve).
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int
import "./fmt" for Fmt
 
Line 2,033 ⟶ 2,321:
 
It's also far quicker - 4.4 seconds to search up to 1 billion and 43.4 seconds to search up to 10 billion.
<syntaxhighlight lang="ecmascriptwren">import "./psieve" for Primes
import "./math" for Int
import "./fmt" for Fmt
Jjuanhdez
2,122

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/358354...361094"