Nine-digit problem

nines.py

#!/usr/bin/env python3

nines = set(range(1, 10))
nines = [ (i, nines - set([ i ])) for i in range(1, 10) ]
print(1, len(nines), [ i for i, _ in nines ])

for k in range(2, 10):
    nines = [ 
        (d * 10 + i, rest - set([ i ])) 
        for d, rest in nines 
        for i in rest if (d * 10 + i) % k == 0 
    ]
    print(k, len(nines), [ i for i, _ in nines ])

nines_with_bitmask.py

#!/usr/bin/env python3

bitmask = lambda n: 1 << (n - 1)
ones  = [ (i, bitmask(i)) for i in range(1, 10) if i != 5 ]
evens = [ (i, bitmask(i)) for i in range(2, 10, 2) if i != 5 ]
accum = ones
print("%d: %d\n\t%s"%(1, len(accum), [ x for x, _ in accum ]))

select = (evens, ones)
for i in range(2, 10):
    if i == 5:
        accum = [ (a * 10 + 5, ba) for a, ba in accum ]
    else:
        accum = [
            (a * 10 + b, ba | bb)
            for a, ba in accum
            for b, bb in select[i & 1]
            if ba & bb == 0 and (a * 10 + b) % i == 0
        ]
    print("%d: %d\n\t%s"%(i, len(accum), [ x for x, _ in accum ]))

output_nines.py

time python3 nines.py
1 9 [1, 2, 3, 4, 5, 6, 7, 8, 9]
2 32 [12, 14, 16, 18, 24, 26, 28, 32, 34, 36, 38, 42, 46, 48, 52, 54, 56, 58, 62, 64, 68, 72, 74, 76, 78, 82, 84, 86, 92, 94, 96, 98]
3 80 [123, 126, 129, 147, 162, 165, 168, 183, 186, 189, 243, 246, 249, 261, 264, 267, 285, 321, 324, 327, 342, 345, 348, 369, 381, 384, 387, 423, 426, 429, 462, 465, 468, 483, 486, 489, 528, 543, 546, 549, 561, 564, 567, 582, 621, 624, 627, 642, 645, 648, 681, 684, 687, 723, 726, 729, 741, 762, 765, 768, 783, 786, 789, 825, 843, 846, 849, 861, 864, 867, 921, 924, 927, 942, 945, 948, 963, 981, 984, 987]
4 88 [1236, 1264, 1268, 1296, 1472, 1476, 1624, 1628, 1652, 1684, 1832, 1836, 1864, 1892, 1896, 2436, 2468, 2496, 2648, 2856, 3216, 3248, 3276, 3428, 3452, 3456, 3692, 3812, 3816, 3872, 3876, 4236, 4268, 4296, 4628, 4652, 4832, 4836, 4892, 4896, 5284, 5432, 5436, 5468, 5492, 5496, 5612, 5648, 5672, 5824, 6248, 6428, 6452, 6812, 6872, 7236, 7264, 7268, 7296, 7412, 7416, 7624, 7628, 7652, 7684, 7832, 7836, 7864, 7892, 7896, 8256, 8432, 8436, 8492, 8496, 8612, 8672, 9216, 9248, 9276, 9428, 9452, 9456, 9632, 9812, 9816, 9872, 9876]
5 68 [12365, 12645, 12685, 12965, 14725, 14765, 16245, 16285, 16845, 18325, 18365, 18645, 18925, 18965, 24365, 24685, 24965, 26485, 32165, 32485, 32765, 34285, 36925, 38125, 38165, 38725, 38765, 42365, 42685, 42965, 46285, 48325, 48365, 48925, 48965, 62485, 64285, 68125, 68725, 72365, 72645, 72685, 72965, 74125, 74165, 76245, 76285, 76845, 78325, 78365, 78645, 78925, 78965, 84325, 84365, 84925, 84965, 86125, 86725, 92165, 92485, 92765, 94285, 96325, 98125, 98165, 98725, 98765]
6 20 [123654, 129654, 147258, 183654, 189654, 321654, 327654, 369258, 381654, 387654, 723654, 729654, 741258, 783654, 789654, 921654, 927654, 963258, 981654, 987654]
7 11 [1296547, 1472583, 3216549, 3692584, 3816547, 7296548, 7296541, 7836542, 7836549, 9216543, 9632581]
8 1 [38165472]
9 1 [381654729]
0.04 real         0.02 user         0.01 sys

output_nines_with_bitmask.txt

time python3 nines_with_bitmask.py
1: 8
	[1, 2, 3, 4, 6, 7, 8, 9]
2: 28
	[12, 14, 16, 18, 24, 26, 28, 32, 34, 36, 38, 42, 46, 48, 62, 64, 68, 72, 74, 76, 78, 82, 84, 86, 92, 94, 96, 98]
3: 64
	[123, 126, 129, 147, 162, 168, 183, 186, 189, 243, 246, 249, 261, 264, 267, 321, 324, 327, 342, 348, 369, 381, 384, 387, 423, 426, 429, 462, 468, 483, 486, 489, 621, 624, 627, 642, 648, 681, 684, 687, 723, 726, 729, 741, 762, 768, 783, 786, 789, 843, 846, 849, 861, 864, 867, 921, 924, 927, 942, 948, 963, 981, 984, 987]
4: 68
	[1236, 1264, 1268, 1296, 1472, 1476, 1624, 1628, 1684, 1832, 1836, 1864, 1892, 1896, 2436, 2468, 2496, 2648, 3216, 3248, 3276, 3428, 3692, 3812, 3816, 3872, 3876, 4236, 4268, 4296, 4628, 4832, 4836, 4892, 4896, 6248, 6428, 6812, 6872, 7236, 7264, 7268, 7296, 7412, 7416, 7624, 7628, 7684, 7832, 7836, 7864, 7892, 7896, 8432, 8436, 8492, 8496, 8612, 8672, 9216, 9248, 9276, 9428, 9632, 9812, 9816, 9872, 9876]
5: 68
	[12365, 12645, 12685, 12965, 14725, 14765, 16245, 16285, 16845, 18325, 18365, 18645, 18925, 18965, 24365, 24685, 24965, 26485, 32165, 32485, 32765, 34285, 36925, 38125, 38165, 38725, 38765, 42365, 42685, 42965, 46285, 48325, 48365, 48925, 48965, 62485, 64285, 68125, 68725, 72365, 72645, 72685, 72965, 74125, 74165, 76245, 76285, 76845, 78325, 78365, 78645, 78925, 78965, 84325, 84365, 84925, 84965, 86125, 86725, 92165, 92485, 92765, 94285, 96325, 98125, 98165, 98725, 98765]
6: 20
	[123654, 129654, 147258, 183654, 189654, 321654, 327654, 369258, 381654, 387654, 723654, 729654, 741258, 783654, 789654, 921654, 927654, 963258, 981654, 987654]
7: 11
	[1296547, 1472583, 3216549, 3692584, 3816547, 7296541, 7296548, 7836542, 7836549, 9216543, 9632581]
8: 1
	[38165472]
9: 1
	[381654729]
0.04 real         0.02 user         0.01 sys

kinda a pointless optimization, but does show how this can be implemented trivially in other languages...

from https://csokavar.hu/blog/2010/04/problem-of-the-week-9-digit-problem/

Explanation: the problem is to find a number with 9 digits (unique), that is divisible by 9, and when you remove the rightmost digit it is divisible by 8, and so on. Pretty trivial; this is a bit random, but I stumbled across this it as an example exercise from the build-you-a-haskell series here: https://gergo.erdi.hu/blog/2010-04-19-unary_arithmetics_is_even_slower_than_you'd_expect/.

The way my solution works is to start with the 1-case (all numbers 1-9), and build up an incremental list of all of the numeric permutations that meet the divisibility criteria, ie. a number (visited digits), and a set of unvisited digits. The set can be optimized into integer bitmasks, since obviously you can store all 9 values in, well, 9 bits. After that there's two useful optimizations that can be made: first, '5' MUST occur in the 5th position (since decimal arithmetic and no '0's), so a) only a 5 will appear on the 5th iteration, b) a 5 cannot appear anywhere else. Second, odd digits can be skipped for the even iterations, since the even cases must ofc be divisible by 2. Pointless optimizations, but hey, this is slightly more optimal (albeit less general).

Algorithm is naive (O(N^3)?), but is fast b/c small N: 2 iterations over [1, 9], and one iteration over the accumulated list, which never grows large due to the filtering criteria.

Output lists the iteration #, # results, and list of matching numbers. By the 9th (actually 8th) iteration there is only one result.

The bitmask version displays fewer results due to skipping 5 until the 5th iteration.