Pandigital prime

Task

The following problem is taken from Project Euler problem 41.

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

Assume that the problem is talking about decimal numbers.

Factor

Works with: Factor version 0.99 2021-06-02

<lang factor>USING: io kernel math math.combinatorics math.functions math.primes math.ranges present sequences sequences.cords ;

! If the digit-sum of a number is divisible by 3, so too is the number. ! The digit-sum of all n-digit pandigitals is the same. ! The digit sums for 9-, 8-, 6-, 5-, and 3-digit pandigitals are all divisible by 3. ! 1, 12, and 21 are not prime so 1- and 2-digit pandigitals don't need checked. ! Hence, we only need to check 4- and 7-digit pandigitals from biggest to smallest.

{ 4 7 } [ [1,b] <permutations> ] [ cord-append ] map-reduce [ reverse 0 [ 10^ * + ] reduce-index prime? ] find-last nip "The largest pandigital decimal prime is: " print [ present write ] each nl</lang>

Output:

The largest pandigital decimal prime is: 
7652413

Phix

with javascript_semantics
sequence avail
function pandigital(integer i, n=0)
    if i=0 then ?n return iff(is_prime(n)?n:0) end if
    for d=length(avail) to 1 by -1 do
        if avail[d] then
            avail[d] = false
            integer r = pandigital(i-1,n*10+d)
            if r then return r end if
            avail[d] = true
        end if
    end for
    return 0
end function

for i=9 to 1 by -1 do
    sequence digits = tagset(i)
    if remainder(sum(digits),3)!=0 then
        avail = repeat(true,i)
        printf(1,"Largest decimal pandigital prime:%,d\n",pandigital(i))
        exit
    end if
end for

Output:

As you can see it does not have to generate and test many candidates for primality before it finds the answer.

7654321
7654312
7654231
7654213
7654132
7654123
7653421
7653412
7653241
7653214
7653142
7653124
7652431
7652413
Largest decimal pandigital prime:7,652,413

Raku

<lang perl6>say max (1..9).map: -> $size {

   |(1..$size).permutations».join.grep(&is-prime);

}</lang>

Output:

Ring

<lang ring> load "stdlib.ring" see "working..." + nl see "The largest pandigital prime is:" + nl

pand = 0 limit = 7654321

for n = limit to 2 step -2

   flag = 1
   strn = string(n) 
   if isprime(n)
      for m = 1 to len(strn)
          ind = count(strn,string(m))
          if ind != 1
             flag = 0
          ok
      next
      if flag = 1
         pand = n
         exit
      ok           
   ok

see "done..." + nl

func count(cString,dString)

    sum = 0
    while substr(cString,dString) > 0
          sum++
          cString = substr(cString,substr(cString,dString)+len(string(sum)))
    end
    return sum

</lang>

Output:

The largest pandigital prime is:
7,652,413

Wren

Library: Wren-math

Library: Wren-fmt

This makes use of the optimization in the Factor entry. <lang ecmascript>import "/math" for Int import "/fmt" for Fmt

// generates all permutations in lexicographical order var permutations = Fn.new { |input|

   var perms = [input]
   var a = input.toList
   var n = a.count - 1
   for (c in 1...Int.factorial(n+1)) {
       var i = n - 1
       var j = n
       while (a[i] > a[i+1]) i = i - 1
       while (a[j] < a[i])   j = j - 1
       var t = a[i]
       a[i] = a[j]
       a[j] = t
       j = n
       i = i + 1
       while (i < j) {
           t = a[i]
           a[i] = a[j]
           a[j] = t
           i = i + 1
           j = j - 1
       }
       perms.add(a.toList)
   }
   return perms

}

System.print("The largest pandigital decimal prime which uses all the digits 1..n once is:") for (n in [7, 4]) {

   var perms = permutations.call((1..n).toList)
   for (i in perms.count - 1..0) {
       if (perms[i][-1] % 2 == 0 || perms[i][-1] == 5) continue
       var p = Num.fromString(perms[i].join())
       if (Int.isPrime(p)) {
           Fmt.print("$,d", p)
           return
       }
   }

}</lang>

Output:

The largest pandigital decimal prime which uses all the digits 1..n once is:
7,652,413