Ormiston triples: Difference between revisions
Content added Content deleted
m (→{{header|J}}: typo) |
m (→{{header|Python}}: Remove unused import) |
||
| Line 340: | Line 340: | ||
<syntaxhighlight lang="python">import textwrap |
<syntaxhighlight lang="python">import textwrap |
||
from collections import Counter |
|||
from itertools import pairwise |
from itertools import pairwise |
||
from typing import Iterator |
from typing import Iterator |
||
Revision as of 09:54, 10 February 2023
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
An Ormiston triple is three consecutive prime numbers which are anagrams, i.e. contain the same decimal digits but in a different order.
- 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.
package main
import (
"fmt"
"rcu"
)
func main() {
const limit = 1e10
primes := rcu.Primes(limit)
var orm25 []int
j := int(1e9)
count := 0
var counts []int
for i := 0; i < len(primes)-2; i++ {
p1 := primes[i]
p2 := primes[i+1]
p3 := primes[i+2]
if (p2-p1)%18 != 0 || (p3-p2)%18 != 0 {
continue
}
key1 := 1
for _, dig := range rcu.Digits(p1, 10) {
key1 *= primes[dig]
}
key2 := 1
for _, dig := range rcu.Digits(p2, 10) {
key2 *= primes[dig]
}
if key1 != key2 {
continue
}
key3 := 1
for _, dig := range rcu.Digits(p3, 10) {
key3 *= primes[dig]
}
if key2 == key3 {
if count < 25 {
orm25 = append(orm25, p1)
}
if p1 >= j {
counts = append(counts, count)
j *= 10
}
count++
}
}
counts = append(counts, count)
fmt.Println("Smallest members of first 25 Ormiston triples:")
for i := 0; i < 25; i++ {
fmt.Printf("%8v ", orm25[i])
if (i+1)%5 == 0 {
fmt.Println()
}
}
fmt.Println()
j = int(1e9)
for i := 0; i < len(counts); i++ {
fmt.Printf("%s Ormiston triples before %s\n", rcu.Commatize(counts[i]), rcu.Commatize(j))
j *= 10
fmt.Println()
}
}
- 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
J
Taking the laziest approach here, we'll use the definition of isorm from the Ormiston pairs task:
omt=: (#~ isorm) _4 p: (#~ isorm) i.&.(p:inv) 1e9
#omt NB. number of ormiston triples less than a billion
368
5 5$omt NB. first prime of the first 25 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
Phix
-- -- demo\rosetta\Ormiston_triplets.exw -- ================================== -- -- Uses a segmented sieve, which is about half the speed of get_primes_le(), but uses far less memory. -- If permited, get_primes_le(1e10) would generate a result of 455,052,511 primes, more than 32 bit -- can cope with, and use over 6GB of ram, and take about 11mins 44s, that is on this box at least, -- whereas this processes them on-the-fly, and only uses about 6MB of memory (ie 0.1% of 6GB). -- with javascript_semantics atom t0 = time() procedure ormiston_triplets(atom limit) // Generate primes using the segmented sieve of Eratosthenes. // credit: https://gist.github.com/kimwalisch/3dc39786fab8d5b34fee integer segment_size = floor(sqrt(limit)), count = 0, i = 3, s = 3, triplen = 1 atom p1 = 2, p2, n = 3, nc = min(1e9,limit), low = 0, t1 = time()+1 sequence isprime = repeat(true,segment_size+1), primes = {}, multiples = {}, orm25 = repeat(0,25) while low<=limit do sequence sieve = repeat(true,segment_size+1) if time()>t1 then progress("Processing %,d/%,d (%3.2f%%)\r",{low,limit,(low/limit)*100}) t1 = time()+1 end if // current segment = [low, high] atom high = min(low+segment_size,limit) // generate sieving primes using simple sieve of Eratosthenes while i*i<=min(high,segment_size) do if isprime[i+1] then for j=i*i to segment_size by i do isprime[j+1] = false end for end if i += 2 end while // initialize sieving primes for segmented sieve while s*s<=high do if isprime[s+1] then primes &= s multiples &= s*s-low end if s += 2 end while // sieve the current segment for mi,j in multiples do integer k = primes[mi]*2 while j<segment_size do sieve[j+1] = false j += k end while multiples[mi] = j - segment_size end for while n<=high do if sieve[n-low+1] then // n is a prime if triplen=1 then if remainder(n-p1,18)=0 and sort(sprint(p1))=sort(sprint(n)) then p2 = n triplen = 2 else p1 = n end if elsif triplen=2 and remainder(n-p2,18)=0 and sort(sprint(p2))=sort(sprint(n)) then -- triplet found! if p1>=nc then string e = elapsed_short(time()-t0) progress("%,d Ormiston triplets before %,d (%s)\n", {count, nc, e}) nc *= 10 end if count += 1 if count<=25 then orm25[count] = sprintf("%d",{p1}) if count=25 then printf(1,"Smallest members of first 25 Ormiston triplets:\n%s\n",join_by(orm25,1,5)) end if end if -- overlapping (and leave triplen set to 2): p1 = p2 p2 = n -- (for disjoint-only just set triplen to 0) else p1 = n triplen = 1 end if end if n += 2 end while low += segment_size end while string e = elapsed_short(time()-t0) progress("%,d Ormiston triplets before %,d (%s)\n", {count, nc, e}) end procedure ormiston_triplets(iff(platform()=JS?1e8:1e9))
- Output:
With limit upped to 1e10
Smallest members of first 25 Ormiston triplets: 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 triplets before 1,000,000,000 (56s) 4,925 Ormiston triplets before 10,000,000,000 (21:32)
Note that running this under pwa/p2js shows 25<1e8 in 8s, a limit of 1e9 would get you a blank screen for 1min 25s
I have not the patience to see whether JavaScript would actually cope with 1e10, but it should (with a blank screen for at least half an hour).
Python
Using Python bindings for the primesieve C++ library, on my machine, this takes about 58 seconds to find Ormiston triples up to one billion, and just over 9 minutes up to 10 billion.
import textwrap
from itertools import pairwise
from typing import Iterator
from typing import List
import primesieve
def primes() -> Iterator[int]:
it = primesieve.Iterator()
while True:
yield it.next_prime()
def triplewise(iterable):
for (a, _), (b, c) in pairwise(pairwise(iterable)):
yield a, b, c
def is_anagram(a: int, b: int, c: int) -> bool:
return sorted(str(a)) == sorted(str(b)) == sorted(str(c))
def up_to_one_billion() -> int:
count = 0
for triple in triplewise(primes()):
if is_anagram(*triple):
count += 1
if triple[2] >= 1_000_000_000:
break
return count
def up_to_ten_billion() -> int:
count = 0
for triple in triplewise(primes()):
if is_anagram(*triple):
count += 1
if triple[2] >= 10_000_000_000:
break
return count
def first_25() -> List[int]:
rv: List[int] = []
for triple in triplewise(primes()):
if is_anagram(*triple):
rv.append(triple[0])
if len(rv) >= 25:
break
return rv
if __name__ == "__main__":
print("Smallest members of first 25 Ormiston triples:")
print(textwrap.fill(" ".join(str(i) for i in first_25())), "\n")
print(up_to_one_billion(), "Ormiston triples before 1,000,000,000")
print(up_to_ten_billion(), "Ormiston triples before 10,000,000,000")
- 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 4925 Ormiston triples before 10,000,000,000
Raku
use Lingua::EN::Numbers;
use List::Divvy;
my @primes = lazy (^∞).hyper.grep( &is-prime ).map: { $_ => .comb.sort.join };
my @Ormistons = @primes.kv.map: { $^value.key if $^value.value eq @primes[$^key+1].value eq @primes[$^key+2].value};
say "First twenty-five Ormiston triples:";
say @Ormistons[^25].batch(5)».join(', ').join: "\n";
say '';
say +@Ormistons.&before( *[0] > $_ ) ~ " Ormiston triples before " ~ .Int.&cardinal for 1e8, 1e9;
- Output:
First twenty-five 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 25 Ormiston triples before one hundred million 368 Ormiston triples before one billion
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.