# Pandigitals with prime-divisible substrings

Published on 2011-08-09Problem 43 asks for a lot, at least it terms of the sheer number of conditions it imposes on potential answers:

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let

d_{1}be the 1^{st}digit,d_{2}be the 2^{nd}digit, and so on. In this way, we note the following:

*d*_{2}*d*_{3}*d*_{4}= 406 is divisible by 2*d*_{3}*d*_{4}*d*_{5}= 063 is divisible by 3*d*_{4}*d*_{5}*d*_{6}= 635 is divisible by 5*d*_{5}*d*_{6}*d*_{7}= 357 is divisible by 7*d*_{6}*d*_{7}*d*_{8}= 572 is divisible by 11*d*_{7}*d*_{8}*d*_{9}= 728 is divisible by 13*d*_{8}*d*_{9}*d*_{10}= 289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

Quite a few problems I've worked through recently have concerned pandigital numbers — a category I'm not sure has any meaning outside the Project Euler universe — and this has given me a chance to reuse the same piece of code a number of times. My solution to problem 32 involved a rather memory-intensive method for checking if an arbitrary integer is pandigital, and I copied it into a new program, wrote a method to check for the substring divisibility property described in the problem text above, and wrote a simple main method that cycled through all integers between 1023456789 and 9876543211:

public static void main(string[] args) { long sumOfPandigitalsSought = 0; for (long i = 1023456789; i < 9876543211; i++) { if (isPandigital(i) && hasSubstringDivisibility(i)) sumOfPandigitalsSought += i; } }

It looked elegant and readable but took **forever** to run. I tried to optimize the `hasSubstringDivisibility`

method by checking first for the least likely condition, i.e., that the last three digits be divisible by seventeen, but it didn't help. Having learned from my experiments with different sieves of Eratosthenes that using addition and boolean arrays to check for even divisibility is considerably faster than using modulo checks, I decided to pre-compile arrays of all 3-digit numbers divisible by 2, 3, 5, 7, 11, 13, and 17 and use those while assembling pandigitals digit by digit. My code is long and probably could have been more succinctly written using recursion, especially since the substring divisors are not random, but that's one aspect of C# I haven't yet learned. In any case, this code ended up running as fast as anything else I've written for Project Euler, and I think recursion might have slowed it down a little. The key to speeding it up was to put pandigitals together piece by piece, checking each three digit substring along the way for even divisibility by the appropriate prime. That way, large groups of numbers could be eliminated at once rather than one at a time.

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Problem043 { class Program { static void Main(string[] args) { long sumOfPandigitalsSought = 0; bool[] divisibleBy17 = new bool[1000]; for (int i = 17; i < 1000; i += 17) divisibleBy17[i] = true; bool[] divisibleBy13 = new bool[1000]; for (int i = 13; i < 1000; i += 13) divisibleBy13[i] = true; bool[] divisibleBy11 = new bool[1000]; for (int i = 11; i < 1000; i += 11) divisibleBy11[i] = true; bool[] divisibleBy7 = new bool[1000]; for (int i = 7; i < 1000; i += 7) divisibleBy7[i] = true; bool[] divisibleBy5 = new bool[10]; for (int i = 0; i < 10; i += 5) divisibleBy5[i] = true; bool[] divisibleBy3 = new bool[1000]; for (int i = 3; i < 1000; i += 3) divisibleBy3[i] = true; bool[] divisibleBy2 = new bool[10]; for (int i = 0; i < 10; i += 2) divisibleBy2[i] = true; for (int firstDigit = 0; firstDigit < 10; firstDigit++) { for (int secondDigit = 0; secondDigit < 10; secondDigit++) { if (secondDigit == firstDigit) continue; for (int thirdDigit = 0; thirdDigit < 10; thirdDigit++) { if (thirdDigit == secondDigit || thirdDigit == firstDigit) continue; for (int fourthDigit = 0; fourthDigit < 10; fourthDigit++) { if (fourthDigit == thirdDigit || fourthDigit == secondDigit || fourthDigit == firstDigit || !divisibleBy2[fourthDigit]) continue; for (int fifthDigit = 0; fifthDigit < 10; fifthDigit++) { if (fifthDigit == fourthDigit || fifthDigit == thirdDigit || fifthDigit == secondDigit || fifthDigit == firstDigit || !divisibleBy3[thirdDigit * 100 + fourthDigit * 10 + fifthDigit]) continue; for (int sixthDigit = 0; sixthDigit < 10; sixthDigit++) { if (sixthDigit == fifthDigit || sixthDigit == fourthDigit || sixthDigit == thirdDigit || sixthDigit == secondDigit || sixthDigit == firstDigit || !divisibleBy5[sixthDigit]) continue; for (int seventhDigit = 0; seventhDigit < 10; seventhDigit++) { if (seventhDigit == sixthDigit || seventhDigit == fifthDigit || seventhDigit == fourthDigit || seventhDigit == thirdDigit || seventhDigit == secondDigit || seventhDigit == firstDigit || !divisibleBy7[fifthDigit * 100 + sixthDigit * 10 + seventhDigit]) continue; for (int eighthDigit = 0; eighthDigit < 10; eighthDigit++) { if (eighthDigit == seventhDigit || eighthDigit == sixthDigit || eighthDigit == fifthDigit || eighthDigit == fourthDigit || eighthDigit == thirdDigit || eighthDigit == secondDigit || eighthDigit == firstDigit || !divisibleBy11[sixthDigit * 100 + seventhDigit * 10 + eighthDigit]) continue; for (int ninthDigit = 0; ninthDigit < 10; ninthDigit++) { if (ninthDigit == eighthDigit || ninthDigit == seventhDigit || ninthDigit == sixthDigit || ninthDigit == fifthDigit || ninthDigit == fourthDigit || ninthDigit == thirdDigit || ninthDigit == secondDigit || ninthDigit == firstDigit || !divisibleBy13[seventhDigit * 100 + eighthDigit * 10 + ninthDigit]) continue; for (int tenthDigit = 0; tenthDigit < 10; tenthDigit++) { if (tenthDigit == ninthDigit || tenthDigit == eighthDigit || tenthDigit == seventhDigit || tenthDigit == sixthDigit || tenthDigit == fifthDigit || tenthDigit == fourthDigit || tenthDigit == thirdDigit || tenthDigit == secondDigit || tenthDigit == firstDigit || !divisibleBy17[eighthDigit * 100 + ninthDigit * 10 + tenthDigit]) continue; long soughtPandigital = (long)firstDigit * 1000000000 + secondDigit * 100000000 + thirdDigit * 10000000 + fourthDigit * 1000000 + fifthDigit * 100000 + sixthDigit * 10000 + seventhDigit * 1000 + eighthDigit * 100 + ninthDigit * 10 + tenthDigit; sumOfPandigitalsSought += soughtPandigital; } } } } } } } } } } Console.WriteLine(sumOfPandigitalsSought); } } }