Ormiston pairs: Difference between revisions
Content added Content deleted
(Added Go) |
(→{{header|J}}: more compact presentation) |
||
Line 238:
For this, we would like to be able to test if a prime number is the first value in an Ormiston pair:
<syntaxhighlight lang=J> isorm=: -:&(/:~)&":&> 4 p: ]</syntaxhighlight>
We could also use a routine to organize pairs of numbers as moderate width lines of text:
<syntaxhighlight lang=J> fmtpairs=: {{ names <@([,',',])&":/"1 y}}</syntaxhighlight>
Then the task becomes:
<syntaxhighlight lang=J> fmtpairs (,. 4 p:]) p:30{.I. isorm i.&.(p:inv) 1e6
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
+/isorm i.&.(p:inv) 1e6 NB. number of Ormiston pairs less than 1e6
382
|
Revision as of 14:07, 30 January 2023
Ormiston pairs 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.
An Ormiston pair is two consecutive prime numbers which are anagrams, i.e. contain the same decimal digits but in a different order.
(1913, 1931) is the first such pair.
- Task
- Find and show the first 30 Ormiston pairs.
- Find and show the count of Ormiston pairs up to one million.
- Stretch
- Find and show the count of Ormiston pairs up to ten million.
- See also
ALGOL 68
When running this with ALGOL 68G, you will need to specify a large heap size with e.g., -heap 256M
on the ALGOL 68G command.
BEGIN # find some Orimiston pairs - pairs of primes where the first and next #
# prime are anagrams #
PR read "primes.incl.A68" PR # include prime utilities #
PR read "rows.incl.a68" PR # include row (array) utilities #
INT max prime = 10 000 000; # maximum number we will consider #
INT max digits = BEGIN # count the digits of max prime #
INT v := 1;
INT d := 1;
WHILE ( v *:= 10 ) < max prime DO d +:= 1 OD;
d
END;
[]BOOL prime = PRIMESIEVE max prime;
# construct a list of the primes up to the maximum prime to consider #
[]INT prime list = EXTRACTPRIMESUPTO max prime FROMPRIMESIEVE prime;
# splits n into its digits, storing them in d #
PROC get digits = ( REF[]INT d, INT n )VOID:
BEGIN
FOR i FROM LWB d TO UPB d DO d[ i ] := -1 OD;
INT v := n;
INT d pos := LWB d;
d[ d pos ] := v MOD 10;
WHILE ( v OVERAB 10 ) > 0 DO
d[ d pos +:= 1 ] := v MOD 10
OD
END # get digits # ;
# returns TRUE if the digits of n are the same as those of m #
# FALSE otherwise #
PROC same digits = ( INT m, n )BOOL:
BEGIN
[ 1 : max digits ]INT md, nd;
get digits( md, m );
get digits( nd, n );
QUICKSORT md FROMELEMENT 1 TOELEMENT max digits;
QUICKSORT nd FROMELEMENT 1 TOELEMENT max digits;
BOOL same := TRUE;
FOR i TO max digits WHILE same := md[ i ] = nd[ i ] DO SKIP OD;
same
END # same digits # ;
# count the Ormiston pairs #
INT o count := 0;
INT o30 := 0;
FOR i WHILE o count < 30 DO
INT p1 = prime list[ i ];
INT p2 = prime list[ i + 1 ];
IF same digits( p1, p2 ) THEN
print( ( " (", whole( p1, -5 ), ", ", whole( p2, -5 ), ")"
, IF ( o count +:= 1 ) MOD 3 = 0 THEN newline ELSE " " FI
)
);
o30 := i
FI
OD;
print( ( newline ) );
INT p10 := 100 000;
FOR i FROM o30 + 1 TO UPB prime list - 1 DO
IF INT p1 = prime list[ i ];
same digits( p1, prime list[ i + 1 ] )
THEN
IF p1 > p10 THEN
print( ( whole( o count, -5 ), " Ormiston pairs below ", whole( p10, 0 ), newline ) );
p10 *:= 10
FI;
o count +:= 1
FI
OD;
print( ( whole( o count, -5 ), " Ormiston pairs below ", whole( max prime, 0 ) ) )
END
- Output:
( 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 below 100000 382 Ormiston pairs below 1000000 3722 Ormiston pairs below 10000000
Factor
USING: grouping io kernel lists lists.lazy math math.parser
math.primes.lists math.statistics prettyprint sequences ;
: ormistons ( -- list )
lprimes dup cdr lzip
[ first2 [ >dec histogram ] same? ] lfilter ;
"First 30 Ormiston pairs:" print
30 ormistons ltake list>array 5 group simple-table. nl
ormistons [ first 1e6 < ] lwhile llength pprint bl
"Ormiston pairs less than a million." print
- Output:
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 } 382 Ormiston pairs less than a million.
Go
package main
import (
"fmt"
"rcu"
"sort"
)
func areEqual(l1, l2 []int) bool {
len1 := len(l1)
len2 := len(l2)
if len1 != len2 {
return false
}
for i := 0; i < len1; i++ {
if l1[i] != l2[i] {
return false
}
}
return true
}
func main() {
const limit = 1e7
primes := rcu.Primes(limit)
var orm30 [][2]int
i := 0
j := int(1e5)
count := 0
var counts []int
for i < len(primes)-1 {
p1 := primes[i]
p2 := primes[i+1]
if (p2-p1)%18 != 0 {
i++
continue
}
d1 := rcu.Digits(p1, 10)
d2 := rcu.Digits(p2, 10)
sort.Ints(d1)
sort.Ints(d2)
if areEqual(d1, d2) {
if count < 30 {
orm30 = append(orm30, [2]int{p1, p2})
}
if p1 >= j {
counts = append(counts, count)
j *= 10
}
count++
i += 2
} else {
i++
}
}
counts = append(counts, count)
fmt.Println("First 30 Ormiston pairs:")
for i := 0; i < 30; i++ {
fmt.Printf("%5v ", orm30[i])
if (i+1)%3 == 0 {
fmt.Println()
}
}
fmt.Printf("\n%d Ormiston pairs before 100,000\n", counts[0])
fmt.Printf("%d Ormiston pairs before 1,000,000\n", counts[1])
fmt.Printf("%s Ormiston pairs before 10,000,000\n", rcu.Commatize(counts[2]))
}
- Output:
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 100,000 382 Ormiston pairs before 1,000,000 3,722 Ormiston pairs before 10,000,000
J
For this, we would like to be able to test if a prime number is the first value in an Ormiston pair:
isorm=: -:&(/:~)&":&> 4 p: ]
We could also use a routine to organize pairs of numbers as moderate width lines of text:
fmtpairs=: {{ names <@([,',',])&":/"1 y}}
Then the task becomes:
fmtpairs (,. 4 p:]) p:30{.I. isorm i.&.(p:inv) 1e6
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
+/isorm i.&.(p:inv) 1e6 NB. number of Ormiston pairs less than 1e6
382
+/isorm i.&.(p:inv) 1e7 NB. number of Ormiston pairs less than 1e7
3722
Raku
use Lingua::EN::Numbers;
use List::Divvy;
my @primes = lazy (^∞).hyper.grep: &is-prime;
my @Ormistons = @primes.kv.map: { ($^value, @primes[$^key+1]) if $^value.comb.Bag eqv @primes[$^key+1].comb.Bag };
say "First thirty Ormiston pairs:";
say @Ormistons[^30].batch(3)».map( { "({.[0].fmt: "%5d"}, {.[1].fmt: "%5d"})" } ).join: "\n";
say '';
say +@Ormistons.&before( *[1] > $_ ) ~ " Ormiston pairs before " ~ .Int.&cardinal for 1e5, 1e6, 1e7;
- Output:
First thirty 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
Wren
import "./math" for Int
import "./seq" for Lst
import "./fmt" for Fmt
var limit = 1e7
var primes = Int.primeSieve(limit)
var orm30 = []
var i = 0
var j = 1e5
var count = 0
var counts = []
while (i < primes.count-1) {
var p1 = primes[i]
var p2 = primes[i+1]
if ((p2 - p1) % 18 != 0) {
i = i + 1
continue
}
var d1 = Int.digits(p1)
var d2 = Int.digits(p2)
if (Lst.areEqual(d1.sort(), d2.sort())) {
if (count < 30) orm30.add([p1, p2])
if (p1 >= j) {
counts.add(count)
j = j * 10
}
count = count + 1
i = i + 2
} else {
i = i + 1
}
}
counts.add(count)
System.print("First 30 Ormiston pairs:")
Fmt.tprint("[$,6d] ", orm30, 3)
Fmt.print("\n$,d Ormiston pairs before 100,000", counts[0])
Fmt.print("$,d Ormiston pairs before 1,000,000", counts[1])
Fmt.print("$,d Ormiston pairs before 10,000,000", counts[2])
- Output:
First 30 Ormiston pairs: [ 1,913 1,931] [18,379 18,397] [19,013 19,031] [25,013 25,031] [34,613 34,631] [35,617 35,671] [35,879 35,897] [36,979 36,997] [37,379 37,397] [37,813 37,831] [40,013 40,031] [40,213 40,231] [40,639 40,693] [45,613 45,631] [48,091 48,109] [49,279 49,297] [51,613 51,631] [55,313 55,331] [56,179 56,197] [56,713 56,731] [58,613 58,631] [63,079 63,097] [63,179 63,197] [64,091 64,109] [65,479 65,497] [66,413 66,431] [74,779 74,797] [75,913 75,931] [76,213 76,231] [76,579 76,597] 40 Ormiston pairs before 100,000 382 Ormiston pairs before 1,000,000 3,722 Ormiston pairs before 10,000,000
XPL0
func IsPrime(N); \Return 'true' if N is prime
int N, I;
[if N <= 2 then return N = 2;
if (N&1) = 0 then \even >2\ return false;
for I:= 3 to sqrt(N) do
[if rem(N/I) = 0 then return false;
I:= I+1;
];
return true;
];
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;
];
int Cnt, N, N0, Sig, Sig0;
[Cnt:= 0; N0:= 0; Sig0:= 0; N:= 3;
Format(6, 0);
loop [if IsPrime(N) then
[Sig:= GetSig(N);
if Sig = Sig0 then
[Cnt:= Cnt+1;
if Cnt <= 30 then
[RlOut(0, float(N0)); RlOut(0, float(N));
if rem(Cnt/3) = 0 then CrLf(0) else Text(0, " ");
];
];
Sig0:= Sig;
N0:= N;
];
if N = 1_000_000-1 then
[Text(0, "^m^jOrmiston pairs up to one million: ");
IntOut(0, Cnt);
];
if N = 10_000_000-1 then
[Text(0, "^m^jOrmiston pairs up to ten million: ");
IntOut(0, Cnt);
quit;
];
N:= N+2;
];
]
- Output:
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 Ormiston pairs up to one million: 382 Ormiston pairs up to ten million: 3722