Anaprimes

Anaprimes 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.

Anaprimes are prime numbers that are anagrams of each other; i.e. they use all of the same digits but in a different order.

Anaprimes are very common. There is an anagram group however, in each order of magnitude greater than two, that contains more members than any other.

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

• Circular primes
• Ormiston pairs

jq

Works with: 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