I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Pandigital Primes

06.27.2013
| 4379 views |
  • submit to reddit

It's Thursday, so it's time for another code puzzler. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Pandigital Primes 

This weeks task is to find the largest pandigital prime. A number is pandigital if it uses all the digits from 1 to n exactly once. An example would be 123 with is a 3 digit pandigital number. 

But here the task is to find the largest n-digits prime that exists. 

Catch up on all our previous puzzlers here

Comments

sun east replied on Thu, 2013/06/27 - 7:20am

Sine all 8 digit and 9 digit pandigital numbers are divisible  by 9, we only to find it from 7654321.

Here it is:

scala> :paste
// Entering paste mode (ctrl-D to finish)

def isprime(n: Int) = 2 to math.sqrt(n).toInt forall (n%_ > 0)

"7654321".permutations map (_.toInt) find isprime get

// Exiting paste mode, now interpreting.

res1: Int = 7652413

Fabien Lamarque replied on Thu, 2013/06/27 - 8:38am in response to: sun east

 I.... I don't get it. Why would 8 and 9 digits pandigital numbers would be divisible by 9?

David Whatever replied on Thu, 2013/06/27 - 12:18pm in response to: Fabien Lamarque

There is a cheat for determining division by 9; if all the sum of the digits are divisible by 9, the number itself will be. 

1..8 summed is 36, 1..9 is 45 - so all numbers composed of those digits would be divisible by 9

Frédéric Vergez replied on Sat, 2013/06/29 - 1:30am

Haskell:


import Data.List
import Data.Char

-- Simple check of prime numbers:
isPrime :: Int -> Bool
isPrime n = not $ any (\x -> (mod n x) == 0) [2..(n-1)]

-- There's surely a simpler solution...
-- Optimized by reverse.sort to simply get the greatest prime
pandigital :: Int -> Maybe Int
pandigital n = find isPrime $ reverse.sort $ map (\x ->i read x:: Int) $ map (map intToDigit) $ permutations [1..n]

Frédéric Vergez replied on Sat, 2013/06/29 - 1:32am in response to: Frédéric Vergez

Replying to myself to give a sample answer (showing there's only pandigital primes for "order" 1, 4 and 7):

map pandigital [1..9]
[Just 1,Nothing,Nothing,Just 4231,Nothing,Nothing,Just 7652413,Nothing,Nothing]

Rafael Naufal replied on Mon, 2013/07/01 - 1:48pm

In Ruby:
require 'mathn'; if n.prime? then a = n.to_s.chars.map(&:to_i); if a.uniq.length == a.length then puts "#{n} is pandigital" end end

Mark Fisher replied on Wed, 2013/07/03 - 9:20am in response to: David Whatever

Excellent observation. It actually extends to "divisible by 3" too (e.g. 123 sum = 6, which divides by 3).

So we can ignore lengths of: 2 (sum 3), 3 (sum 6), 5 (sum 15), 6 (sum 21), 8 (sum 36) and 9 (sum 45), leaving only lengths 4 and 7 as shown in the results by Frédéric Vergez. (1 is not a prime number, see http://primes.utm.edu/notes/faq/one.html)

John Schudy replied on Wed, 2013/07/03 - 2:34pm in response to: David Whatever

By the same token, 2, 3, 5, 6 won't have pandigital primes either.  (The same rule works for testing divisibility by 3.)
Sorry, I didn't see the other post.

Bob Beechey replied on Thu, 2013/07/04 - 10:20am

A Python readable version:

 

from itertools import permutations
from pyprimes import isprime
for p in permutations(list(str(7654321))):
    num = int(''.join(p))
    if isprime(num):
        print(num)
        break


 

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.