Anaprimes: Difference between revisions
Content deleted Content added
m →{{header|Phix}}: in |
|||
(26 intermediate revisions by 14 users not shown) | |||
Line 1:
{{
Anaprimes are prime numbers that are anagrams of each other, i.e. they use exactly the same digits with the same frequency but in a different order.
Line 31:
=={{header|ALGOL 68}}==
If running this with Algol 68G, a large heap size must be requested on the command line with, e.g.: <code>-heap 512M</code> for version 2 under Windows. On TIO.RUN, it wanted <code>-heap=512M</code>. If max prime is set to 100 000 000, the heap size needs to be 1536M (which I think is thge largest size Algol 68G allows).
<syntaxhighlight lang="algol68">
BEGIN # find some anaprimes: groups of primes that have the same digits and #
# so are anagrams #
INT max prime = 10 000 000; # maximum number we will consider #
[ 0 : max prime ]BOOL prime; # sieve the primes to max prime #
prime[ 0 ] := prime[ 1 ] := FALSE;
prime[ 2 ] := TRUE;
FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] := TRUE OD;
FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO
IF prime[ i ] THEN
FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD
FI
OD;
# construct a table of ordered digits of primes #
# pd[ i ] 0 if no prime with its digits in order = i, #
# > 0 if there is a group of primes with ordered digits = i #
# pd[ i ] is then the final prime in the group #
# < 0 if there is a group of primes with ordered digits = i #
# ABS pd[ i ] is then the next prime in the group #
# if i is not itself prime, the final element in the chain will #
# be 0 #
[ 0 : max prime ]INT pd; FOR i FROM LWB pd TO UPB pd DO pd[ i ] := 0 OD;
FOR p FROM UPB prime BY -1 TO LWB prime DO
IF prime[ p ] THEN
# have a prime - order its digits #
[ 0 : 9 ]INT d count; FOR i FROM 0 TO 9 DO d count[ i ] := 0 OD;
INT v := p;
WHILE d count[ v MOD 10 ] +:= 1;
( v OVERAB 10 ) > 0
DO SKIP OD;
# get the digits in descending order, so e.g.: 103 yields 310 #
INT ordered digits := 0;
FOR i FROM 9 BY -1 TO 0 DO
FOR n TO d count[ i ] DO
ordered digits *:= 10 +:= i
OD
OD;
IF pd[ ordered digits ] /= 0 THEN
# there was a previous prime with these digits #
pd[ p ] := - pd[ ordered digits ]
FI;
pd[ ordered digits ] := p
FI
OD;
# display information about the groups #
INT p10 := 10;
WHILE p10 < max prime DO
# find the groups in p10..p10*10 #
INT min element := 0;
INT max element := 0;
INT group count := 0;
INT group length := 0;
INT length count := 0;
INT range end = ( p10 * 10 ) - 1;
FOR g FROM p10 TO range end DO
IF pd[ g ] < 0 THEN
# a group starts here #
group count +:= 1;
INT this max := ABS pd[ g ];
INT this length := 2;
WHILE pd[ this max ] < 0 DO
INT prev max := this max;
this max := ABS pd[ this max ];
this length +:= 1;
pd[ prev max ] := 0
OD;
IF this length > group length THEN
# found a longer group #
IF pd[ this max ] > 0 THEN
min element := pd[ this max ]
ELSE
min element := g
FI;
max element := this max;
group length := this length;
length count := 1
ELIF this length = group length THEN
# have another group of the same length #
length count +:= 1
FI
FI
OD;
print( ( "Anaprime groups in ", whole( p10, 0 )
, "..", whole( range end, 0 )
, ": ", whole( group count, 0 )
, "; "
, IF group count = length count
THEN "all"
ELSE whole( length count, 0 )
FI
, IF length count = 1
THEN " has"
ELSE " have"
FI
, " maximum length(", whole( group length, 0 )
, "), first: ", whole( min element, 0 )
, IF group length = 2
THEN ", "
ELSE ", ... "
FI
, whole( max element, 0 )
, newline
)
);
p10 *:= 10
OD
END
</syntaxhighlight>
{{out}}
<pre>
Anaprime groups in 10..99: 4; all have maximum length(2), first: 13, 31
Anaprime groups in 100..999: 42; 3 have maximum length(4), first: 149, ... 941
Anaprime groups in 1000..9999: 261; 2 have maximum length(11), first: 1237, ... 7321
Anaprime groups in 10000..99999: 1006; 1 has maximum length(39), first: 13789, ... 98731
Anaprime groups in 100000..999999: 2868; 1 has maximum length(148), first: 123479, ... 974213
Anaprime groups in 1000000..9999999: 6973; 1 has maximum length(731), first: 1235789, ... 9875321
</pre>
=={{header|C++}}==
{{libheader|Primesieve}}
This takes about 70 seconds on my system. Memory usage is 4G.
<syntaxhighlight lang="cpp">#include <
#include <iostream>
#include <map>
Line 43 ⟶ 163:
#include <primesieve.hpp>
digit_set get_digits(uint64_t n) {
for (; n > 0; n /= 10)
++result[n % 10];
return result;
}
int main() {
std::cout.imbue(std::locale(""));
primesieve::iterator pi;
using map_type =
std::map<digit_set, std::vector<uint64_t>, std::greater<digit_set>>;
map_type anaprimes;
for (uint64_t limit = 1000; limit <= 10000000000;) {
Line 90 ⟶ 201:
limit *= 10;
}
anaprimes[
}
}</syntaxhighlight>
Line 123 ⟶ 234:
First: 1,123,465,789 Last: 9,876,543,211
</pre>
=={{header|EasyLang}}==
<syntaxhighlight lang=text>
fastfunc isprim num .
if num mod 2 = 0
if num = 2
return 1
.
return 0
.
i = 3
while i <= sqrt num
if num mod i = 0
return 0
.
i += 2
.
return 1
.
fastfunc nextprim prim .
repeat
prim += 1
until isprim prim = 1
.
return prim
.
func group n .
while n > 0
d = n mod 10
n = n div 10
h = pow 10 d
r += h
.
return r
.
hashsz = 199999
len hashind[] hashsz
len hashval[] hashsz
global maxcnt grcnt[] grmax[] grmin[] .
#
func hash ind .
hi = ind mod hashsz + 1
while hashind[hi] <> 0 and hashind[hi] <> ind
hi = hi mod hashsz + 1
.
return hi
.
prim = 1
for limit in [ 1000 10000 100000 1000000 ]
repeat
prim = nextprim prim
until prim >= limit
g = group prim
hi = hash g
if hashind[hi] = 0
hashind[hi] = g
grcnt[] &= 1
grmax[] &= prim
grmin[] &= prim
hashval[hi] = len grcnt[]
else
i = hashval[hi]
grcnt[i] += 1
grmax[i] = higher grmax[i] prim
grmin[i] = lower grmin[i] prim
maxcnt = higher grcnt[i] maxcnt
.
.
print maxcnt
for i to len grcnt[]
if grcnt[i] = maxcnt
print grmin[i] & " " & grmax[i]
.
.
print ""
.
</syntaxhighlight>
{{out}}
<pre>
4
149 941
179 971
379 937
11
1237 7321
1279 9721
39
13789 98731
148
123479 974213
</pre>
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]
<syntaxhighlight lang="fsharp">
// Anaprimes. Nigel Galloway: February 2nd., 2023
let fN g=let i=Array.zeroCreate<int>10
let rec fN g=if g<10 then i[g]<-i[g]+1 else i[g%10]<-i[g%10]+1; fN (g/10)
fN g; i
let aP n=let _,n=primes32()|>Seq.skipWhile((>)(pown 10 (n-1)))|>Seq.takeWhile((>)(pown 10 n-1))|>Seq.groupBy fN|>Seq.maxBy(fun(_,n)->Seq.length n)
let n=Array.ofSeq n
(n.Length,Array.min n,Array.max n)
[3..9]|>List.map aP|>List.iteri(fun i (n,g,l)->printfn $"%d{i+3} digits: Count=%d{n} Min=%d{g} Max=%d{l}")
</syntaxhighlight>
{{out}}
<pre>
3 digits: Count=4 Min=149 Max=941
4 digits: Count=11 Min=1237 Max=7321
5 digits: Count=39 Min=13789 Max=98731
6 digits: Count=148 Min=123479 Max=974213
7 digits: Count=731 Min=1235789 Max=9875321
8 digits: Count=4333 Min=12345769 Max=97654321
9 digits: Count=26519 Min=102345697 Max=976542103
</pre>
Line 212 ⟶ 440:
First: 1,123,465,789 Last: 9,876,543,211
</pre>
=={{header|J}}==
Here, we'll define the "largeness" of a group of primes as its sum.
<syntaxhighlight lang=J>dgt=: 10&#.inv
dgrp=: </.~ /:~"1&.dgt
pgrp=: {{dgrp p:(+ i.)/(-/)\ p:inv 0 _1+10^_1 0+y}}
big=: \: +/@>
largest=: 0 {:: big</syntaxhighlight>
Here, <code>dgt</code> gives use the base 10 digits of a number, <code>dgrp</code> groups numbers which contain the same digits, <code>pgrp</code> groups all primes of a given digit count by their digits, <code>big</code> sorts groups of numbers in descending order by their sum and <code>largest</code> extracts a group of numbers with the largest sum.
With these definitions, the count, min and max of prime groups with various (base 10) digit lengths are:
<syntaxhighlight lang=J> (#,<./,>./) largest pgrp 1
1 7 7
(#,<./,>./) largest pgrp 2
2 79 97
(#,<./,>./) largest pgrp 3
4 379 937
(#,<./,>./) largest pgrp 4
10 1789 9871
(#,<./,>./) largest pgrp 5
39 13789 98731
(#,<./,>./) largest pgrp 6
141 136879 987631
(#,<./,>./) largest pgrp 7
708 1345879 9874531
(#,<./,>./) largest pgrp 8
4192 13456879 98765431
(#,<./,>./) largest pgrp 9
26455 103456789 987654103</syntaxhighlight>
Note that we could instead look for a longest group, where length is defined as the count of the primes in a group. That would give us:
<syntaxhighlight lang=J> longest=: 0 {:: (\: #@>)
(#,<./,>./) longest pgrp 1
1 7 7
(#,<./,>./) longest pgrp 2
2 79 97
(#,<./,>./) longest pgrp 3
4 179 971
(#,<./,>./) longest pgrp 4
11 1279 9721
(#,<./,>./) longest pgrp 5
39 13789 98731
(#,<./,>./) longest pgrp 6
148 123479 974213
(#,<./,>./) longest pgrp 7
731 1235789 9875321
(#,<./,>./) longest pgrp 8
4333 12345769 97654321
(#,<./,>./) longest pgrp 9
26519 102345697 976542103</syntaxhighlight>
=={{header|jq}}==
Line 220 ⟶ 502:
'''General utilities'''
<syntaxhighlight lang=jq>
# Input: a positive integer
#
# $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;
else .
end;
Line 335 ⟶ 618:
186.920326 seconds (455.94 M allocations: 72.961 GiB, 1.54% gc time, 0.02% compilation time)
</pre>
=={{header|Nim}}==
{{trans|Wren}}
Run in 14 seconds on an Intel Core i5-8250U (four cores at 1.60GHz).
<syntaxhighlight lang="Nim">import std/[algorithm, bitops, math, strformat, strutils, tables]
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
proc digits(n: Positive): seq[0..9] =
var n = n.Natural
while n != 0:
result.add n mod 10
n = n div 10
const Limit = 1_000_000_000
const MaxIndex = log10(Limit.toFloat).int
let primes = initPrimes(Limit)
var anaPrimes: Table[int, seq[int]]
for p in primes:
var key = 1
for digit in p.digits:
key *= primes[digit]
anaPrimes.mgetOrPut(key, @[]).add p
var largest: array[1..MaxIndex, int]
var groups: array[1..MaxIndex, seq[seq[int]]]
for key, values in anaPrimes.pairs:
let nd = values[0].digits.len
if values.len > largest[nd]:
largest[nd] = values.len
groups[nd] = @[values]
elif values.len == largest[nd]:
groups[nd].add values
var j = 1000
for i in 3..MaxIndex:
echo &"Largest group(s) of anaprimes before {insertSep($j)}: {largest[i]} members:"
groups[i].sort(proc (x, y: seq[int]): int = cmp(x[0], y[0]))
for g in groups[i]:
echo &" First: {insertSep($g[0])} Last: {insertSep($g[^1])}"
j *= 10
echo()
</syntaxhighlight>
{{out}}
<pre>Largest group(s) of anaprimes before 1_000: 4 members:
First: 149 Last: 941
First: 179 Last: 971
First: 379 Last: 937
Largest group(s) of anaprimes before 10_000: 11 members:
First: 1_237 Last: 7_321
First: 1_279 Last: 9_721
Largest group(s) of anaprimes before 100_000: 39 members:
First: 13_789 Last: 98_731
Largest group(s) of anaprimes before 1_000_000: 148 members:
First: 123_479 Last: 974_213
Largest group(s) of anaprimes before 10_000_000: 731 members:
First: 1_235_789 Last: 9_875_321
Largest group(s) of anaprimes before 100_000_000: 4333 members:
First: 12_345_769 Last: 97_654_321
Largest group(s) of anaprimes before 1_000_000_000: 26519 members:
First: 102_345_697 Last: 976_542_103
</pre>
=={{header|Pascal}}==
==={{header|Free Pascal}}===
Not as fast as other versions, with runtime of 260s for 10 digits. ( Ryzen 5600G, 16 GB, 4.4 Ghz )
<syntaxhighlight lang="pascal">
program AnaPrimes;
{$IFDEF FPC}
{$MODE DELPHI}
{$OPTIMIZATION ON,ALL}
{$ELSE}
{$APPLICATION CONSOLE}
{$ENDIF}
uses
sysutils;
const
Limit= 100*1000*1000;
type
tPrimesSieve = array of boolean;
tElement = Uint64;
tarrElement = array of tElement;
tpPrimes = pBoolean;
const
cTotalSum = 16;
cMaxCardsOnDeck = cTotalSum;
CMaxCardsUsed = cTotalSum;
type
tDeckIndex = 0..cMaxCardsOnDeck-1;
tSequenceIndex = 0..CMaxCardsUsed;
tDiffCardCount = Byte;
tSetElem = packed record
Elemcount : tDeckIndex;
Elem : tDiffCardCount;
end;
tSetRange = low(tDeckIndex)..High(tDeckIndex);
tRemSet = array [low(tDeckIndex)..High(tDeckIndex)] of tSetElem;
tpRemSet = ^tRemSet;
tRemainSet = array [tSequenceIndex] of tRemSet;
tCardSequence = array [tSequenceIndex] of tDiffCardCount;
tChain = record
StartNum,
EndNum,
chainLength : Int64;
end;
var
PrimeSieve : tPrimesSieve;
gblTestChain : tChain;
//*********** Sieve of erathostenes
procedure ClearAll;
begin
setlength(PrimeSieve,0);
end;
function BuildWheel(pPrimes:tpPrimes;lmt:Uint64): Uint64;
var
wheelSize, wpno, pr, pw, i, k: NativeUint;
wheelprimes: array[0..15] of byte;
begin
pr := 1;//the mother of all numbers 1 ;-)
pPrimes[1] := True;
WheelSize := 1;
wpno := 0;
repeat
Inc(pr);
//pw = pr projected in wheel of wheelsize
pw := pr;
if pw > wheelsize then
Dec(pw, wheelsize);
if pPrimes[pw] then
begin
k := WheelSize + 1;
//turn the wheel (pr-1)-times
for i := 1 to pr - 1 do
begin
Inc(k, WheelSize);
if k < lmt then
move(pPrimes[1], pPrimes[k - WheelSize], WheelSize)
else
begin
move(pPrimes[1], pPrimes[k - WheelSize], Lmt - WheelSize * i);
break;
end;
end;
Dec(k);
if k > lmt then
k := lmt;
wheelPrimes[wpno] := pr;
pPrimes[pr] := False;
Inc(wpno);
WheelSize := k;//the new wheelsize
//sieve multiples of the new found prime
i := pr;
i := i * i;
while i <= k do
begin
pPrimes[i] := False;
Inc(i, pr);
end;
end;
until WheelSize >= lmt;
//re-insert wheel-primes 1 still stays prime
while wpno > 0 do
begin
Dec(wpno);
pPrimes[wheelPrimes[wpno]] := True;
end;
result := pr;
end;
procedure Sieve(pPrimes:tpPrimes;lmt:Uint64);
var
sieveprime, fakt, i: UInt64;
begin
sieveprime := BuildWheel(pPrimes,lmt);
repeat
repeat
Inc(sieveprime);
until pPrimes[sieveprime];
fakt := Lmt div sieveprime;
while Not(pPrimes[fakt]) do
dec(fakt);
if fakt < sieveprime then
BREAK;
i := (fakt + 1) mod 6;
if i = 0 then
i := 4;
repeat
pPrimes[sieveprime * fakt] := False;
repeat
Dec(fakt, i);
i := 6 - i;
until pPrimes[fakt];
if fakt < sieveprime then
BREAK;
until False;
until False;
pPrimes[1] := False;//remove 1
end;
procedure InitAndGetPrimes;
begin
setlength(PrimeSieve,Limit+1);
Sieve(@PrimeSieve[0],Limit);
end;
//*********** End Sieve of erathostenes
{$ALIGN 32}
type
tCol = Int32;
tFreeCol = Array[0..CMaxCardsUsed] of tCol;
var
RemainSets : tRemainSet;
PrmDgts :tFreeCol;
maxDgt,
gblMaxCardsUsed,
gblMaxUsedIdx,
gblPermCount : NativeInt;
//**************** Permutator
procedure EvaluatePerm;
var
j,k : NativeUint;
Begin
j := PrmDgts[0];
for k := 1 to maxDgt do
j := 10*j+PrmDgts[k];
If PrimeSieve[j] then
begin
PrimeSieve[j] := false;
with gblTestChain do
begin
EndNum := j;
inc(ChainLength);
end;
end;
end;
function shouldSwap(var PrmDgts:tFreeCol;start,curr :int32):boolean;
begin
for start := start to curr-1 do
if PrmDgts[start] = PrmDgts[curr] then
EXIT(false);
result := true;
end;
procedure Permutate(var PrmDgts:tFreeCol;index:Int32);
const
mask = (1 shl 1) OR (1 shl 3) OR (1 shl 7) OR (1 shl 9);
var
i : Int32;
tmp : tCol;
begin
if index < maxDgt then
begin
for i := index to maxDgt do
if shouldSwap(PrmDgts, index, i) then
begin
tmp:= PrmDgts[i];PrmDgts[i] := PrmDgts[index];PrmDgts[index]:= tmp;
Permutate(PrmDgts, index+1);
tmp:= PrmDgts[i];PrmDgts[i] := PrmDgts[index];PrmDgts[index]:= tmp;
end;
end
else
if PrmDgts[0] <> 0 then
if (1 shl PrmDgts[maxDgt]) AND mask <> 0 then
Begin
inc(gblpermCount);
EvaluatePerm;
end;
end;
procedure CheckChain(n,dgtcnt:Uint64);
var
dgts : array[0..9] of Uint32;
i,k,idx : Int32;
begin
gblTestChain.StartNum := n;
gblTestChain.chainLength := 0;
fillChar(dgts,SizeOF(dgts),#0);
fillChar(PrmDgts,SizeOF(PrmDgts),#0);
For i := 1 to dgtcnt do
Begin
inc(dgts[n MOD 10]);
n := n div 10;
end;
idx := 0;
For i := 0 to 9 do
For k := dgts[i] downto 1 do
begin
PrmDgts[idx]:= i;
inc(idx);
end;
Permutate(PrmDgts,0);
end;
var
T1,T0: TDateTime;
MaxChain : tChain;
dgtCount : LongInt;
pr,lmt :nativeInt;
Begin
T0 := now;
InitAndGetPrimes;
T1 := now;
Writeln('time for sieving ',FormatDateTime('NN:SS.ZZZ',T1-T0));
dgtCount := 2;
lmt := 99;
pr := 10;
repeat
write(dgtCount:2);
maxDgt := dgtCount-1;
MaxChain.Chainlength := 0;
gblpermCount := 0;
repeat
while (pr<lmt) AND Not primeSieve[pr] do
inc(pr);
if pr >lmt then
BREAK;
CheckChain(pr,dgtCount);
If gblTestChain.chainLength > MaxChain.chainLength then
MaxChain := gblTestChain;
inc(pr);
until pr>lmt;
with MaxChain do
writeln(StartNUm:12,EndNum:12,ChainLength:8);
inc(dgtCount);
lmt := lmt*10+9;
until lmt>LIMIT;
end.</syntaxhighlight>
{{out|@TIO.RUN}}
<pre>
time for sieving 00:00.318
2 13 31 2
3 149 941 4
4 1237 7321 11
5 13789 91387 39
6 123479 917243 148
7 1235789 9127583 731
8 12345769 91274563 4333
Real time: 4.228 s User time: 4.116 s Sys. time: 0.081 s CPU share: 99.26 %
//before Real time: 16.973 s
@home
time for sieving 00:17.377
....
9 102345697 901263457 26519
10 1123465789 9811325467 152526
real 4m19.653s user 4m17.515s sys 0m2.134s</pre>
=={{header|Perl}}==
{{libheader|ntheory}}
<syntaxhighlight lang="perl" line>use v5.36;
use ntheory 'primes';
use List::Util 'max';
use Lingua::EN::Numbers qw(num2en);
for my $l (3..9) {
my %p;
$p{ join '', sort split //, "$_" } .= "$_ " for @{ primes 10**($l-1), 10**$l };
my $m = max map { length $p{$_} } keys %p;
printf "Largest group of anaprimes before %s: %d members.\n", num2en(10**$l), $m/($l+1);
for my $k (sort grep { $m == length $p{$_} } keys %p) {
printf "First: %d Last: %d\n", $p{$k} =~ /^(\d+).* (\d+) $/;
}
say '';
}</syntaxhighlight>
{{out}}
<pre>Largest group of anaprimes before one thousand: 4 members.
First: 149 Last: 941
First: 179 Last: 971
First: 379 Last: 937
Largest group of anaprimes before ten thousand: 11 members.
First: 1237 Last: 7321
First: 1279 Last: 9721
Largest group of anaprimes before one hundred thousand: 39 members.
First: 13789 Last: 98731
Largest group of anaprimes before one million: 148 members.
First: 123479 Last: 974213
Largest group of anaprimes before ten million: 731 members.
First: 1235789 Last: 9875321
Largest group of anaprimes before one hundred million: 4333 members.
First: 12345769 Last: 97654321
Largest group of anaprimes before one billion: 26519 members.
First: 102345697 Last: 976542103</pre>
=={{header|Phix}}==
Line 342 ⟶ 1,068:
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">start</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1e2</span><span style="color: #0000FF;">))+</span><span style="color: #000000;">1</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Largest anagram groups:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">pow10</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"getting_primes...\r"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (~12s in total)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pow10</span><span style="color: #0000FF;">)),</span>
<span style="color: #000000;">anap</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">start</span><span style="color: #0000FF;">..$],</span>
<span style="color: #
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span> <span style="color: #008080;">in</span> <span style="color: #000000;">anap</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- (~2M/s, 30s in total)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"converting %d/%d...\r"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">anap</span><span style="color: #0000FF;">)})</span>
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #
<span style="color: #008080;">while</span> <span style="color: #000000;">a</span> <span style="color: #008080;">do</span>
<span style="color: #
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span> <span style="color: #008080;">then</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">
<span style="color: #008080;">for</span> <span style="color: #000000;">dc</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">*</span><span style="color: #000000;">10</span><span style="color: #0000FF;">+</span><span style="color: #000000;">d</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">anap</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"sorting...\r"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (~
<span style="color: #004080;">sequence</span> <span style="color: #000000;">anasorted</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">anap</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"scanning...\r"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (pretty fast)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">longest</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">maxlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">maxstart</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,
<span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">anasorted</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">maxstart</span> <span style="color: #0000FF;"><=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">anasorted</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #
<span style="color: #
<span style="color: #008080;">while</span> <span style="color: #000000;">maxend</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">l</span> <span style="color: #008080;">and</span> <span style="color: #000000;">anasorted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">maxend</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">am</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">maxend</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">maxlen</span><span style="color: #0000FF;"><</span><span style="color: #000000;">maxend</span><span style="color: #0000FF;">-</span><span style="color: #000000;">maxstart</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">maxlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">maxend</span><span style="color: #0000FF;">-</span><span style="color: #000000;">maxstart</span>
<span style="color: #000000;">longest</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">maxstart</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">maxend</span>
Line 387 ⟶ 1,123:
<pre>
Largest anagram groups:
3-digits: [
4-digits: [
5-digits: [
6-digits: [
7-digits: [
8-digits: [
9-digits: [
</pre>
For comparison, on the same (ten year old 16GB) box the Julia entry took 38s (2nd run) to complete to 9 digits.<br>
I simply don't have enough memory to attempt 10 digits, and in fact trying to run the Julia entry as-is forced a hard reboot.<br>
When transpiled to JavaScript and run in a web browser, 8 digits took
=={{header|Raku}}==
Line 404 ⟶ 1,140:
<syntaxhighlight lang="raku" line>use Lingua::EN::Numbers;
use Math::Primesieve;
use List::Allmax;
my $p = Math::Primesieve.new;
for 3 .. 9 {
my
put "\nLargest group of anaprimes before {cardinal 10 ** $_}: {+
put 'First: ', ' Last: ' Z~
}</syntaxhighlight>
{{out}}
<pre>Largest group of anaprimes before one thousand: 4 members.
First: 149 Last: 941
First: 179 Last: 971
First: 379 Last: 937
Largest group of anaprimes before ten thousand: 11 members.
First: 1237 Last: 7321
First: 1279 Last: 9721
Largest group of anaprimes before one hundred thousand: 39 members.
Line 434 ⟶ 1,174:
Largest group of anaprimes before one billion: 26,519 members.
First: 102345697 Last: 976542103</pre>
=={{header|Ruby}}==
9 digit takes about 4 minutes (not done here). Could use something like Raku's Allmax.
<syntaxhighlight lang="ruby" line>require 'prime'
upto = 100_000_000
h = Hash.new {|hash, key| hash[key] = []}
Prime.each(upto) {|pr| h[pr.digits.sort] << pr }
(3..(upto.digits.size-1)).each do |num_digits|
group = h.select {|k,v| k.size == num_digits}
sizes = group.values.group_by(&:size)
max = sizes.keys.max
maxes = sizes[max]
puts "Anaprime groups of #{num_digits} digits: #{maxes.size} ha#{maxes.size == 1 ? "s" : "ve"} #{max} primes."
maxes.each{|group| puts " First: #{group.first} Last: #{group.last}"}
end
</syntaxhighlight>
{{out}}
<pre>Anaprime groups of 3 digits: 3 have 4 primes.
First: 149 Last: 941
First: 179 Last: 971
First: 379 Last: 937
Anaprime groups of 4 digits: 2 have 11 primes.
First: 1237 Last: 7321
First: 1279 Last: 9721
Anaprime groups of 5 digits: 1 has 39 primes.
First: 13789 Last: 98731
Anaprime groups of 6 digits: 1 has 148 primes.
First: 123479 Last: 974213
Anaprime groups of 7 digits: 1 has 731 primes.
First: 1235789 Last: 9875321
Anaprime groups of 8 digits: 1 has 4333 primes.
First: 12345769 Last: 97654321</pre>
=={{header|Sidef}}==
Up to 8 digits, takes about 30 seconds, using ~800 MB of RAM.
<syntaxhighlight lang="ruby">for k in (3..8) {
var P = primes(10**(k-1), 10**k).group_by{ Str(_).sort }
var G = P.values
var m = G.map{.len}.max
printf("Largest group of anaprimes before %s: %s members.\n", commify(10**k), m)
G.grep { .len == m }.sort.each {|group|
say "First: #{group.head} Last: #{group.tail}"
}
say ""
}</syntaxhighlight>
{{out}}
<pre>
Largest group of anaprimes before 1,000: 4 members.
First: 149 Last: 941
First: 179 Last: 971
First: 379 Last: 937
Largest group of anaprimes before 10,000: 11 members.
First: 1237 Last: 7321
First: 1279 Last: 9721
Largest group of anaprimes before 100,000: 39 members.
First: 13789 Last: 98731
Largest group of anaprimes before 1,000,000: 148 members.
First: 123479 Last: 974213
Largest group of anaprimes before 10,000,000: 731 members.
First: 1235789 Last: 9875321
Largest group of anaprimes before 100,000,000: 4333 members.
First: 12345769 Last: 97654321
</pre>
=={{header|Wren}}==
Line 439 ⟶ 1,249:
{{libheader|Wren-fmt}}
Getting up to 1 billion takes around 2 minutes 25 seconds on my Core i7 machine. I've left it at that.
<syntaxhighlight lang="
import "./fmt" for Fmt
|