# Old chestnut: divisible by two through 10 Jun 10, 2011

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 `int`s 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(?).