Pandigital prime
- Task
The following problem is taken from Project Euler.
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
<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 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
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
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