Rosetta Code

Ormiston pairs: Difference between revisions

Page Discussion

Ormiston pairs (view source)

Revision as of 21:25, 16 January 2024

12,713 bytes added ,  4 months ago
→‎{{header|Haskell}}: Fractionally more efficient
(Added AppleScript.)
(→‎{{header|Haskell}}: Fractionally more efficient)
(11 intermediate revisions by 9 users not shown)
Line 458:
Number of Ormiston pairs < 100000000: 34901
Number of Ormiston pairs < 1000000000: 326926
</pre>
 
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
Uses iterator to do both the first 30 and the millionth and 10 millionth pair. It is an easy way to make the same code do both showing a number of pairs and picking counts out of different points in the iteration.
 
<syntaxhighlight lang="Delphi">
 
{------- These subroutines would normally be in libraries, but they are included here for clairty------------- }
 
function IsPrime(N: int64): boolean;
{Fast, optimised prime test}
var I,Stop: int64;
begin
if (N = 2) or (N=3) then Result:=true
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false
else
begin
I:=5;
Stop:=Trunc(sqrt(N+0.0));
Result:=False;
while I<=Stop do
begin
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit;
Inc(I,6);
end;
Result:=True;
end;
end;
 
 
function GetNextPrime(Start: integer): integer;
{Get the next prime number after Start}
begin
repeat Inc(Start)
until IsPrime(Start);
Result:=Start;
end;
 
{-----------------------------------------------------------------------------------------------------}
 
 
type TPrimeInfo = record
Prime1,Prime2: integer;
Count: integer;
end;
 
type TOrmIterator = class(TObject)
Info: TPrimeInfo;
private
function IsOrmistonPair(P1, P2: integer): boolean;
protected
public
procedure Reset;
function GetNext: TPrimeInfo;
end;
 
 
function TOrmIterator.IsOrmistonPair(P1,P2: integer): boolean;
{Tests if P1 and P2 primes represent Ormiston Pairs}
{I}
var S1,S2: string;
var I,J: integer;
var SL1,SL2: TStringList;
begin
Result:=False;
SL1:=TStringList.Create;
SL2:=TStringList.Create;
try
{Copy characters in numbers into string lists}
SL1.Duplicates:=dupAccept;
SL2.Duplicates:=dupAccept;
S1:=IntToStr(P1); S2:=IntToStr(P2);
for I:=1 to Length(S1) do SL1.Add(S1[I]);
for I:=1 to Length(S2) do SL2.Add(S2[I]);
{Sort them }
SL1.Sort; SL2.Sort;
{And compare them item for item - any mismatch = not Ormiston Pair }
for I:=0 to Min(SL1.Count,SL2.Count)-1 do
if SL1[I]<>SL2[I] then exit;
Result:=True;
finally Sl1.Free; SL2.Free; end;
end;
 
 
procedure TOrmIterator.Reset;
{Restart iterator}
begin
Info.Count:=0;
Info.Prime1:=1; Info.Prime2:=3;
end;
 
 
function TOrmIterator.GetNext: TPrimeInfo;
{Iterate to next Ormiston Pair}
begin
while true do
begin
Info.Prime2:=GetNextPrime(Info.Prime1);
if IsOrmistonPair(Info.Prime1,Info.Prime2) then
begin
Inc(Info.Count);
Result:=Info;
Info.Prime1:=Info.Prime2;
break;
end
else Info.Prime1:=Info.Prime2;
end;
end;
 
 
procedure ShowOrmistonPairs(Memo: TMemo);
var I: integer;
var S: string;
var OI: TOrmIterator;
var Info: TPrimeInfo;
begin
{Create iterator}
OI:=TOrmIterator.Create;
try
OI.Reset;
{Iterate throug 1st 30 pairs}
for I:=1 to 30 do
begin
Info:=OI.GetNext;
S:=S+Format('(%6D %6D) ',[Info.Prime1,Info.Prime2]);
If (Info.Count mod 3)=0 then S:=S+CRLF;
end;
Memo.Lines.Add(S);
Memo.Lines.Add('Count='+IntToStr(Info.Count));
 
{iterate to millionth pair}
repeat Info:=OI.GetNext
until Info.Prime2>=1000000;
Memo.Lines.Add('1000,000 ='+IntToStr(Info.Count-1));
{iterate to 10 millionth pair}
repeat Info:=OI.GetNext
until Info.Prime2>=10000000;
Memo.Lines.Add('10,000,000 ='+IntToStr(Info.Count-1));
finally OI.Free; end;
end;
 
</syntaxhighlight>
{{out}}
<pre>
( 1913 1931) ( 18379 18397) ( 19013 19031)
( 25013 25031) ( 34613 34631) ( 35617 35671)
( 35879 35897) ( 36979 36997) ( 37379 37397)
( 37813 37831) ( 40013 40031) ( 40213 40231)
( 40639 40693) ( 45613 45631) ( 48091 48109)
( 49279 49297) ( 51613 51631) ( 55313 55331)
( 56179 56197) ( 56713 56731) ( 58613 58631)
( 63079 63097) ( 63179 63197) ( 64091 64109)
( 65479 65497) ( 66413 66431) ( 74779 74797)
( 75913 75931) ( 76213 76231) ( 76579 76597)
 
Count=30
1000,000 =382
10,000,000 =3722
Elapsed Time: 10.046 Sec.
 
</pre>
 
Line 638 ⟶ 800:
326,926 Ormiston pairs before 1,000,000,000
</pre>
 
=={{header|Haskell}}==
 
<syntaxhighlight lang=haskell>import Data.List (sort)
import Data.Numbers.Primes (primes)
 
---------------------- ORMISTON PAIRS --------------------
 
ormistonPairs :: [(Int, Int)]
ormistonPairs =
[ (fst a, fst b)
| (a, b) <- zip primeDigits (tail primeDigits),
snd a == snd b
]
 
primeDigits :: [(Int, String)]
primeDigits = (,) <*> (sort . show) <$> primes
 
--------------------------- TEST -------------------------
main :: IO ()
main =
putStrLn "First 30 Ormiston pairs:"
>> mapM_ print (take 30 ormistonPairs)
>> putStrLn "\nCount of Ormistons up to 1,000,000:"
>> print (length (takeWhile ((<= 1000000) . snd) ormistonPairs))</syntaxhighlight>
 
{{Out}}
<pre>First 30 Ormiston pairs:
(1913,1931)
(18379,18397)
(19013,19031)
(25013,25031)
(34613,34631)
(35617,35671)
(35879,35897)
(36979,36997)
(37379,37397)
(37813,37831)
(40013,40031)
(40213,40231)
(40639,40693)
(45613,45631)
(48091,48109)
(49279,49297)
(51613,51631)
(55313,55331)
(56179,56197)
(56713,56731)
(58613,58631)
(63079,63097)
(63179,63197)
(64091,64109)
(65479,65497)
(66413,66431)
(74779,74797)
(75913,75931)
(76213,76231)
(76579,76597)
 
Count of Ormistons up to 1,000,000:
382</pre>
 
=={{header|J}}==
Line 662 ⟶ 885:
+/isorm i.&.(p:inv) 1e7 NB. number of Ormiston pairs less than 1e7
3722</syntaxhighlight>
 
=={{header|jq}}==
{{works with|jq}}
'''Preliminaries'''
<syntaxhighlight lang=jq>
# Input: a positive integer
# Assuming . > 2, return an array, $a, of length .+1 such that
# $a[$i]Output: isan $i ifarray, $ia, isof prime,length and.+1 nullsuch otherwise.that
# $a[$i] is $i if $i is prime, and false otherwise.
def primeSieve:
# erase(i) sets .[i*j] to false for integral j > 1
def erase($i):
if .[$i] then
reduce (range(2*$i; (1 + length) /; $i)) as $j (.; .[i * $j] = nullfalse)
else .
end;
Line 730 ⟶ 955:
3722 Ormiston pairs before 10000000
</pre>
 
=={{header|Julia}}==
{{trans|Python}}
<syntaxhighlight lang="Julia">using Primes
 
function testormistons(toshow = 30, lim = 1_000_000)
pri = primes(lim)
csort = [sort!(collect(string(i))) for i in pri]
ormistons = [(pri[i - 1], pri[i]) for i in 2:lastindex(pri) if csort[i - 1] == csort[i]]
println("First $toshow Ormiston pairs under $lim:")
for (i, o) in enumerate(ormistons)
i > toshow && break
print("(", lpad(first(o), 6), lpad(last(o), 6), " )", i % 5 == 0 ? "\n" : " ")
end
println("\n", length(ormistons), " is the count of Ormiston pairs up to one million.")
end
 
testormistons()
</syntaxhighlight>{{out}} Same as Python example.
 
=={{header|Nim}}==
<syntaxhighlight lang=Nim>import std/[algorithm, bitops, math, strformat, strutils]
 
type Sieve = object
data: seq[byte]
 
func `[]`(sieve: Sieve; idx: Positive): bool =
## Return value of element at index "idx".
let idx = idx shr 1
let iByte = idx shr 3
let iBit = idx and 7
result = sieve.data[iByte].testBit(iBit)
 
func `[]=`(sieve: var Sieve; idx: Positive; val: bool) =
## Set value of element at index "idx".
let idx = idx shr 1
let iByte = idx shr 3
let iBit = idx and 7
if val: sieve.data[iByte].setBit(iBit)
else: sieve.data[iByte].clearBit(iBit)
 
func newSieve(lim: Positive): Sieve =
## Create a sieve with given maximal index.
result.data = newSeq[byte]((lim + 16) shr 4)
 
func initPrimes(lim: Positive): seq[Natural] =
## Initialize the list of primes from 2 to "lim".
var composite = newSieve(lim)
composite[1] = true
for n in countup(3, sqrt(lim.toFloat).int, 2):
if not composite[n]:
for k in countup(n * n, lim, 2 * n):
composite[k] = true
result.add 2
for n in countup(3, lim, 2):
if not composite[n]:
result.add n
 
let primes = initPrimes(100_000_000)
 
func digits(n: Positive): seq[int] =
## Return the sorted list of digits of "n".
var n = n.Natural
while n != 0:
result.add n mod 10
n = n div 10
result.sort()
 
echo "First 30 Ormiston pairs:"
var count = 0
var limit = 100_000
for i in 1..(primes.len - 2):
let p1 = primes[i]
let p2 = primes[i + 1]
if p1.digits == p2.digits:
inc count
if count <= 30:
stdout.write &"({p1:5}, {p2:5})"
stdout.write if count mod 3 == 0: '\n' else: ' '
if count == 30: echo()
elif p1 >= limit:
echo &"Number of Ormiston pairs below {insertSep($limit)}: {count - 1}"
limit *= 10
if limit == 100_000_000:
break
</syntaxhighlight>
 
{{out}}
<pre>First 30 Ormiston pairs:
( 1913, 1931) (18379, 18397) (19013, 19031)
(25013, 25031) (34613, 34631) (35617, 35671)
(35879, 35897) (36979, 36997) (37379, 37397)
(37813, 37831) (40013, 40031) (40213, 40231)
(40639, 40693) (45613, 45631) (48091, 48109)
(49279, 49297) (51613, 51631) (55313, 55331)
(56179, 56197) (56713, 56731) (58613, 58631)
(63079, 63097) (63179, 63197) (64091, 64109)
(65479, 65497) (66413, 66431) (74779, 74797)
(75913, 75931) (76213, 76231) (76579, 76597)
 
Number of Ormiston pairs below 100_000: 40
Number of Ormiston pairs below 1_000_000: 382
Number of Ormiston pairs below 10_000_000: 3722
</pre>
 
=={{header|Pascal}}==
==={{header|Free Pascal}}===
Line 1,176 ⟶ 1,506:
@home real 0m6,873s user 0m6,864s sys 0m0,008s
</pre>
 
=={{header|Perl}}==
{{libheader|ntheory}}
<syntaxhighlight lang="perl" line>use strict;
use warnings;
use feature 'say';
use ntheory <primes vecfirstidx>;
 
my(@O,$pairs);
my @primes = @{ primes(1,1e8) };
my @A = map { join '', sort split '', $_ } @primes;
for (1..$#primes-1) { push @O, $_ if $A[$_] eq $A[$_+1] }
 
say "First 30 Ormiston pairs:";
$pairs .= sprintf "(%5d,%5d) ", $primes[$_], $primes[$_+1] for @O[0..29];
say $pairs =~ s/.{42}\K/\n/gr;
 
for (
[1e5, 'one hundred thousand'],
[1e6, 'one million'],
[1e7, 'ten million']
) {
my($limit,$text) = @$_;
my $i = vecfirstidx { $primes[$_] >= $limit } @O;
printf "%4d Ormiston pairs before %s\n", $i, $text;
}</syntaxhighlight>
{{out}}
<pre>First 30 Ormiston pairs:
( 1913, 1931) (18379,18397) (19013,19031)
(25013,25031) (34613,34631) (35617,35671)
(35879,35897) (36979,36997) (37379,37397)
(37813,37831) (40013,40031) (40213,40231)
(40639,40693) (45613,45631) (48091,48109)
(49279,49297) (51613,51631) (55313,55331)
(56179,56197) (56713,56731) (58613,58631)
(63079,63097) (63179,63197) (64091,64109)
(65479,65497) (66413,66431) (74779,74797)
(75913,75931) (76213,76231) (76579,76597)
 
40 Ormiston pairs before one hundred thousand
382 Ormiston pairs before one million
3722 Ormiston pairs before ten million</pre>
 
=={{header|Phix}}==
Line 1,412 ⟶ 1,784:
382 Ormiston pairs before one million
3722 Ormiston pairs before ten million</pre>
 
=={{header|Ring}}==
<syntaxhighlight lang="ring">
see "working..." + nl
see "First 30 Ormiston pairs:" + nl
limit = 1000000
Primes = []
Primes1 = []
Primes2 = []
 
add(Primes,2)
pr = 1
while true
pr = pr + 2
if isPrime(pr) and pr < limit
add(Primes,pr)
ok
if pr > limit
exit
ok
end
 
n = 0
row = 0
 
for n = 1 to len(Primes) - 1
Primes1 = []
Primes2 = []
str1 = string(Primes[n])
str2 = string(Primes[n+1])
for p = 1 to len(str1)
add(Primes1,substr(str1,p,1))
next
for p = 1 to len(str2)
add(Primes2,substr(str2,p,1))
next
Sort1 = sort(Primes1)
Sort2 = sort(Primes2)
 
flag = 1
if len(Sort1) = len(Sort2)
for p = 1 to len(Sort1)
if Sort1[p] != Sort2[p]
flag = 0
exit
ok
next
if flag = 1
row++
if row < 31
str1m = str1
str2m = str2
see "(" + str1 + ", " + str2 + ") "
if row % 3 = 0
see nl
ok
ok
ok
ok
end
see nl + "Number of pairs < 1,000,000: " + row + nl
see "done..." + nl
 
func isPrime num
if (num <= 1) return 0 ok
if (num % 2 = 0 and num != 2) return 0 ok
for i = 3 to floor(num / 2) -1 step 2
if (num % i = 0) return 0 ok
next
return 1
</syntaxhighlight>
{{out}}
<pre>
working...
First 30 Ormiston pairs:
( 1913, 1931) (18379, 18397) (19013, 19031)
(25013, 25031) (34613, 34631) (35617, 35671)
(35879, 35897) (36979, 36997) (37379, 37397)
(37813, 37831) (40013, 40031) (40213, 40231)
(40639, 40693) (45613, 45631) (48091, 48109)
(49279, 49297) (51613, 51631) (55313, 55331)
(56179, 56197) (56713, 56731) (58613, 58631)
(63079, 63097) (63179, 63197) (64091, 64109)
(65479, 65497) (66413, 66431) (74779, 74797)
(75913, 75931) (76213, 76231) (76579, 76597)
Number of pairs < 1,000,000: 382
done...
</pre>
 
 
=={{header|RPL}}==
{{works with|HP|49}}
« →STR { 10 } 0 CON
1 PICK3 SIZE '''FOR''' j
OVER j DUP SUB STR→ 1 +
DUP2 GET 1 + PUT
'''NEXT''' NIP
» '<span style="color:blue">DIGCNT</span>' STO <span style="color:grey">''@ ( n → [ count0 .. count9 ] ) ''</span>
« 0 { } 2 3
'''WHILE''' DUP 1E6 < '''REPEAT'''
'''IF''' DUP2 <span style="color:blue">DIGCNT</span> SWAP <span style="color:blue">DIGCNT</span> == '''THEN'''
'''IF''' PICK3 SIZE 30 < '''THEN'''
DUP2 2 →LIST 1 →LIST 4 ROLL SWAP + UNROT
'''END'''
4 ROLL 1 + 4 ROLLD
'''END'''
NIP DUP NEXTPRIME
'''END''' DROP2 SWAP
» '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
2: {{1913 1931} {18379 18397} {19013 19031} {25013 25031} {34613 34631} {35617 35671} {35879 35897} {36979 36997} {37379 37397} {37813 37831} {40013 40031} {40213 40231} {40639 40693} {45613 45631} {48091 48109} {49279 49297} {51613 51631} {55313 55331} {56179 56197} {56713 56731} {58613 58631} {63079 63097} {63179 63197} {64091 64109} {65479 65497} {66413 66431} {74779 74797} {75913 75931} {76213 76231} {76579 76597}}
1: 382
</pre>
 
=={{header|Rust}}==
Line 1,493 ⟶ 1,980:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int
import "./fmt" for Fmt
 
Hout
9,655

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/339603...358343"