Anaprimes
You are encouraged to solve this task according to the task description, using any language you may know.
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.
Anaprimes are very common. To illustrate this, we will investigate the sizes of the equivalence classes defined by the "is an anagram of" relation.
For example, the equivalence class of 149 has four anaprimes: {149, 419, 491, 941}. It turns out that there is no larger equivalence class of 3-digit anaprimes.
- Task
- Find prime numbers that are anagrams of each other.
- Find the largest anagram group of prime numbers and display the count, and minimum and maximum members for prime numbers:
- up to three digits long (before 1,000)
- up to four digits long (before 10,000)
- up to five digits long (before 100,000)
- up to six digits long (before 1,000,000)
- Stretch
- Find the largest anagram group and display the count, and smallest and largest members for prime numbers:
- up to seven digits long (before 10,000,000)
- up to eight digits long (before 100,000,000)
- up to nine digits long (before 1,000,000,000)
- ???!
- Related tasks
ALGOL 68
If running this with Algol 68G, a large heap size must be requested on the command line with, e.g.: -heap 512M for version 2 under Windows. On TIO.RUN, it wanted -heap=512M. 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).
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
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- Output:
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
C++
This takes about 70 seconds on my system. Memory usage is 4G.
#include <array>
#include <iostream>
#include <map>
#include <vector>
#include <primesieve.hpp>
using digit_set = std::array<int, 10>;
digit_set get_digits(uint64_t n) {
digit_set result = {};
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;) {
uint64_t prime = pi.next_prime();
if (prime > limit) {
size_t max_length = 0;
std::vector<map_type::iterator> groups;
for (auto i = anaprimes.begin(); i != anaprimes.end(); ++i) {
if (i->second.size() > max_length) {
groups.clear();
max_length = i->second.size();
}
if (max_length == i->second.size())
groups.push_back(i);
}
std::cout << "Largest group(s) of anaprimes before " << limit
<< ": " << max_length << " members:\n";
for (auto i : groups) {
std::cout << " First: " << i->second.front()
<< " Last: " << i->second.back() << '\n';
}
std::cout << '\n';
anaprimes.clear();
limit *= 10;
}
anaprimes[get_digits(prime)].push_back(prime);
}
}
- Output:
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: 4,333 members: First: 12,345,769 Last: 97,654,321 Largest group(s) of anaprimes before 1,000,000,000: 26,519 members: First: 102,345,697 Last: 976,542,103 Largest group(s) of anaprimes before 10,000,000,000: 152,526 members: First: 1,123,465,789 Last: 9,876,543,211
EasyLang
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 ""
.
- Output:
4 149 941 179 971 379 937 11 1237 7321 1279 9721 39 13789 98731 148 123479 974213
F#
This task uses Extensible Prime Generator (F#)
// 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}")
- Output:
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
FreeBASIC
Const _top As Ulong = 100000000 ' 100M max. Allocation is > (_top * 11)
Dim Shared As Ulong first(_top), last(_top)
Dim Shared As Ushort count(_top)
Dim Shared As Boolean notPrime(_top)
Dim Shared As Ubyte hash(10)
Sub anaprimes()
Dim As Ulong max = 1, a = 3, z = 100, dgts = 2, n, i, v
While z <= _top
For n = a To z Step 2 ' Check only odd numbers
If notPrime(n) Then Continue For ' Skip any non-prime
For i = n * 3 To _top Step n * 2 ' Build sieve of Eratosthenes
notPrime(i) = True ' by marking odd multiples of n as not prime
Next
v = n
While v ' Sort v into ascending digits
hash(v Mod 10) += 1 ' by building hash table of digits
v \= 10
Wend
v = 0
For i = 1 To 10 ' Reassemble hashed digits in ascending order
While hash(i) > 0
v = v * 10 + i
hash(i) -= 1
Wend
Next
count(v) += 1
If count(v) > max Then max = count(v)
If first(v) = 0 Then first(v) = n Else last(v) = n
Next
Print "Largest group(s) of " & dgts & "-digit anaprimes (" & max & " members):"
For i = a To z Step 2
If count(i) = max Then
Print Using !" first: ######## last: ########"; first(i); last(i)
End If
Next
' Clear count array for next group
For i = a To z
count(i) = 0
Next
max = 1 : a = z + 1 : z *= 10 : dgts += 1
Wend
End Sub
Dim As Double t = Timer
anaprimes()
Print Using !"\n Calc time = ##.### seconds."; Timer - t
Sleep
- Output:
Largest group(s) of 2-digit anaprimes (2 members): first: 13 last: 31 first: 17 last: 71 first: 37 last: 73 first: 79 last: 97 Largest group(s) of 3-digit anaprimes (4 members): first: 149 last: 941 first: 179 last: 971 first: 379 last: 937 Largest group(s) of 4-digit anaprimes (11 members): first: 1237 last: 7321 first: 1279 last: 9721 Largest group(s) of 5-digit anaprimes (39 members): first: 13789 last: 98731 Largest group(s) of 6-digit anaprimes (148 members): first: 123479 last: 974213 Largest group(s) of 7-digit anaprimes (731 members): first: 1235789 last: 9875321 Largest group(s) of 8-digit anaprimes (4333 members): first: 12345769 last: 97654321 Calc time = 2.686 seconds.
FutureBasic
This implementation is super fast thanks to its routine for sorting digits.
_top = 100000000 // 100M max. Allocation is > (_top * 11)
uint32 first(_top), last(_top)
uint16 count(_top)
bool notPrime(_top)
byte hash( 10 )
—
void local fn anaprimes
uint32 max = 1, a = 3, z = 100, dgts = 2, n, i, v
while z <= _top
for n = a to z step 2 // Check only odd numbers
if notPrime(n) then continue // Skip any non-prime
for i = n * n to _top step n * 2 // Build sieve of Eratosthenes
notPrime(i) = YES // by marking odd multiples of n as not prime
next
v = n
while v // Sort v into ascending digits
hash(v mod 10)++ // by building hash table of digits
v /= 10
wend
for i = 1 to 10 // Reassemble hashed digits in ascending order
while hash(i)
v = v * 10 + i
hash(i)--
wend
next
count(v)++
if count(v) > max then max = count(v)
if first(v) then last(v) = n else first(v) = n
next
printf @"\n Largest group(s) of %u-digit anaprimes (%u members):",dgts,max
for i = a to z step 2
if count(i) == max then printf @"\t\t first: %u last: %u",first(i),last(i)
next
fn memset( @count(a), 0, @count(z) - @count(a) ) // clear for next group
max = 1 : a = z + 1 : z *= 10 : dgts++
wend
end fn
—
window 1, @"Largest Anaprime Groups", (0,0,425,425)
CFTimeInterval t : t = fn CACurrentMediaTime
fn anaprimes
printf @"\n Calc time = %.3f seconds.", (fn CACurrentMediaTime - t)
handleevents- Output:
Go
Getting up to 10 billion takes around 2 minutes 28 seconds on my Core i7 machine.
package main
import (
"fmt"
"rcu"
"sort"
)
func main() {
const limit = int(1e10)
const maxIndex = 9
primes := rcu.Primes(limit)
anaprimes := make(map[int][]int)
for _, p := range primes {
digs := rcu.Digits(p, 10)
key := 1
for _, dig := range digs {
key *= primes[dig]
}
if _, ok := anaprimes[key]; ok {
anaprimes[key] = append(anaprimes[key], p)
} else {
anaprimes[key] = []int{p}
}
}
largest := make([]int, maxIndex+1)
groups := make([][][]int, maxIndex+1)
for key := range anaprimes {
v := anaprimes[key]
nd := len(rcu.Digits(v[0], 10))
c := len(v)
if c > largest[nd-1] {
largest[nd-1] = c
groups[nd-1] = [][]int{v}
} else if c == largest[nd-1] {
groups[nd-1] = append(groups[nd-1], v)
}
}
j := 1000
for i := 2; i <= maxIndex; i++ {
js := rcu.Commatize(j)
ls := rcu.Commatize(largest[i])
fmt.Printf("Largest group(s) of anaprimes before %s: %s members:\n", js, ls)
sort.Slice(groups[i], func(k, l int) bool {
return groups[i][k][0] < groups[i][l][0]
})
for _, g := range groups[i] {
fmt.Printf(" First: %s Last: %s\n", rcu.Commatize(g[0]), rcu.Commatize(g[len(g)-1]))
}
j *= 10
fmt.Println()
}
}
- Output:
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: 4,333 members: First: 12,345,769 Last: 97,654,321 Largest group(s) of anaprimes before 1,000,000,000: 26,519 members: First: 102,345,697 Last: 976,542,103 Largest group(s) of anaprimes before 10,000,000,000: 152,526 members: First: 1,123,465,789 Last: 9,876,543,211
J
Here, we'll define the "largeness" of a group of primes as its sum.
dgt=: 10&#.inv
dgrp=: </.~ /:~"1&.dgt
pgrp=: {{dgrp p:(+ i.)/(-/)\ p:inv 0 _1+10^_1 0+y}}
big=: \: +/@>
largest=: 0 {:: big
Here, dgt gives use the base 10 digits of a number, dgrp groups numbers which contain the same digits, pgrp groups all primes of a given digit count by their digits, big sorts groups of numbers in descending order by their sum and largest 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:
(#,<./,>./) 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
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:
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
Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public final class Anaprimes {
public static void main(String[] args) {
List<Integer> primes = listPrimeNumbers(1_000_001_000);
Map<List<Integer>, List<Integer>> anaprimes = new HashMap<List<Integer>, List<Integer>>();
int index = 0;
int limit = 1_000;
while ( limit <= 1_000_000_000 ) {
final int prime = primes.get(index++);
if ( prime > limit ) {
int maxLength = 0;
List<List<Integer>> groups = new ArrayList<List<Integer>>();
for ( List<Integer> value : anaprimes.values() ) {
if ( value.size() > maxLength ) {
groups.clear();
maxLength = value.size();
}
if ( value.size() == maxLength ) {
groups.addLast(value);
}
}
System.out.println(
"Largest group(s) of anaprimes less than " + limit + " has " + maxLength + " members:");
for ( List<Integer> group : groups ) {
System.out.println(" First: " + group.getFirst() + ", Last: " + group.getLast());
}
System.out.println();
anaprimes.clear();
limit *= 10;
}
anaprimes.computeIfAbsent(digits(prime), v -> new ArrayList<Integer>() ).addLast(prime);
}
}
private static List<Integer> digits(int number) {
List<Integer> result = new ArrayList<Integer>();
while ( number > 0 ) {
result.addLast(number % 10);
number /= 10;
}
Collections.sort(result);
return result;
}
private static List<Integer> listPrimeNumbers(int limit) {
List<Integer> primes = new ArrayList<Integer>();
primes.add(2);
final int halfLimit = ( limit + 1 ) / 2;
boolean[] composite = new boolean[halfLimit];
for ( int i = 1, p = 3; i < halfLimit; p += 2, i++ ) {
if ( ! composite[i] ) {
primes.add(p);
for ( int a = i + p; a < halfLimit; a += p ) {
composite[a] = true;
}
}
}
return primes;
}
}
- Output:
Largest group(s) of anaprimes less than 1000 has 4 members:
First: 179, Last: 971
First: 379, Last: 937
First: 149, Last: 941
Largest group(s) of anaprimes less than 10000 has 11 members:
First: 1279, Last: 9721
First: 1237, Last: 7321
Largest group(s) of anaprimes less than 100000 has 39 members:
First: 13789, Last: 98731
Largest group(s) of anaprimes less than 1000000 has 148 members:
First: 123479, Last: 974213
Largest group(s) of anaprimes less than 10000000 has 731 members:
First: 1235789, Last: 9875321
Largest group(s) of anaprimes less than 100000000 has 4333 members:
First: 12345769, Last: 97654321
Largest group(s) of anaprimes less than 1000000000 has 26519 members:
First: 102345697, Last: 976542103
jq
One point of interest here is the definition of `maximals_by/2` so that [size, min, max] details about all the maximally-sized groups in each category can be displayed.
General utilities
# Input: a positive integer
# Output: an array, $a, of length .+1 such 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; length; $i)) as $j (.; .[$j] = false)
else .
end;
(. + 1) as $n
| (($n|sqrt) / 2) as $s
| [null, null, range(2; $n)]
| reduce (2, 1 + (2 * range(1; $s))) as $i (.; erase($i))
;
# Produce a stream of maximal elements in the stream s.
# To emit both the item and item|f, run: maximal_by( s | [., f]; .[1])
def maximals_by(s; f):
reduce s as $x ({v:null, a:[]};
($x|f) as $y
| if $y == .v then .a += [$x] elif $y > .v then .v = $y | .a = [$x] else . end)
| .a[];
# Input: the size of the sieve
def primes: primeSieve | map(select(.));Anaprimes
# Input: null or a suitable array of primes
# Output: for each maximally sized group: [number, min, max]
def anaprimes($limit):
def stats:
maximals_by(.[]; length)
| [length, min, max];
def groupOf: tostring | explode | sort | implode;
(if . then . else $limit|primes end) as $primes
| reduce $primes[] as $p ({}; .[$p|groupOf] += [$p])
| stats;
def task($digits):
# Avoid recomputing the primes array:
(pow(10;$digits) | primes) as $primes
| range(3; $digits+1) as $i
| pow(10; $i) as $p
| "For \($i) digit numbers:",
($primes | map(select(.<$p)) | anaprimes($p)),
"";
task(7)- Output:
For 3 digit numbers: [4,149,941] [4,179,971] [4,379,937] For 4 digit numbers: [11,1237,7321] [11,1279,9721] For 5 digit numbers: [39,13789,98731] For 6 digit numbers: [148,123479,974213] For 7 digit numbers: [731,1235789,9875321]
Julia
Takes a bit over 1.5 minutes on a 10-year-old Haswell i7 machine.
""" rosettacode.org task Anaprimes """
using Primes
@time for pow10 = 2:9
parr = primes(10^pow10, 10^(pow10 + 1))
anap = map(n -> evalpoly(10, sort!(digits(n))), parr)
anasorted = sort(anap)
longest, maxlen, maxstart, maxend = 0, 1, 1, 1
while maxstart < length(anasorted)
maxend = searchsortedfirst(anasorted, anasorted[maxstart] + 1)
if maxlen <= maxend - maxstart
maxlen = maxend - maxstart
longest = anasorted[maxend - 1]
end
maxstart = maxend
end
println(
"For $(pow10 + 1)-digit primes, a largest anagram group, [",
parr[findfirst(==(longest), anap)],
", ..",
parr[findlast(==(longest), anap)],
"], has a group size of $maxlen.",
)
end
- Output:
For 3-digit primes, a largest anagram group, [379, ..937], has a group size of 4. For 4-digit primes, a largest anagram group, [1279, ..9721], has a group size of 11. For 5-digit primes, a largest anagram group, [13789, ..98731], has a group size of 39. For 6-digit primes, a largest anagram group, [123479, ..974213], has a group size of 148. For 7-digit primes, a largest anagram group, [1235789, ..9875321], has a group size of 731. For 8-digit primes, a largest anagram group, [12345769, ..97654321], has a group size of 4333. For 9-digit primes, a largest anagram group, [102345697, ..976542103], has a group size of 26519. For 10-digit primes, a largest anagram group, [1123465789, ..9876543211], has a group size of 152526. 186.920326 seconds (455.94 M allocations: 72.961 GiB, 1.54% gc time, 0.02% compilation time)
Mathematica / Wolfram Language
ClearAll[nDigitPrimes, anaprimes, output, maximalEquivalenceClasses];
nDigitPrimes[n_Integer?Positive] := Prime@Range[PrimePi[10^(n - 1) + 1], PrimePi[10^n]];
anaprimes[n_Integer?Positive] := GatherBy[nDigitPrimes[n], Sort[IntegerDigits[#]] &];
SetAttributes[anaprimes, Listable];
(*Produce output*)
maximalEquivalenceClasses = MaximalBy[Length] /@ anaprimes[Range[9]];
output[n_Integer?Positive] :=
Module[{class = maximalEquivalenceClasses[[n]]},
Print["Largest group(s) of ", n, "-digit anaprimes (", Length[First@class], " members):"];
Print["First: ", First[class], " Last: ", Last[class]];
Print[];
];
Map[output, Range[3, 9]];
- Output:
Largest group of 3-digit anaprimes (4 members): First: 149 Last: 941 First: 179 Last: 971 First: 379 Last: 937 Largest group of 4-digit anaprimes (11 members): First: 1237 Last: 7321 First: 1279 Last: 9721 Largest group of 5-digit anaprimes (39 members): First: 13789 Last: 98731 Largest group of 6-digit anaprimes (148 members): First: 123479 Last: 974213 Largest group of 7-digit anaprimes (731 members): First: 1235789 Last: 9875321 Largest group of 8-digit anaprimes (4333 members): First: 12345769 Last: 97654321 Largest group of 9-digit anaprimes (26519 members): First: 102345697 Last: 976542103
Nim
Run in 14 seconds on an Intel Core i5-8250U (four cores at 1.60GHz).
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()
- Output:
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
Pascal
Free Pascal
Not as fast as other versions, with runtime of 260s for 10 digits. ( Ryzen 5600G, 16 GB, 4.4 Ghz )
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.
- @TIO.RUN:
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
Perl
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 '';
}
- Output:
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
Phix
with javascript_semantics atom t0 = time(), t1 = time()+1 integer start = length(get_primes_le(1e2))+1 printf(1,"Largest anagram groups:\n") for pow10=3 to iff(platform()=JS?7:9) do atom t2 = time() progress("getting_primes...\r") -- (~12s in total) sequence primes = get_primes_le(power(10,pow10)), anap = primes[start..$], digits = repeat(0,9) for i,a in anap do -- (~2M/s, 30s in total) if time()>t1 then progress("converting %d/%d...\r",{i,length(anap)}) t1 = time()+1 end if -- convert eg 791 to 179: while a do integer r = remainder(a,10) if r then digits[r] += 1 end if a = floor(a/10) end while for d=1 to length(digits) do for dc=1 to digits[d] do a = a*10+d end for digits[d] = 0 end for anap[i] = a end for progress("sorting...\r") -- (~45s in total) sequence anasorted = sort(deep_copy(anap)) progress("scanning...\r") -- (pretty fast) integer longest=0, maxlen = 1, maxstart = 1, l = length(anasorted) while maxstart <= length(anasorted) do atom am = anasorted[maxstart] integer maxend = maxstart+1 while maxend<=l and anasorted[maxend]=am do maxend += 1 end while if maxlen<maxend-maxstart then maxlen = maxend-maxstart longest = am end if maxstart = maxend end while progress("") integer lodx = find(longest,anap)+start-1, hidx = rfind(longest,anap)+start-1 string e = elapsed_short(time()-t0) printf(1,"%d-digits: [%d..%d], size %d (%s)\n",{pow10,primes[lodx],primes[hidx],maxlen,e}) start = length(primes)+1 end for
- Output:
Largest anagram groups: 3-digits: [149..941], size 4 (0s) 4-digits: [1237..7321], size 11 (0s) 5-digits: [13789..98731], size 39 (0s) 6-digits: [123479..974213], size 148 (0s) 7-digits: [1235789..9875321], size 731 (0s) 8-digits: [12345769..97654321], size 4333 (8s) 9-digits: [102345697..976542103], size 26519 (1:26)
For comparison, on the same (ten year old 16GB) box the Julia entry took 38s (2nd run) to complete to 9 digits.
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.
When transpiled to JavaScript and run in a web browser, 8 digits took 39s, so I capped it at 7 (3s).
Python
# def sieve(limit):
# """Generate list of primes up to the given limit using the Sieve of Eratosthenes."""
# sieve = [True] * (limit + 1)
# sieve[0:2] = [False, False] # 0 and 1 are not primes
# for num in range(2, int(limit**0.5) + 1):
# if sieve[num]:
# sieve[num*num : limit+1 : num] = [False] * len(range(num*num, limit+1, num))
# primes = [num for num, is_prime in enumerate(sieve) if is_prime]
# return primes
def sieve(limit):
"""Generate list of primes up to the given limit using the Sieve of Atkin."""
# Handle edge cases
if limit < 2:
return []
# Initialize the sieve with False
sieve = [False] * (limit + 1)
# Mark sieve[2] and sieve[3] as True (primes)
if limit >= 2:
sieve[2] = True
if limit >= 3:
sieve[3] = True
# Main loop to mark numbers based on Atkin's rules
for x in range(1, int(limit ** 0.5) + 1):
for y in range(1, int(limit ** 0.5) + 1):
# First condition: (4x² + y²) % 12 == 1 or 5
n = 4 * x ** 2 + y ** 2
if n <= limit and (n % 12 == 1 or n % 12 == 5):
sieve[n] = not sieve[n]
# Second condition: (3x² + y²) % 12 == 7
n = 3 * x ** 2 + y ** 2
if n <= limit and n % 12 == 7:
sieve[n] = not sieve[n]
# Third condition: (3x² - y²) % 12 == 11 (only if x > y)
n = 3 * x ** 2 - y ** 2
if x > y and n <= limit and n % 12 == 11:
sieve[n] = not sieve[n]
# Eliminate all squares of primes
for i in range(5, int(limit ** 0.5) + 1):
if sieve[i]:
for k in range(i ** 2, limit + 1, i ** 2):
sieve[k] = False
# Collect all primes
primes = [i for i in range(limit + 1) if sieve[i]]
return primes
def group_anagrams(primes):
"""Group primes by their sorted digits."""
anagram_groups = {}
for prime in primes:
sorted_digits = ''.join(sorted(str(prime)))
if sorted_digits in anagram_groups:
anagram_groups[sorted_digits].append(prime)
else:
anagram_groups[sorted_digits] = [prime]
return anagram_groups
def find_largest_group(anagram_groups):
"""Find the largest group of anagram primes."""
largest_group = max(anagram_groups.values(), key=lambda x: len(x))
return largest_group
def get_group_info(group):
"""Get count, smallest, and largest primes from a group."""
count = len(group)
min_prime = min(group)
max_prime = max(group)
return count, min_prime, max_prime
def main():
"""Main function to process different ranges and display results."""
limits = [10**3, 10**4, 10**5, 10**6, 10**7, 10**8, 10**9]
for limit in limits:
primes = sieve(limit)
anagram_groups = group_anagrams(primes)
largest_group = find_largest_group(anagram_groups)
count, min_prime, max_prime = get_group_info(largest_group)
print(f"Up to {limit}: Count={count}, Min={min_prime}, Max={max_prime}")
if __name__ == "__main__":
main()
- Output:
Up to 1000: Count=4, Min=149, Max=941 Up to 10000: Count=11, Min=1237, Max=7321 Up to 100000: Count=39, Min=13789, Max=98731 Up to 1000000: Count=148, Min=123479, Max=974213 Up to 10000000: Count=731, Min=1235789, Max=9875321 Up to 100000000: Count=4333, Min=12345769, Max=97654321 Up to 1000000000: Count=26519, Min=102345697, Max=976542103
Raku
9 digit is slooow. I didn't have the patience for 10.
use Lingua::EN::Numbers;
use Math::Primesieve;
use List::Allmax;
my $p = Math::Primesieve.new;
for 3 .. 9 {
my @largest = $p.primes(10**($_-1), 10**$_).classify(*.comb.sort.join).List.&all-max(:by(+*.value)).values;
put "\nLargest group of anaprimes before {cardinal 10 ** $_}: {+@largest[0].value} members.";
put 'First: ', ' Last: ' Z~ .value[0, *-1] for sort @largest;
}
- Output:
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: 4,333 members. First: 12345769 Last: 97654321 Largest group of anaprimes before one billion: 26,519 members. First: 102345697 Last: 976542103
Ruby
9 digit takes about 4 minutes (not done here). Could use something like Raku's Allmax.
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
- Output:
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
Sidef
Up to 8 digits, takes about 30 seconds, using ~800 MB of RAM.
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 ""
}
- Output:
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
Wren
Getting up to 1 billion takes around 2 minutes 25 seconds on my Core i7 machine. I've left it at that.
import "./math" for Int
import "./fmt" for Fmt
var limit = 1e9
var maxIndex = 8
var primes = Int.primeSieve(limit)
var anaprimes = {}
for (p in primes) {
var digs = Int.digits(p)
var key = 1
for (dig in digs) key = key * primes[dig]
if (anaprimes.containsKey(key)) {
anaprimes[key].add(p)
} else {
anaprimes[key] = [p]
}
}
var largest = List.filled(maxIndex + 1, 0)
var groups = List.filled(maxIndex + 1, null)
for (key in anaprimes.keys) {
var v = anaprimes[key]
var nd = Int.digits(v[0]).count
var c = v.count
if (c > largest[nd-1]) {
largest[nd-1] = c
groups[nd-1] = [v]
} else if (c == largest[nd-1]) {
groups[nd-1].add(v)
}
}
var j = 1000
for (i in 2..maxIndex) {
Fmt.print("Largest group(s) of anaprimes before $,d: $,d members:", j, largest[i])
groups[i].sort { |a, b| a[0] < b[0] }
for (g in groups[i]) Fmt.print(" First: $,d Last: $,d", g[0], g[-1])
j = j * 10
System.print()
}
- Output:
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: 4,333 members: First: 12,345,769 Last: 97,654,321 Largest group(s) of anaprimes before 1,000,000,000: 26,519 members: First: 102,345,697 Last: 976,542,103