An old chestnut goes like this:

Arrange the ten digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 such that the first two of them form a number divisible by two, the first three form a number divisible by three, . . . , all ten digits form a number divisible by 10.


The answer is 3816547290.

To find this, write out placeholders for the ten digits and fill in what you know.

The last digit must be zero to get divisibility by 10. #########0

The fifth digit must be 5 or 0 to get divisibility by 5, and 0's gone. ####5####0

The second, fourth, sixth, and eighth digits must be even. Thus all the other unfilled digits are odd. #E#E5E#E#0

Since the third and seventh digits are odd, the fourth and eighth digits must then be 2 and 6 in some order. (Numbers are divisible by four if the last two digits are divisible by 4.) Thus, the second and sixth digits are 4 and 8 in some order. #A#B5A#B#0 where A = 4,8; B=2,6

Likewise, since the sixth number is even, the seventh and eighth digits form a number divisible by 8.

The first three must add to a multiple of three to get divisibility by 3, and likewise so must the next three and the three after that.

The last bit of info in most useful with the second set of three, where we already know the first digit is 2 or 6, the next is 5, and the last is 4 or 8. Out of these combinations, 654 and 258 work. Each of these forces the second and eighth digits to the remaining values. #8#654#2#0 or #4#258#6#0

Now, in the 654 case, the seventh digit must be 3 or 7 to give divisibility by 8, and in the 258 case, the seventh number must by 1 or 9 (or 5, but that's taken).

What numbers can go in the first and third positions? some pair of 1, 3, 7, 9 must go there, such that the first three add up to a number divisible by three, and a valid number must be left for the seventh position.

For 654, we have these starts divisible by three: 183, 189, 381, 387, 783, 789, 981, 987, but we throw out 387 and 783 because the seventh number must be 3 or 7 in this case.

For 258, we have only two possible these starts: 147, 741.

Now for the remaining eight cases, fill in the one or two possible seventh digits and test the number(s) formed by the first seven digits for divisibility by 7.

1836547, 1896543, and 1896547 are not divisible by 7.
3816547 works, so we have the answer 3816547290.
7896543, 9816543, 9816547, and 9876543 are not divisible by 7.
1472589 and 7412589 are not divisible by 7.

We didn't check divisibility by 9 above, but it's automatic after putting the 0 at the end -- the first nine digits must be 1 through 9 once each, which add to 45.

I saw this problem and it begged to be brute-forced with a recursive algorithm.

int RecurseNumber(int *, int *, int *);

int main(int argc, char **argv){

int number⎖];
int used⎖];
int offset;
int i;

for(offset = 0 ; offset < 10 ; offset++){
	used[offset] = 0;	
	}
	
	/* 0 cannot be the first number */
for(i = 1 ; i < 10 ; i++){
	numberΎ] = i;
	used[i] = 1;
	offset = 1;
	if(RecurseNumber(used, number, &offset) == 1)
		break;
	used[i] = 0;	
	}
printf("\nnumber is : ");
for(i = 0 ; i < 10 ; i++)
	printf("%d", number[i]);
printf("\n\n");
return 0;
}




int RecurseNumber(int *used, int *number, int *offset){
int i, j;
double term, val;

if(*offset == 10)
	return 1;  // bottom of recursion

for(i = 0 ; i < 10 ; i++){

		// find an unused digit
	if(used[i] == 1)
		continue;

		// add unused digit to array
	number[*offset] = i;
	used[i] = 1;

	for(j = 0, val = 0 ; j < *offset + 1 ; j++){
		term = number[*offset - j]*(pow(10.0, (double)j));
		val += term;
		}

	if(fmod(val, (double)(*offset + 1)) != 0.0){	
		used[i] = 0;		// reset this digit to unused
		continue;		// go on to next digit
		}
	else{
		(*offset)++;
		if(RecurseNumber(used, number, offset) == 1)
			return 1;
		(*offset)--;
		used[i] = 0;
		continue;
		}
	}
	// no solution for this recursion path was found
return 0;
}

Seeing the brute-force solution above made me want to do a brute-force recursive solution of my own, and as I am trying to learn Prolog, a language well-designed for such tasks, I decided it would be a good choice for the task. The following code was used:

  %Convert from a little-endian(backwards) list of decimal digits to a number
  digitize([],0).
  digitize([A|B],N) :- digitize(B,M), N is 10*M+A.
  
  %Does the list of numbers do what we want?
  pandivisible(_,0).
  pandivisible([A|B],N) :- digitize([A|B],X), X mod N =:= 0, M is N-1, pandivisible(B,M).

  %Find a permutation that does what we want, and convert it into a number.
  chestnut(N) :- permutation([0,1,2,3,4,5,6,7,8,9],L),pandivisible(L,10),digitize(L,N).
This code is much more concise than the evilkalla's C code. To run this in Prolog, I typed the following code into the interpreter(after loading the source file containing the above code):
  ?- chestnut(N).
  N = 3816547290 ;
  false.
The following code shows that 3816547290 is an answer to the problem, the false shows that it is the only answer to the problem. Although it worked perfectly well without bugs(the first time, which is rather surprising), it was rather slow(taking roughly 20 seconds on my machine) due to having to check every permutation rather than being able to rule out large groups of numbers from their initial few digits(most of which will be invalid). For this, instead of using the built-in permutation method, we create an accumulator which collects the first few digits of each permutation and allows us to check them for satisfaction of each part of the requirement as soon as possible.
  pandivisible([],Out,Out,_).
  pandivisible(In,Out,Acc,N) :-
      select(Digit,In,Remaining),
      NewAcc is Acc*10+Digit,
      NewN is N + 1,
      NewAcc mod NewN =:= 0,
      pandivisible(Remaining,Out,NewAcc,NewN).

  chestnut(N) :- pandivisible([0,1,2,3,4,5,6,7,8,9],N,0,0).

This code is roughly as concise, and with a basic understanding of how Prolog does things, can be easily understood; first, the pandivisible code nondeterministically selects a digit of the input array(by splitting it into two arrays of which number two cannot be empty, taking the first element away from the second array, and pasting the two arrays back together, with the selected element removed), appends it to the end of the accumulator in decimal, checks to see if it is divisible by its new length(and if not, it fails and causes the code to backtrack), and then, finally, recursively calls itself at the end of the code with the remaining digits.

This code gives the exact same results as the previous code, but immediately rather than in a relatively long period of time, as the algorithm only has to check a small subset of the permutations; I have not done any rigorous mathematics, but based on the reasonable assumption that roughly 1/k of the k-digit numbers checked by the algorithm are divisible by k, each stage checks a number of numbers roughly equal to a binomial coefficient, and adding these up produces the exponential value 2b, a number that might seem large, but it is small in comparison to the b! that the first algorithm requires.

Tho' it be poor nodeform, shall I be the one to defend C? If I had a nickel for each one of these code nodes I've considered adding to, I'd probably have a dollar. Well, I got absolutely no noding done in May (sorry Cass! I'll get that one finished some day...) so here goes:

#include <stdio.h>

int search(long n, int digits, int count)
{
	int d, m;
	if (count > 8 || n % (10 - count) == 0) {
		for (d = 0, m = 0x200; m; d++, m >>= 1)
			if (m & digits) search(n * 10 + d, ~m & digits, count - 1);
		if (!count) printf("%ld\n", n);
	}
}

int main(int argc, char ** argv)
{
	search(0, 0x3ff, 10);
}

This code was derived from William42's second (more elegant) solution, above. It does the exact same thing as his non-deterministic Prolog magic, but without any fancy tricks like arrays. On a side note, /dev/joe's solution, being analytical, is of course the most elegant one here.

search() uses four ints and a long (because any pandigital above 4293567810 will overflow an unsigned int). n is the string of digits, built up from the left. No divisibility tests are performed if we have fewer than two digits (count > 8). Once we've run out of bits (!count), we know we've passed all the divisibility tests and that n holds the answer (printf(...)).

0x3ff is ten ones in binary. The highest bit represents the digit 'zero', and the next 'one', 'two', and so on to the lowest bit which represents 'nine'. The for loop searches the bits of digits using m as a mask, recursing on digits which have not been used yet (~m & digits is digits with the bit at m unset).

search() is called 4136 times, which is several orders of magnitude below the brute force time of ten factorial (3628800). Python brute force: 15.7 seconds. Python version of this code: .034 seconds. This code: .003 seconds.

If you want to get crazy about memory usage (and who doesn't?), digits and m could be typed as short, and count and d as char. Additionally, count could be eliminated by employing some form of bit counting on digits, as it is always equal to the number of bits set in digits.

For completeness, here's the python version:

def search(n, digits):
    if len(digits) > 8 or n % (10 - len(digits)) == 0:
        for d in digits:
            search(n * 10 + d, [x for x in digits if x != d])
        if not digits: print n

search(0, range(10))

That was a terrible node. I'm going back to poetry(?).

Log in or register to write something here or to contact authors.