Pandigital prime

Pandigital prime 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.

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 pandigital prime that exists?

Optional

Further say that an n+1-digit number is pandigital0 if it makes use of all the digits 0 to n exactly once. For example 10243 is a 5-digit pandigital0 and is also prime.

What is the largest pandigital0 prime that exists?

Assume that the problem is talking about decimal numbers.

ALGOL 68

Uses the observations in the Factor sample - the prime we are looking for can only have 7 or 4 digits.

BEGIN # Find the largest n-digit prime that contains all the digits 1..n #
      # As noted in the Factor sample, only 7 and 4 digit primes need be #
      # considered: 1 is not prime, all 2, 3, 5, 6, 8 and 9 digit        #
      # pandigital numbers are divisible by 3                            #
      # Also find the largest n+1 digit prime that contains all the      #
      # digits 0..n (only 5 and 8 digit numbers need be considered as    #
      # the 0 digit does not affect divisibility by 3)                   #
    # permutation code from the Algol 68 Permutations by swapping task   #
    # entry - uses Heap's algorithm - based on the pseudo code on the    #
    # Wikipedia page for Heap's Algorithm                                #
    # generate permutations of a, the results are stored in p #
    PROC generate = ( INT k, REF[]INT a, REF[]INT p, REF INT p pos )VOID:
         IF k = 1 THEN
            INT last digit = a[ UPB a ];
            IF ODD last digit AND last digit /= 5 THEN
                # the number doesn't end in 2 or 5 so might be prime     #
                INT a value := a[ 0 ];
                FOR d TO UPB a DO
                   a value *:= 10 +:= a[ d ]
                OD;
                p[ p pos +:= 1 ] := a value
             FI
         ELSE
            # Generate permutations with kth unaltered #
            # Initially k = length a #
            generate( k - 1, a, p, p pos );
            # Generate permutations for kth swapped with each k-1 initial #
            FOR i FROM 0 TO k - 2 DO
                # Swap choice dependent on parity of k (even or odd) #
                INT swap item = IF ODD k THEN 0 ELSE i FI;
                INT t           = a[ swap item ];
                a[ swap item ] := a[ k - 1 ];
                a[ k - 1     ] := t;
                generate( k - 1, a, p, p pos )
            OD
         FI # generate # ;
    # generate permutations of a, p is used to hold the output #
    # returns the number of permutations stored #
    PROC permute digits = ( REF[]INT a, REF[]INT p )INT:
         BEGIN
            INT p pos := -1;
            generate( ( UPB a + 1 ) - LWB a, a[ AT 0 ], p[ AT 0 ], p pos );
            p pos
         END # permute digits # ;
    # Quicksorts in-place the array of integers a, from lb to ub #
    PROC quicksort = ( REF[]INT a, INT lb, ub )VOID:
         IF ub > lb THEN
            # more than one element, so must sort #
            INT left   := lb;
            INT right  := ub;
            # choosing the middle element of the array as the pivot #
            INT pivot  := a[ left + ( ( right + 1 ) - left ) OVER 2 ];
            WHILE
                WHILE IF left  <= ub THEN a[ left  ] < pivot ELSE FALSE FI DO left  +:= 1 OD;
                WHILE IF right >= lb THEN a[ right ] > pivot ELSE FALSE FI DO right -:= 1 OD;
                left <= right
            DO
                INT t      := a[ left  ];
                a[ left  ] := a[ right ];
                a[ right ] := t;
                left      +:= 1;
                right     -:= 1
            OD;
            quicksort( a, lb,   right );
            quicksort( a, left, ub    )
         FI # quicksort # ;
    # attenmpt to find the maximum pandigital prime with digits f..n, return it if found, 0 otherwise #
    PROC try pd prime = ( INT f, INT n )INT:
         BEGIN
            # array of digits to permute for the numbers #
            [ f : n ]INT digits; FOR i FROM LWB digits TO UPB digits DO digits[ i ] := i OD;
            # array to hold the permuted digits, there will be ( ( n + 1 ) - f)! elements #
            INT factorial n := 1; FOR i FROM 2 TO ( n + 1 ) - f DO factorial n *:= i OD;
            [ 0 : factorial n - 1 ]INT permuted digits;
            # permute the digits #
            INT p count = permute digits( digits, permuted digits );
            # sort the permuted numbers, assuming the prime is near the high end #
            quicksort( permuted digits, LWB permuted digits, p count );
            # try finding a prime - use trial division to test for primality #
            INT pd prime := 0;
            FOR p pos FROM p count BY -1 TO LWB permuted digits WHILE pd prime = 0 DO
                INT p = permuted digits[ p pos ];
                # we have onlt stored the odd numbers that don't end in 5 #
                # and we know they are not divisible by 3 #
                BOOL prime := TRUE;
                FOR i FROM 7 BY 2 TO ENTIER sqrt(p) WHILE prime := p MOD i /= 0 DO SKIP OD;
                IF prime THEN
                    # found a pandigital prime #
                    pd prime := p
                FI
            OD;
            pd prime
         END # try pd prime # ;
    # trys to find the maximem pandigital/pandigital0 prime #
    PROC find pd prime = ( INT first digit, STRING title )VOID:
         IF   # first try digits up to 7 then up to 4 if we can't find one with pt to 7 #
              INT pd prime := try pd prime( first digit, 7 );
              pd prime > 0
         THEN
            print( ( "max ", title, " prime: ", whole( pd prime, 0 ), newline ) )
         ELIF pd prime := try pd prime( first digit, 4 );
              pd prime > 0
         THEN
            print( ( "max ", title, " prime: ", whole( pd prime, 0 ), newline ) )
         ELSE
            print( ( "Can't find a ", title, " prime", newline ) )
         FI # find pd prime # ;
    # task #
    find pd prime( 1, "pandigital"  );
    find pd prime( 0, "pandigital0" )
END

Output:

max pandigital prime: 7652413
max pandigital0 prime: 76540231

C#

using System;
 
class Program {
  // Find the highest pandigital number in base 10, excluding or including the digit zero.
 
  // Since the sum-of-digits of the pandigital numbers 0..9 and 0..8 are respectively 45 and 36, (both
  // divisible by 3 and therefore always composite), we will only be looking at pandigital numbers 0..7
 
  static void fun(char sp) {
    var sw = System.Diagnostics.Stopwatch.StartNew();
    // The difference between every permutation is a multiple of 9.  To check odds only,
    // start at XXXXXX1 or XXXXXX01 and decrement by 18.
    // It's slightly faster to check pan-digitality before the multi-factor test.
 
    for (int x = sp == '1' ? 7654321 : 76543201; ; x -= 18) {
 
      // Tests for pan-digitality of x
      // Check for digits sp through 7.  If a duplicate occurs, at least one of the
      // other required digits sp..7 will be missing, and therefore rejected.
      var s = x.ToString();
      for (var ch = sp; ch < '8'; ch++) if (s.IndexOf(ch) < 0) goto nxt;
 
      // Multi-factor test
      // There is no check for even numbers since starting on an odd number and stepping by an even number
      if (x % 3 == 0) continue;
      for (int i = 1; i * i < x; ) {
        if (x % (i += 4) == 0) goto nxt;
        if (x % (i += 2) == 0) goto nxt;
      }
      sw.Stop(); Console.WriteLine("{0}..7: {1,10:n0} {2} μs", sp, x, sw.Elapsed.TotalMilliseconds * 1000); break;
      nxt: ;
    }
  }

static void Main(string[] args) {
    fun('1');
    fun('0');
  }
}

Output @ Tio.run:

1..7:  7,652,413 21 μs
0..7: 76,540,231 24.5 μs

Delphi

uses System.SysUtils, System.Classes, System.Math;
label nxt;
begin
  for var sp := '0' to '1' do for var x := IfThen(sp = '1', 7654321, 76543210) downto 0 do
  begin
    var s := x.ToString;
    for var ch := sp to '7' do if not s.Contains(ch) then goto nxt;
    if x mod 3 = 0 then goto nxt;
    var i := 1;
    repeat
      if x mod (i + 4) = 0 then goto nxt; Inc(i, 4);
      if x mod (i + 2) = 0 then goto nxt; Inc(i, 2);
    until i * i >= x;
    Writeln(Format('%s..7: %d', [sp, x])); Break; nxt:;
  end;
end.

Output:

0..7: 76541302
1..7: 7654312

Factor

Works with: Factor version 0.99 2021-06-02

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

Output:

The largest pandigital decimal prime is: 
7652413

FreeBASIC

Translation of: Ring

Function isPrime(Byval n As Integer) As Boolean
    If n Mod 3 = 0 Then Return False
    Dim As Integer i = 5
    While i * i < n
        If n Mod i = 0 Then Return False : End If : i += 2
        If n Mod i = 0 Then Return False : End If : i += 4
    Wend
    Return True
End Function

Dim As Integer digits = 7654321
For z As Integer = 1 To 0 Step -1
    Print "The largest"; z; "..7 pandigital prime is ";
    Dim As Double start = Timer
    For n As Integer = digits To 0 Step -18
        Dim As String cadena = Str(n)
        Dim As Boolean flag = True
        For i As Integer = z To 7
            If Instr(cadena, Str(i)) = 0 Then
                flag = False
                Exit For
            End If
        Next i
        If flag And isPrime(n) Then
            Print Using "########.  ##.## ms"; n; (Timer - start) * 10000
            Exit For
        End If
    Next n
    digits = digits * 10 - 9
Next z
Sleep

Output:

The largest 1..7 pandigital prime is  7652413.   6.32 ms
The largest 0..7 pandigital prime is 76540231.  13.95 ms

Go

Translation of: Wren

Library: Go-rcu

package main

import (
    "fmt"
    "rcu"
)

// only small factorials needed
func factorial(n int) int {
    fact := 1
    for i := 2; i <= n; i++ {
        fact *= i
    }
    return fact
}

// generates all permutations in lexicographical order
func permutations(input []int) [][]int {
    perms := [][]int{input}
    a := make([]int, len(input))
    copy(a, input)
    var n = len(input) - 1
    for c := 1; c < factorial(n+1); c++ {
        i := n - 1
        j := n
        for a[i] > a[i+1] {
            i--
        }
        for a[j] < a[i] {
            j--
        }
        a[i], a[j] = a[j], a[i]
        j = n
        i += 1
        for i < j {
            a[i], a[j] = a[j], a[i]
            i++
            j--
        }
        b := make([]int, len(input))
        copy(b, a)
        perms = append(perms, b)
    }
    return perms
}

func main() {
outer:
    for _, start := range []int{1, 0} {
        fmt.Printf("The largest pandigital decimal prime which uses all the digits %d..n once is:\n", start)
        for _, n := range []int{7, 4} {
            m := n + 1 - start
            list := make([]int, m)
            for i := 0; i < m; i++ {
                list[i] = i + start
            }
            perms := permutations(list)
            for i := len(perms) - 1; i >= 0; i-- {
                le := len(perms[i])
                if perms[i][le-1]%2 == 0 || perms[i][le-1] == 5 || (start == 0 && perms[i][0] == 0) {
                    continue
                }
                p := 0
                pow := 1
                for j := le - 1; j >= 0; j-- {
                    p += perms[i][j] * pow
                    pow *= 10
                }
                if rcu.IsPrime(p) {
                    fmt.Println(rcu.Commatize(p) + "\n")
                    continue outer
                }
            }
        }
    }
}

Output:

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

The largest pandigital decimal prime which uses all the digits 0..n once is:
76,540,231

jq

Works with: jq

Works with gojq, the Go implementation of jq

See e.g. Erdős-primes#jq for a suitable implementation of `is_prime`.

# Output: a stream of strings of pandigital numbers 
# drawing from the digits in the input array,
# in descending numerical order
def candidates:
  . as $use
  | if . == [] then ""
    else .[] as $i
    | ($use - [$i] | candidates) as $j
    | "\($i)\($j)"
    end;

# Output: a stream in descending numerical order
def pandigital_primes:
  range(9; 0; -1)
  | [range(.; 0; -1)]
  | candidates
  | tonumber
  | select(is_prime);

first(pandigital_primes)

Output:

7652413

Julia

using Primes

function pandigitals(firstdig, lastdig)
    mask = primesmask(10^(lastdig - firstdig + 1))
    for j in lastdig:-1:firstdig
        n = j - firstdig + 1
        for i in evalpoly(10, firstdig:j):-1:evalpoly(10, j:-1:firstdig)
            if mask[i]
                d = digits(i)
                if length(d) == n && all(x -> count(y -> y == x, d) == 1, firstdig:j)
                    return i
                end
            end
        end
    end
    return 0
end

for firstdigit in [1, 0]
    println("Max pandigital prime over [$firstdigit, 9] is ", pandigitals(firstdigit, 9))
end

Output:

Max pandigital prime over [1, 9] is 7652413
Max pandigital prime over [0, 9] is 76540231

Perl

Library: ntheory

#!/usr/bin/perl

use strict; # https://rosettacode.org/wiki/Pandigital_prime
use warnings;
use ntheory qw( forperm is_prime );

for my $digits ( reverse 1 .. 9 )
  {
  forperm
    {
    my $n = join '', map $digits - $_, @_;
    is_prime($n) and exit ! print "$n\n";
    } $digits;
  }

Output:

7652413

Slightly different approach for optional portion of task.

use strict;
use warnings;
use ntheory <forperm is_prime vecmax>;

my @p;
for my $c (0..7) {
    forperm {
        my $n = join '', @_;
        push @p, $n if $n !~ /^0/ and is_prime($n);
    } @{[0..$c]};
}
print vecmax(@p) . "\n";

Output:

76540231

Phix

with javascript_semantics
sequence avail
function pandigital(bool bZero, 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(bZero,i-1,n*10+d-bZero)
            if r then return r end if
            avail[d] = true
        end if
    end for
    return 0
end function

constant fmt = "Largest decimal pandigital%s prime with %d digits:%,d\n"
for i=1 to 9 do
    sequence digits = tagset(i)
    if remainder(sum(digits),3)!=0 then
        avail = repeat(true,i)
        integer r = pandigital(false,i)
        if r then printf(1,fmt,{"",i,r}) end if
        avail = repeat(true,i+1)
        r = pandigital(true,i+1)
        if r then printf(1,fmt,{"0",i+1,r}) end if
    end if
end for

Output:

With full inner workings (the second "1" is really "01", a failing pandigital0), obviously removing the "?n" on the fourth line above will reduce the output to just four lines.
As you can see it does not have to generate and test many candidates for primality before it finds the (or no) answer.
You could of course easily change the main loop to go from 9 down to 1 and quit once any answer is found.

1
10
1
4321
4312
4231
Largest decimal pandigital prime with 4 digits:4,231
43210
43201
Largest decimal pandigital0 prime with 5 digits:43,201
7654321
7654312
7654231
7654213
7654132
7654123
7653421
7653412
7653241
7653214
7653142
7653124
7652431
7652413
Largest decimal pandigital prime with 7 digits:7,652,413
76543210
76543201
76543120
76543102
76543021
76543012
76542310
76542301
76542130
76542103
76542031
76542013
76541320
76541302
76541230
76541203
76541032
76541023
76540321
76540312
76540231
Largest decimal pandigital0 prime with 8 digits:76,540,231

Raku

for 1, 0 -> $i {
    say max ($i..7).map: -> $size {
        |($i..$size).permutations».join.grep(&is-prime);
    }
}

Output:

7652413
76540231

REXX

The longest part of the program execution time was the generating of 402 primes.

Essentially, the CPU time was displayed as using 0.00 seconds   (rounded to two fractional decimal digits).

/*REXX program  finds and displays  the  largest  prime pandigital  number.             */
pand = reverse(123456789)                        /*get a big 9-digit pandigital number. */
gp= 0                                            /*indicate that primes not generated.  */
     do j=9  by -1  for 9;  $= right(pand, j)    /*get largest pandigital # of length=J.*/
     if sumDigs($)//3==0  then iterate           /*Is sumDigs($) ÷ by 3?   Then skip it.*/
     if \gp  then do                             /*if not generated primes, then do so. */
                  call genP  iSqrt($)            /*gen primes up to  $  (pandigital #). */
                  end
        do k=$  by -2  for $%2                   /*start with  $  and search downwards. */
        if verify($, k)>0  then iterate          /*$ pandigital? No, skip.       _____  */
           do d=1  for #;  p= @.d                /*divide by all the primes  ≤  √  K    */
           if p*p>k        then iterate k        /*Is prime squared>K?  Then try next K.*/
           if k//p==0      then iterate k        /*Is K ÷ by this prime?  "   "    "  " */
           end
        leave j
        end     /*k*/
     end        /*j*/
say 'the largest prime pandigital number is: '     commas(k)
exit 0                                           /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?;  do jc=length(?)-3  to 1  by -3; ?=insert(',', ?, jc); end;  return ?
sumDigs:procedure;parse arg x 1 s 2;do j=2 for length(x)-1;s=s+substr(x,j,1);end; return s
/*──────────────────────────────────────────────────────────────────────────────────────*/
iSqrt: procedure; parse arg x;  r=0;  q=1;             do while q<=x;  q=q*4;     end
         do while q>1; q= q%4; _= x-r-q; r= r%2; if _>=0  then do; x= _; r= r+q;  end; end
       return r
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13          /*assign low primes; # primes.*/
      !.= 0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1   /*   "   semaphores to   "    */
      parse arg hp;        #= 6;  sq.#= @.# ** 2          /*# primes so far;  P squared.*/
        do j=@.#+4  by 2  to hp;  parse var j '' -1 _;  if _==5  then iterate  /*÷ by 5?*/
        if j// 3==0  then iterate;   if j// 7==0  then iterate    /*÷ by 3?;     ÷ by 7?*/
        if j//11==0  then iterate                                 /*"  " 11?     " " 13?*/
                do k=6  while sq.k<=j            /*divide by some generated odd primes. */
                if j//@.k==0  then iterate j     /*Is J divisible by  P?  Then not prime*/
                end   /*k*/                      /* [↓]  a prime  (J)  has been found.  */
        #= #+1;   @.#= j;   sq.#= j*j;   !.j= 1  /*bump #Ps; P──►@.assign P; P^2; P flag*/
        end     /*j*/;      gp= 1;       return

output   when using the internal default input:

the largest prime pandigital number is:  7,652,413

Ring

? "working..."
hi = 7654321
for z in ['1', '0']
    see "The largest " + z + "..7 pandigital prime is "
    st = clock()
    for n = hi to 0 step -18
        strn = string(n)
        pandig = true
        for i in z:'7'
            if substr(strn, i) = 0
                pandig = 0
                exit
            ok
        next
        if pandig and isprime(n)
            et = clock()
            ? "" + n + " " + (et - st) / clockspersecond() * 1000 + " ms"
            exit
        ok
    next
    hi = hi * 10 - 9
next
put "done..."
 
func isprime(n)
    if n % 3 = 0 return 0 ok
    i = 5
    while i * i < n
        if n % i = 0 return 0 ok i += 2
        if n % i = 0 return 0 ok i += 4
    end
    return 1

Output @ Tio.run:

working...
The largest 1..7 pandigital prime is 7652413 9.84 ms
The largest 0..7 pandigital prime is 76540231 20.30 ms
done...

Ruby

Using the observations from the Factor code:

require "prime"
    
def find_pan(ar) = ar.permutation(ar.size).find{|perm| perm.join.to_i.prime? }.join.to_i
  
digits = [7,6,5,4,3,2,1]
puts find_pan(digits)
digits << 0
puts find_pan(digits)

Output:

7652413
76540231

Sidef

func largest_pandigital_prime(base = 10, a = 1, b = base-1) {

    for n in (b `downto` 1) {

        var digits = @(a..n -> flip)

        if (base == 10) {   # check for divisibility by 3
            digits.sum % 3 == 0 && next
        }

        digits.permutations { |*p|
            var v = p.flip.digits2num(base)
            return v if v.is_prime
        }
    }

    return nil
}

say ("Max pandigital prime over [1, 9] is: ", largest_pandigital_prime(a: 1))
say ("Max pandigital prime over [0, 9] is: ", largest_pandigital_prime(a: 0))

Output:

Max pandigital prime over [1, 9] is: 7652413
Max pandigital prime over [0, 9] is: 76540231

Wren

Library: Wren-perm

Library: Wren-math

Library: Wren-fmt

This makes use of the optimization strategy in the Factor entry to do both the basic and optional tasks.

import "./perm" for Perm
import "./math" for Int
import "./fmt" for Fmt
  
for (start in 1..0) {
    var outer = false
    System.print("The largest pandigital decimal prime which uses all the digits %(start)..n once is:")
    for (n in [7, 4]) {
        var perms = Perm.listLex((start..n).toList)
        for (i in perms.count - 1..0) {
            if (perms[i][-1] % 2 == 0 || perms[i][-1] == 5 || (start == 0 && perms[i][0] == "0")) continue
            var p = Num.fromString(perms[i].join())
            if (Int.isPrime(p)) {
                Fmt.print("$,d\n", p)
                outer = true
                break
            }
        }
        if (outer) break
    }
}

Output:

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

The largest pandigital decimal prime which uses all the digits 0..n once is:
76,540,231