Pandigital prime
Problem 041: Pandigital 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.
What is the largest n-digit pandigital prime that exists?
Solution:
vXXXXXX
$
>7 12p 0>:0\1p::"1"+v
|-g21:+1p0\ <
v p231$<
>32g1gv
>32g2%| vp24<>2g1g1+32gv
>32g:1g`| >0 ^^3p0g23p0<1
^ >032g1pv>42g0g32g0g42g^p
^p23+1g23 < vp230<
v6:-1g26*+ 55<0p26g21< @.<
>2p0g"0"-+62g| $
# >:>302pv >:02g2-:*` !|
$ >!\2% +|%p20+1:g20:<
^`2::< $
^ <
Explanation:
Perhaps you remember from elementary school that numbers with a digit sum divisible by three is also divisible by three (an so not a prime).
So our number can't be 9 digits long (digit sum = 45) nor 8 (digit sum = 36). Our next best try is a 7-digit palindrome.
With the QuickPerm algorithm we generate all the permutations and test them for their primality. This time we don't use a prime sieve, the numbers are just too big and it's faster with a simple naive prime test.
The rest is just implementation. But the resulting code looks imho pretty nice because it really uses the four directions of befunge and often intersects with itself, even though I think that doesn't make it more readable.
| Interpreter steps: | 83 726 |
| Execution time (BefunExec): | 31ms (2.70 MHz) |
| Program size: | 40 x 17 (fully conform befunge-93) |
| Solution: | 7652413 |
| Solved at: | 2014-10-12 |