Anaprimes
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
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
# return an array, $a, of length .+1 or .+2 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; (1 + length) / i) as $j (.; .[i * $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
""" rosettacode.org task Anagram primes """
using Primes
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.
Raku
9 digit is slooow. I didn't have the patience for 10.
use Lingua::EN::Numbers;
use Math::Primesieve;
my $p = Math::Primesieve.new;
for 3 .. 9 {
my $largest = $p.primes(10**($_-1), 10**$_).classify(*.comb.sort.join).max(+*.value).value;
put "\nLargest group of anaprimes before {cardinal 10 ** $_}: {+$largest} members.";
put 'First: ', ' Last: ' Z~ $largest[0, *-1];
}
- Output:
Largest group of anaprimes before one thousand: 4 members. First: 179 Last: 971 Largest group of anaprimes before ten thousand: 11 members. First: 1237 Last: 7321 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
Wren
Unsurprisingly, getting up to 1 billion is a struggle for the Wren interpreter - 8 minutes 50 seconds on my Core i7 machine. I gave up after that.
import "./math" for Int
import "./sort" for Sort
import "./fmt" for Fmt
var limit = 1e9
var maxIndex = 8
var primes = Int.primeSieve(limit)
var anaprimes = {}
for (p in primes) {
var d = Sort.insertion(Int.digits(p)).join()
if (anaprimes.containsKey(d)) {
anaprimes[d].add(p)
} else {
anaprimes[d] = [p]
}
}
var largest = List.filled(maxIndex + 1, 0)
var groups = List.filled(maxIndex + 1, null)
for (key in anaprimes.keys) {
var nd = key.count
var v = anaprimes[key]
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