# Project Euler #41 - pandigital prime

I've written a solution to Euler 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 n-digit pandigital prime that exists?

But it feels like I could compress the code down instead of having 30 lines of for loops. To briefly explain how it works:

I generate all pandigital numbers through the generate function which features 9 nested for loops which continue if their value is equal to a higher loop or if they would make a number longer than what is required. The generated numbers are then prime checked. This is a bruteforce method.

var time = new Date;
var buffer = [];
var greatest = 0;

function isPrime(number) {
var s = Math.sqrt(number);
for (var b = 2; b <= s; b++) {
if (number % b === 0) {
return false;
}
}
return true;
}

function push(array) {
buffer.push(array.join(''));
}

function generate(length) {
var max = length;
for (var u = 1; u <= max; u++) {
if (max === 1) {
push([u]);
}
for (var i = 1; i <= max; i++) {
if (i === u || max < 2) {
continue;
}
if (max === 2) {
push([u, i]);
}
for (var o = 1; o <= max; o++) {
if (o === i || o === u || max < 3) {
continue;
}
if (max === 3) {
push([u, i, o]);
}
for (var p = 1; p <= max; p++) {
if (p === i || p === o || p === u || max < 4) {
continue;
}
if (max === 4) {
push([u, i, o, p]);
}
for (var a = 1; a <= max; a++) {
if (a === i || a === o || a === p || a === u || max < 5) {
continue;
}
if (max === 5) {
push([u, i, o, p, a]);
}
for (var s = 1; s <= max; s++) {
if (s === a || s === p || s === o || s === i || s === u || max < 6) {
continue;
}
if (max === 6) {
push([u, i, o, p, a, s]);
}
for (var d = 1; d <= max; d++) {
if (d === s || d === a || d === p || d === o || d === i || d === u || max < 7) {
continue;
}
if (max === 7) {
push([u, i, o, p, a, s, d]);
}
for (var f = 1; f <= max; f++) {
if (f === d || f === s || f === a || f === p || f === o || f === i || f === u || max < 8) {
continue;
}
if (max === 8) {
push([u, i, o, p, a, s, d, f]);
}
for (var g = 1; g <= max; g++) {
if (g === f || g === d || g === s || g === a || g === p || g === o || g === i || g === u || max < 9) {
continue;
}
push([u, i, o, p, a, s, d, f, g]);
}
}
}
}
}
}
}
}
}
}

for (var i = 1; i <= 8; i++) {
generate(i);
}

for (var i = buffer.length - 1; i >= 0; i--) {
if (isPrime(buffer[i])) {
greatest = buffer[i];
break;
}
}

var time1 = new Date;
console.log(greatest, 'took:', time1 - time, 'ms');


I think this is a bit over engineered. Let's talk our way through the problem.

• By definition we know the highest pandigital number is 987654321.
• We need to loop through each odd number between 1 and 987654321.
• We need to test each number as a prime. Here's a nice optimised isPrime function from here.

function isPrime(number) {
var start = 2;
while (start <= Math.sqrt(number)) {
if (number % start++ < 1) return false;
}
return number > 1;
}

• If it is prime we need to test each number is pandigital. We should only need to loop once. If we make a set of the digits in a number, then the length of the set will be equal to the total count of digits in the number.

function isPandigital(number) {
var numStr = number.toString(),
digits = [];

for (var digit in numStr) {

if (numStr.hasOwnProperty(digit) && digits.indexOf(digit) === -1)
digits.push(digit);
}

return digits.length === numStr.length;
}

• Then you just need to write the loop:

var pandigitalPrimes = [];

for (var n = 1; n <= 987654321; n+=2) {
if (isPrime(n) && isPandigital(n)) pandigitalPrimes.push(n);
}

• Now it's your job to optimise these ideas so that this process doesn't take absolutely forever.

• Maybe it's a bit under-engineered. :) "Optimise these ideas" means "Use the Sieve of Erastothene" which is a bit different than simply looping over all numbers. – Quentin Pradet Feb 6 '14 at 12:29