//-------------------------------------------------------------------
// enigma1343.c (c) 2005 by Charles Petzold (www.charlespetzold.com)
//
// "Digital Dividend", New Scientist, 4 June 2005, page 28.
//
// Find the largest number whose digits are all different (and non-zero)
// and which is divisible by each of its digits.
//
// This problem practically cries out for a brute-force approach.
// You basically start with the largest number whose digits are all
// different and non-zero, test it, and decrement. Lather, rinse,
// repeat.
//
// The largest number whose digits are all different and non-zero
// is 987,654,321. However, this number is obviously not divisible by
// all its digits. It's not divisible by 2, for example.
//
// MOREOVER -- and this is the important revelation that dramatically
// cuts the job down in size -- any number that is divisible by both 2
// and 5 is also divisible by 10, which means that the least-significant
// digit is 0. Therefore, the solution cannot contain both 2 and 5,
// which means that it cannot be a 9-digit number.
//
// Also, if the number does contain a 5, then 5 must be the
// least-significant digit.
//
// So, let's instead start with the largest 8-digit number whose digits
// are all different and non-zero, and see if the program finishes in a
// reasonable amount of time. (It takes less than a minute.)
//-------------------------------------------------------------------
#include
int main(void)
{
int Number, i, Test, Digits[10], Digit;
for (Number = 98764321; Number > 0; Number--)
{
// Zero out the array used to determine if all the digits
// are unique.
for (i = 0; i < 10; i++)
Digits[i] = 0;
// Copy the number into another int for stripping out the
// digits.
Test = Number;
while (Test > 0)
{
// Obtain the least-significant digit. If it's zero,
// we're not interested in the number.
if (0 == (Digit = Test % 10))
break;
// If that digit is already in the array, we're not
// interested either.
if (Digits[Digit] == 1)
break;
// If the number is not divisible by that digit,
// we just don't care.
if (Number % Digit != 0)
break;
// So far, so good. Set that element of the array so
// we know we have that digit and won't duplicate it.
Digits[Digit] = 1;
// Divide the Test integer by ten to have access to
// the next less-significant digit.
Test /= 10;
}
// If the number passed all the tests in the while loop without
// prematurely exiting, we have a winner!
if (Test == 0)
break;
}
printf("%i\n", Number);
return 0;
}