|No such thing as a small change|
Efficient enumeration of pandigital fractionsby kikuchiyo (Friar)
|on Jul 20, 2018 at 20:51 UTC||Need Help??|
kikuchiyo has asked for the wisdom of the Perl Monks concerning the following question:
The fraction 6952 / 1738 has a curious property: each non-zero decimal digit appears exactly once in the expression, and the result of the divison happens to be the missing digit, 4.
Are there, by any chance, other fractions that share this property? It is fairly simple to devise a semi-brute force solution to answer this question:
restate the problem as abcd = efgh * i, generate all 5-element variations (k-permutations) of the set of digits 1..9, perform the multiplication and check that the result consists only of digits not in the sequence.
Here is a somewhat optimized implementation:
For base 10 this runs quickly enough to find that there is one additional solution. But for the obvious and straightforward generalization to higher bases this brute force solution is not going to cut it.
Tinkering with the innards of the loop or using a different permutation engine might give us a speedup factor of two, while rewriting the whole thing in C might give us two orders of magnitudes. But we'd be still generating all permutations, and the number of those grows relentlessly as the base increases ((b - 1)! / (b/2 - 1)!):
6 60 8 840 10 15120 12 332640 14 8648640 16 259459200 18 8821612800 20 335221286400
On my machine the program above needed 6 seconds to find all base-14 solutions, more than 3 minutes for base-16, and I dared not run it with higher bases.
However, the number of actual solutions is much smaller:
6 1 8 2 10 2 12 18 14 136 16 188
which suggests that there may be better, more efficient approaches that don't have to trudge through a lot of useless permutations to find the solutions. However, so far I haven't been able to find one.