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.