Pandigitals with prime-divisible substrings
Published on Tuesday, August 9, 2011Problem 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 1st digit, _d_2 be the 2nd 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);
}
}
}