Ormiston pairs: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Rdm (talk | contribs)
6,963 edits
→‎{{header|J}}: more compact presentation
→‎{{header|ALGOL 68}}: Simplify and Improve using ideas from the Wren and XPL0 samples.
Line 28: Line 28:
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
{{libheader|ALGOL 68-primes}}
{{libheader|ALGOL 68-primes}}
{{libheader|ALGOL 68-rows}}
When running this with ALGOL 68G, you will need to specify a large heap size with e.g., <code>-heap 256M</code> on the ALGOL 68G command.
When running this with ALGOL 68G, you will need to specify a large heap size with e.g., <code>-heap 256M</code> on the ALGOL 68G command.
<br>
<br>
Uses the "signature" idea from the XPL0 sample and the "difference is 0 MOD 18" filter from the Wren sample.
<br>
Also shows the number of prime pairs whose difference is 0 MOD 18 but are not Ormiston pairs.
<syntaxhighlight lang="algol68">
<syntaxhighlight lang="algol68">
BEGIN # find some Orimiston pairs - pairs of primes where the first and next #
BEGIN # find some Orimiston pairs - pairs of primes where the first and next #
# prime are anagrams #
# prime are anagrams #
PR read "primes.incl.A68" PR # include prime utilities #
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 prime = 10 000 000; # maximum number we will consider #
INT max digits = BEGIN # count the digits of max prime #
INT max digits = BEGIN # count the digits of max prime #
Line 42: Line 45:
d
d
END;
END;
[ 0 : 9 ]LONG INT dp; # table of max digit powers for signature creation #
⚫
dp[ 0 ] := 1; FOR i TO UPB dp DO dp[ i ] := max digits * dp[ i - 1 ] OD;
[]BOOL prime = PRIMESIEVE max prime;
[]BOOL prime = PRIMESIEVE max prime;
# construct a list of the primes up to the maximum prime to consider #
# construct a list of the primes up to the maximum prime to consider #
[]INT prime list = EXTRACTPRIMESUPTO max prime FROMPRIMESIEVE prime;
[]INT prime list = EXTRACTPRIMESUPTO max prime FROMPRIMESIEVE prime;
# splits n into its digits, storing them in d #
# splits n into its digits, returning the sum of their counts, each #
⚫
# scaled by the digit power of max digits #
PROC get digits = ( REF[]INT d, INT n )VOID:
PROC get digits = ( INT n )LONG INT:
BEGIN
BEGIN
FOR i FROM LWB d TO UPB d DO d[ i ] := -1 OD;
INT v := n;
INT v := n;
LONG INT result := dp[ v MOD 10 ];
⚫
INT d pos := LWB d;
⚫
d[ d pos ] := v MOD 10;
WHILE ( v OVERAB 10 ) > 0 DO
WHILE ( v OVERAB 10 ) > 0 DO
d[ d pos +:= 1 ] := v MOD 10
result +:= dp[ v MOD 10 ]
OD
OD;
⚫
result
END # get digits # ;
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 #
# count the Ormiston pairs #
INT o count := 0;
INT o count := 0;
INT o30 := 0;
INT n count := 0;
FOR i WHILE o count < 30 DO
INT p10 := 100 000;
⚫
FOR i TO UPB prime list - 1 DO
INT p1 = prime list[ i ];
INT p1 = prime list[ i ];
INT p2 = prime list[ i + 1 ];
INT p2 = prime list[ i + 1 ];
IF same digits( p1, p2 ) THEN
IF ( p2 - p1 ) MOD 18 = 0 THEN
print( ( " (", whole( p1, -5 ), ", ", whole( p2, -5 ), ")"
# p2 and p1 might be anagrams #
, IF ( o count +:= 1 ) MOD 3 = 0 THEN newline ELSE " " FI
IF get digits( p1 ) /= get digits( p2 ) THEN
)
# not an Ormiston pair afterall #
);
n count +:= 1
o30 := i
ELSE
# p1 and p2 are an Ormiston pair #
FI
⚫
o count +:= 1;
OD;
IF o count <= 30 THEN
print( ( newline ) );
print( ( " (", whole( p1, -5 ), ", ", whole( p2, -5 ), ")"
INT p10 := 100 000;
, IF o count MOD 3 = 0 THEN newline ELSE " " FI
⚫
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
ELIF p1 >= p10 THEN
IF p1 > p10 THEN
print( ( whole( o count - 1, -9 )
print( ( whole( o count, -5 ), " Ormiston pairs below ", whole( p10, 0 ), newline ) );
, " Ormiston pairs below "
p10 *:= 10
, whole( p10, 0 )
FI;
, newline
o count +:= 1
)
⚫
);
⚫
p10 *:= 10
⚫
FI
⚫
FI
FI
FI
OD;
OD;
print( ( whole( o count, -5 ), " Ormiston pairs below ", whole( max prime, 0 ) ) )
print( ( whole( o count, -9 ), " Ormiston pairs below ", whole( max prime, 0 ), newline ) );
print( ( whole( n count, -9 ), " non-Ormiston ""0 MOD 18"" pairs bwlow ", whole( max prime, 0 ) ) )
END
END
</syntaxhighlight>
</syntaxhighlight>
Line 111: Line 109:
(65479, 65497) (66413, 66431) (74779, 74797)
(65479, 65497) (66413, 66431) (74779, 74797)
(75913, 75931) (76213, 76231) (76579, 76597)
(75913, 75931) (76213, 76231) (76579, 76597)
40 Ormiston pairs below 100000

40 Ormiston pairs below 100000
382 Ormiston pairs below 1000000
382 Ormiston pairs below 1000000
3722 Ormiston pairs below 10000000
3722 Ormiston pairs below 10000000
53369 non-Ormiston "0 MOD 18" pairs bwlow 10000000
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Ormiston_pairs"