Pandigital prime
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?
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
- 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
Alternative, faster version
The Delphi sample this was based on has been replaced since this was written - it had a bug that is fixed here.
FOR sp FROM 0 TO 1 DO
FOR x FROM IF sp = 1 THEN 7654321 ELSE 76543211 FI BY -2 TO 0 DO
IF x MOD 3 /= 0 THEN
STRING s = whole( x, 0 );
FOR ch FROM sp TO 7 DO IF NOT char in string( REPR ( ch + ABS "0" ), NIL, s ) THEN GOTO nxt FI OD;
INT i := 1;
WHILE i * i < x DO
IF x MOD ( i + 4 ) = 0 THEN GOTO nxt FI; i +:= 4;
IF x MOD ( i + 2 ) = 0 THEN GOTO nxt FI; i +:= 2
OD;
print( ( whole( sp, 0 ), "..7: ", whole( x, 0 ), newline ) ); GOTO done;
nxt: SKIP
FI
OD;
done: SKIP
OD- Output:
0..7: 76540231 1..7: 7652413
Arturo
allowed: @1..7
pandigital?: function [n][
allowed = sort unique digits n
]
largestPossiblePandigital: 7654321
until -> dec 'largestPossiblePandigital [
and? -> pandigital? largestPossiblePandigital
-> prime? largestPossiblePandigital
]
print "The largest pandigital prime is:"
print largestPossiblePandigital
- Output:
The largest pandigital prime is: 7652413
BASIC
BASIC256
#include "isprime.kbs"
digits = 7654321
for z = 1 to 0 step -1
print "The largest"; z; "..7 pandigital prime is ";
start = msec
for n = digits to 0 step -18
cadena$ = string(n)
flag = True
for i = z to 7
if instr(cadena$, string(i)) = 0 then
flag = False
exit for
end if
next i
if flag and isPrime(n) then
print rjust(string(n), 8);". "; (msec - start); " ms"
exit for
end if
next n
digits = digits * 10 - 9
next z
FreeBASIC
#include "isprime.bas"
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
Gambas
Use "isprime.bas"
Public Sub Main()
Dim digits As Integer = 7654321
For z As Integer = 1 To 0 Step -1
Print "The largest "; z; "..7 pandigital prime is ";
For n As Integer = digits To 0 Step -18
Dim cadena As String = Str(n)
Dim flag As Boolean = True
For i As Integer = z To 7
If InStr(cadena, Str(i)) = 0 Then
flag = False
Break
End If
Next
If flag And isPrime(n) Then
Print Format$(Str$(n), "########"); ". "; Timer; " ms "
Break
End If
Next
digits = digits * 10 - 9
Next
End
PureBasic
;XIncludeFile "isprime.pb"
OpenConsole()
digits.i = 7654321
For z.i = 1 To 0 Step -1
Print("The largest" + Str(z) + "..7 pandigital prime is ")
For n.i = digits To 0 Step -18
cadena.s = Str(n)
flag.b = #True
For i.i = z To 7
If FindString(cadena, Str(i)) = 0:
flag = #False
Break
EndIf
Next i
If flag And isPrime(n):
;Print ""; n; " "; (ElapsedMilliseconds() - start) * 10000; " ms"
PrintN(Str(n) + ". ")
Break
EndIf
Next n
digits = digits * 10 - 9
Next z
PrintN(#CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
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
The original version generated results that weren't prime. This version has been rewritten to fix the prime problem and make it more modular.
{This code is normally put in a separate library, but it is included here for clarity}
function IsPrime(N: int64): boolean;
{Fast, optimised prime test}
var I,Stop: int64;
begin
if (N = 2) or (N=3) then Result:=true
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false
else
begin
I:=5;
Stop:=Trunc(sqrt(N+0.0));
Result:=False;
while I<=Stop do
begin
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit;
Inc(I,6);
end;
Result:=True;
end;
end;
function HighestPandigitalPrime(ZeroBased: boolean): integer;
{Returns the highest pandigital prime}
{ZeroBased = includes 0..N versus 1..N }
var I: integer;
type TDigitFlagArray = array [0..9] of integer;
procedure GetDigitCounts(N: integer; var FA: TDigitFlagArray);
{Get a count of all the digits in the number}
var T,I,DC: integer;
begin
DC:=Trunc(Log10(N))+1;
{Zero counts}
for I:=0 to High(FA) do FA[I]:=0;
{Count each time a digits is used}
for I:=0 to DC-1 do
begin
T:=N mod 10;
N:=N div 10;
Inc(FA[T]);
end;
end;
function IsPandigital(N: integer): boolean;
{Checks to see if all digits 0..N or 1..N are included}
var IA: TDigitFlagArray;
var I,DC: integer;
var Start: integer;
begin
Result:=False;
{ZeroBased includes zero}
if ZeroBased then Start:=0 else Start:=1;
{Get count of digits}
DC:=Trunc(Log10(N))+1;
{Get a count of each digits that are used}
GetDigitCounts(N,IA);
{Each digit 0..N or 1..N can only be used once}
for I:=Start to DC-1 do
if IA[I]<>1 then exit;
Result:=True;
end;
begin
if ZeroBased then Result:=76543210+1 else Result:=7654321;
{Check all numbers in the range}
while Result>2 do
begin
{Check that number is prime and Pandigital}
if IsPrime(Result) then
if IsPandigital(Result) then break;
Dec(Result,2);
end;
end;
procedure PandigitalPrime(Memo: TMemo);
var P: integer;
begin
P:=HighestPandigitalPrime(False);
Memo.Lines.Add(Format('Non Zero Based: %11.0n',[P+0.0]));
P:=HighestPandigitalPrime(True);
Memo.Lines.Add(Format('Zero Based: %11.0n',[P+0.0]));
end;
- Output:
Non Zero Based: 7,652,413 Zero Based: 76,540,231 Elapsed Time: 6.044 ms.
EasyLang
fastfunc isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
proc nextperm . a[] .
n = len a[]
k = n - 1
while k >= 1 and a[k + 1] > a[k]
k -= 1
.
if k = 0
a[] = [ ]
return
.
l = n
while a[l] > a[k]
l -= 1
.
swap a[l] a[k]
k += 1
while k < n
swap a[k] a[n]
k += 1
n -= 1
.
.
for ndigs in [ 7 4 ]
digs[] = [ ]
for i = ndigs downto 1
digs[] &= i
.
repeat
n = 0
for d in digs[]
n = n * 10 + d
.
if isprim n = 1
print n
break 2
.
nextperm digs[]
until len digs[] = 0
.
.
- Output:
7652413
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
- Output:
The largest pandigital decimal prime is: 7652413
Go
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
J
gpdp=. >./@({:@(#~ 1&p:)@(10&#.@A.~ i.@!@#)\)
gpdp >: i. 7
7652413
gpdp i. 8
76540231
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
MATLAB
including zero
primeNumbers = sum(perms(0:7).*repmat((10*ones(1,8)).^(8-1:-1:0), [factorial(8),1]),'c')
mprintf('The largest pandigital prime is %u.', max(primeNumbers(find(members(primeNumbers, primes(7.7e7))==1))))
without zero
primeNumbers = sum(perms(1:7).*repmat((10*ones(1,7)).^(7-1:-1:0), [factorial(7),1]),'c')
mprintf('The largest pandigital prime is %u', max(primeNumbers(find(members(primeNumbers, primes(7.7e6))==1))))
Pascal
Free Pascal
nearly
program PandigitalPrime;
uses
SysUtils;
type
tDigits = set of 0..7;
const
cPanDigits : array['0'..'1'] of string=('76543210','7654321');
cDigits : array['0'..'1'] of tDigits =([0..7],[1..7]);
var
s : String;
x,i,l : NativeInt;
check,myCheck : tDigits;
sp : char;
begin
for sp := '0' to '1' do
Begin
myCheck := cDigits[sp];
val(cPanDigits[sp],x,i);
l := length(cPanDigits[sp]);
//only odd numbers
IF Not(Odd(x)) then
dec(x);
inc(x,2);
repeat
dec(x,2);
//early checking
if x mod 3 = 0 then
continue;
str(x,s);
if length(s)<l then
BREAK;
//check pandigital
check := myCheck;
For i := 1 to l do
Exclude(check,Ord(s[i])-Ord('0'));
if check <> [] then
continue;
//rest of prime check
i := 5;
repeat
if x mod i = 0 then BREAK;
Inc(i, 2);
if x mod i = 0 then BREAK;
Inc(i, 4);
until i * i >= x;
if i*i> x then
Begin
Writeln(Format('%s..7: %d', [sp, x]));
Break;
end;
until x <= 2;
end;
end.
- @TIO.RUN:
0..7: 76540231 1..7: 7652413
Perl
#!/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
Quackery
As per the Factor solution, only 4 and 7 digit pandigital numbers can be prime. We start with the largest 7 digit pandigital number and work down until we find one that is prime. (If there had been no 7 digit pandigital primes, I would then have added code for a 4 digit solution.) As nextperm generates permutations in lexicographical order the word ->revnum subtracts each digit from 8 to give reverse numerical order.
nextperm is defined at Permutations with some identical elements#Quackery.
isprime is defined at Primality by trial division#Quackery.
[ 0 swap
witheach
[ 8 swap -
swap 10 * + ] ] is ->revnum ( [ --> n )
' [ [ 1 2 3 4 5 6 7 ]
[ 1 2 3 4 5 6 7 8 ] ]
witheach
[ [ dup ->revnum
isprime not while
nextperm again ]
->revnum
echo cr ]- Output:
7652413 76540231
Raku
say ($_..7).reverse.permutations».join.first: &is-prime for 1,0;
- 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...
RPL
Based on Factor's insights, we only need to check 4- and 7-digit pandigitals from biggest to smallest. Rather than generating permutations, we start from the biggest pandigital number for a given number of digits and go backwards by increment of 18, since:
- the difference between 2 pandigital numbers is a multiple of 9
- the biggest pandigital number for a given number of digits is odd and lower candidate numbers must also be odd
« R→I →STR DUP SIZE → d s
« 0
1 s FOR j
d j DUP SUB STR→ ALOG + NEXT @ count digit occurrences into a unique number
10 / 9 * 1 + LOG FP NOT @ check that the result is a repunit
» » 'ISPAND?' STO
« 0
WHILE OVER REPEAT
10 * OVER + SWAP 1 - SWAP END
NIP 1 CF
DUP XPON ALOG FOR n
IF n ISPRIME? THEN
IF n ISPAND? THEN 1 SF n DUP XPON ALOG 'n' STO
END END
-18 STEP
IF 1 FC? THEN 0 END
» 'PANPRIME' STO
« 7 PANPRIME
IF DUP NOT THEN 4 PANPRIME END
» 'P041' STO
- Output:
1: 7652413
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
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
XPL0
The largest pandigital number not evenly divisible by 3 is 76543210. This is because any number whose digits add to a multiple of 3 is evenly divisible by 3, and 8+7+6+5+4+3+2+1+0 = 36 and adding 9 = 45, both of which are evenly divisible by 3.
func IsPrime(N); \Return 'true' if N is prime
int N, D;
[if N < 2 then return false;
if (N&1) = 0 then return N = 2;
if rem(N/3) = 0 then return N = 3;
D:= 5;
while D*D <= N do
[if rem(N/D) = 0 then return false;
D:= D+2;
if rem(N/D) = 0 then return false;
D:= D+4;
];
return true;
];
func Pandigital(N, Set); \Return 'true' if N is pandigital
int N, Set, Used;
[Used:= 0;
while N do
[N:= N/10;
if Used & 1<<rem(0) then return false;
Used:= Used ! 1<<rem(0);
];
return Used = Set;
];
int Data, Task, N, Set;
[Data:= ["1..7: ", 7654321, %1111_1110, "0..7: ", 76543210-1\odd\, %1111_1111];
for Task:= 0 to 1 do
[Text(0, Data(Task*3+0));
N:= Data(Task*3+1); Set:= Data(Task*3+2);
loop [if IsPrime(N) then
if Pandigital(N, Set) then
[IntOut(0, N); quit];
N:= N-2;
];
CrLf(0);
];
]- Output:
1..7: 7652413 0..7: 76540231