Pandigital prime: Difference between revisions
(→Using digits 0 to n: Sigh, no need to check 3 digit cases in fact.) |
(added optional use of 0) |
||
| Line 6: | Line 6: | ||
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. |
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. |
||
<br><br> |
<br><br> |
||
What is the largest ''' |
What is the largest '''pandigital prime''' that exists? |
||
<br><br> |
|||
;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. |
|||
<br><br> |
|||
What is the largest '''pandigital0 prime''' that exists? |
|||
<br><br> |
<br><br> |
||
Assume that the problem is talking about '''decimal''' numbers. |
Assume that the problem is talking about '''decimal''' numbers. |
||
Revision as of 12:23, 11 September 2021
- 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. <lang algol68>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 #
# 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 a value := a[ 0 ];
FOR d TO UPB a DO
a value *:= 10 +:= a[ d ]
OD;
p[ p pos ] := a value;
p pos +:= 1
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 #
PROC permute digits = ( REF[]INT a, REF[]INT p )VOID:
BEGIN
INT p pos := 0;
generate( ( UPB a + 1 ) - LWB a, a[ AT 0 ], p[ AT 0 ], 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 n digit pandigital prime, return it if found, 0 otherwise #
PROC try pd prime = ( INT n )INT:
BEGIN
# array of digits to permute for the numbers #
[ 0 : n - 1 ]INT digits; FOR i TO n DO digits[ i - 1 ] := i OD;
# array to hold the permuted digits, there will be n! elements #
INT factorial n := 1;
FOR i FROM 2 TO n DO factorial n *:= i OD;
[ 0 : factorial n - 1 ]INT permuted digits;
# permute the digits #
permute digits( digits, permuted digits );
# sort the permuted numbers, assuming the prime is near the high end #
quicksort( permuted digits, LWB permuted digits, UPB permuted digits );
# try finding a prime - use trial division to test for primality #
INT pd prime := 0;
FOR p pos FROM UPB permuted digits BY -1 TO LWB permuted digits WHILE pd prime = 0 DO
INT p = permuted digits[ p pos ];
IF ODD p AND p MOD 10 /= 5 THEN
BOOL prime := TRUE;
FOR i FROM 3 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
FI
OD;
pd prime
END # try pd prime # ;
# first try a 7 digit number then a 4 digit number if we can't find a 7 digit one #
IF INT pd prime := try pd prime( 7 );
pd prime > 0
THEN
print( ( "max pandigital prime: ", whole( pd prime, 0 ), newline ) )
ELIF pd prime := try pd prime( 4 );
pd prime > 0
THEN
print( ( "max pandigital prime: ", whole( pd prime, 0 ), newline ) )
ELSE
print( ( "Can't find a pandigital prime", newline ) )
FI
END</lang>
- Output:
max pandigital prime: 7652413
C#
<lang csharp>using System;
class Program {
// Find the highest pandigital number in base 10 (without the digit zero)
// Since the sum-of-digits of the pandigital numbers 1..9 and 1..8 are respectively 45 and 36, (both // divisible by 3 and therefore always composite), we will only be looking at pandigital numbers 1..7
static void Main(string[] args) {
var sw = System.Diagnostics.Stopwatch.StartNew();
// The difference between every permutation is a multiple of 9. To check odds only, start at XXXXXX1
// and decrement by 18. It's slightly faster to check pan-digitality before the multi-factor test.
for (int x = 7654321; ; x -= 18) {
// Tests for pan-digitality of x
// Hard-coded to only check for digits 1 through 7. If a duplicate occurs, at least one of the
// other required digits 1..7 will be missing, and therefore rejected.
var s = x.ToString();
for (var ch = '1'; ch < '8'; ch++) if (s.IndexOf(ch) < 0) goto bottom;
// 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 bottom;
if (x % (i += 2) == 0) goto bottom;
}
sw.Stop(); Console.Write("{0} {1} ns", x, sw.Elapsed.TotalMilliseconds * 1000); break;
bottom: ;
}
}
}</lang>
- Output:
@ Tio.run
7652413 29.2 ns
Factor
<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
jq
Works with gojq, the Go implementation of jq
See e.g. Erdős-primes#jq for a suitable implementation of `is_prime`. <lang jq># 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)</lang>
- Output:
7652413
Julia
<lang julia>using Primes
function pandigitals(N)
mask = primesmask(10^N)
ret = Int[]
for j in N:-1:1, i in 10^j:-1:10^(j-1)
if mask[i]
d = digits(i)
if length(d) == j && all(x -> count(y -> y == x, d) == 1, 1:j)
push!(ret, i)
end
end
end
return ret
end
println("The largest prime containing numerals 1 through n of length n is ", maximum(pandigitals(9)))
</lang>
- Output:
The largest prime containing numerals 1 through n of length n is 7652413
Perl
<lang 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;
}</lang>
- Output:
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 constant fmt = "Largest decimal pandigital 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(i) if r then printf(1,fmt,{i,r}) end if 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 (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 4321 4312 4231 Largest decimal pandigital prime with 4 digits:4,231 7654321 7654312 7654231 7654213 7654132 7654123 7653421 7653412 7653241 7653214 7653142 7653124 7652431 7652413 Largest decimal pandigital prime with 7 digits:7,652,413
with 0
(See talk page)
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)
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
<lang perl6>say max (1..9).map: -> $size {
|(1..$size).permutations».join.grep(&is-prime);
}</lang>
- Output:
7652413
REXX
<lang rexx>/*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 -1 for $ /*start with $ and search downwards. */
if verify($, k)>0 then iterate /*$ pandigital? No, skip. _____ */
do d=1; 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? " " " " */
leave j /*We found the largest pandigital num.*/
end
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</lang>
- output when using the internal default input:
the largest prime pandigital number is: 7,654,321
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
next
see "" + pand + nl
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
Using digits 1 to n
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
Using digits 0 to n
Applying the Factor logic for the digits 0..n, we only need to check 8 and 5 digit cases as it can't be any of the others. <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 0..n once is:") for (n in [7, 4]) {
var perms = permutations.call((0..n).toList)
for (i in perms.count - 1..0) {
if (perms[i][0] == "0" || 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 0..n once is: 76,540,231