Ormiston triples
An Ormiston triple is three consecutive prime numbers which are anagrams, i.e. contain the same decimal digits but in a different order.
Ormiston triples is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- Definition
- Example
The three consecutive primes (11117123, 11117213, 11117321) are an Ormiston triple.
- Task
- Find and show the smallest member of the first 25 Ormiston triples.
- Find and show the count of Ormiston triples up to one billion.
- Stretch
- Find and show the count of Ormiston triples up to ten billion.
- Reference
- Related task
C++
#include <array>
#include <iostream>
#include <primesieve.hpp>
class ormiston_triple_generator {
public:
ormiston_triple_generator() {
for (int i = 0; i < 2; ++i) {
primes_[i] = pi_.next_prime();
digits_[i] = get_digits(primes_[i]);
}
}
std::array<uint64_t, 3> next_triple() {
for (;;) {
uint64_t prime = pi_.next_prime();
auto digits = get_digits(prime);
bool is_triple = digits == digits_[0] && digits == digits_[1];
uint64_t prime0 = primes_[0];
primes_[0] = primes_[1];
primes_[1] = prime;
digits_[0] = digits_[1];
digits_[1] = digits;
if (is_triple)
return {prime0, primes_[0], primes_[1]};
}
}
private:
static std::array<int, 10> get_digits(uint64_t n) {
std::array<int, 10> result = {};
for (; n > 0; n /= 10)
++result[n % 10];
return result;
}
primesieve::iterator pi_;
std::array<uint64_t, 2> primes_;
std::array<std::array<int, 10>, 2> digits_;
};
int main() {
ormiston_triple_generator generator;
int count = 0;
std::cout << "Smallest members of first 25 Ormiston triples:\n";
for (; count < 25; ++count) {
auto primes = generator.next_triple();
std::cout << primes[0] << ((count + 1) % 5 == 0 ? '\n' : ' ');
}
std::cout << '\n';
for (uint64_t limit = 1000000000; limit <= 10000000000; ++count) {
auto primes = generator.next_triple();
if (primes[2] > limit) {
std::cout << "Number of Ormiston triples < " << limit << ": "
<< count << '\n';
limit *= 10;
}
}
}
- Output:
Smallest members of 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 Number of Ormiston triples < 1000000000: 368 Number of Ormiston triples < 10000000000: 4925
F#
This task uses Ormiston_pairs#F#
// Ormiston triples. Nigel Galloway: February 3rd., 2023
let oTriples n=n|>Seq.pairwise|>Seq.filter(fun((n,i),(g,l))->i=g)|>Seq.map(fun((n,i),(g,l))->(n,g,l))
primes32()|>oPairs|>oTriples|>Seq.take 25|>Seq.iter(fun(n,_,_)->printf "%d " n); printfn ""
printfn $"<100 million: %d{primes32()|>Seq.takeWhile((>)100000000)|>oPairs|>oTriples|>Seq.length}"
printfn $"<1 billion: %d{primes32()|>Seq.takeWhile((>)1000000000)|>oPairs|>oTriples|>Seq.length}"
- Output:
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 <100 million: 25 <1 billion: 368
Go
This runs in about 54 seconds on my Core i7 machine.
import "./math" for Int
import "./fmt" for Fmt
var limit = 1e10
var primes = Int.segmentedSieve(limit, 8)
var orm25 = []
var j = 1e9
var count = 0
var counts = []
for (i in 0...primes.count-2) {
var p1 = primes[i]
var p2 = primes[i+1]
var p3 = primes[i+2]
if ((p2 - p1) % 18 != 0 || (p3 - p2) % 18 != 0) continue
var key1 = 1
for (dig in Int.digits(p1)) key1 = key1 * primes[dig]
var key2 = 1
for (dig in Int.digits(p2)) key2 = key2 * primes[dig]
if (key1 != key2) continue
var key3 = 1
for (dig in Int.digits(p3)) key3 = key3 * primes[dig]
if (key2 == key3) {
if (count < 25) orm25.add(p1)
if (p1 >= j) {
counts.add(count)
j = j * 10
}
count = count + 1
}
}
counts.add(count)
System.print("Smallest members of first 25 Ormiston triples:")
Fmt.tprint("$,10d ", orm25, 5)
System.print()
j = 1e9
for (i in 0...counts.count) {
Fmt.print("$,d Ormiston triples before $,d", counts[i], j)
j = j * 10
System.print()
}
- Output:
Smallest members of 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 before 1,000,000,000 4,925 Ormiston triples before 10,000,000,000
Wren
This uses a segmented sieve to get up to 10 billion without running out of memory (bools in Wren require 8 bytes rather than one) and takes just over 13 minutes to achieve the stretch goal.
Limiting the search to a billion, takes about 73 seconds (68 seconds using our 'standard' sieve).
import "./math" for Int
import "./fmt" for Fmt
var limit = 1e10
var primes = Int.segmentedSieve(limit, 8)
var orm25 = []
var j = 1e9
var count = 0
var counts = []
for (i in 0...primes.count-2) {
var p1 = primes[i]
var p2 = primes[i+1]
var p3 = primes[i+2]
if ((p2 - p1) % 18 != 0 || (p3 - p2) % 18 != 0) continue
var key1 = 1
for (dig in Int.digits(p1)) key1 = key1 * primes[dig]
var key2 = 1
for (dig in Int.digits(p2)) key2 = key2 * primes[dig]
if (key1 != key2) continue
var key3 = 1
for (dig in Int.digits(p3)) key3 = key3 * primes[dig]
if (key2 == key3) {
if (count < 25) orm25.add(p1)
if (p1 >= j) {
counts.add(count)
j = j * 10
}
count = count + 1
}
}
counts.add(count)
System.print("Smallest members of first 25 Ormiston triples:")
Fmt.tprint("$,10d ", orm25, 5)
System.print()
j = 1e9
for (i in 0...counts.count) {
Fmt.print("$,d Ormiston triples before $,d", counts[i], j)
j = j * 10
System.print()
}
- Output:
Smallest members of first 25 Ormiston triples: 11,117,123 12,980,783 14,964,017 32,638,213 32,964,341 33,539,783 35,868,013 44,058,013 46,103,237 48,015,013 50,324,237 52,402,783 58,005,239 60,601,237 61,395,239 74,699,789 76,012,879 78,163,123 80,905,879 81,966,341 82,324,237 82,523,017 83,279,783 86,050,781 92,514,341 368 Ormiston triples before 1,000,000,000 4,925 Ormiston triples before 10,000,000,000
XPL0
Runs in 87 seconds on Pi4.
char Sieve;
proc MakeSieve(Size); \Make prime number sieve
int Size, Prime, I, K;
[Size:= Size/2; \ignore even numbers
Sieve:= MAlloc(Size+1); \(XPL0's heap only provides 64 MB)
for I:= 0 to Size do \set Sieve flags all true
Sieve(I):= true;
for I:= 0 to Size do
if Sieve(I) then \found a prime, which is equal to
[Prime:= I + I + 3; \ twice the index + 3
K:= I + Prime; \first multiple to strike off
while K <= Size do \strike off all multiples
[Sieve(K):= false;
K:= K + Prime;
];
];
];
func GetSig(N); \Return signature of N
\A "signature" is the count of each digit in N packed into a 32-bit word
int N, Sig;
[Sig:= 0;
repeat N:= N/10;
Sig:= Sig + 1<<(rem(0)*3);
until N = 0;
return Sig;
];
def Limit = 1_000_000_000;
int Cnt, N, N0, N1, Sig, Sig0, Sig1;
[MakeSieve(Limit);
Text(0, "Smallest members of first 25 Ormiston triples:^m^j");
Cnt:= 0; N0:= 0; N1:= 0; Sig0:= 0; Sig1:= 0; N:= 3;
Format(10, 0);
loop [if Sieve(N>>1-1) then \is prime
[Sig:= GetSig(N);
if Sig = Sig1 and Sig = Sig0 then
[Cnt:= Cnt+1;
if Cnt <= 25 then
[RlOut(0, float(N0));
if rem(Cnt/5) = 0 then CrLf(0);
];
];
Sig0:= Sig1; Sig1:= Sig;
N0:= N1; N1:= N;
];
if N >= Limit then
[IntOut(0, Cnt);
Text(0, " Ormiston triples before one billion.^m^j");
quit;
];
N:= N+2;
];
]
- Output:
Smallest members of 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 before one billion.