Old chestnut: divisible by two through 10

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.

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

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

int number[10];
int used[10];
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[0] = 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;
}