"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
I just brute-force tested it for bases 3 through 20 for digit products 1 through 5000. The first two bases for which any exceptions were found were 9 and 13. The first exception found was base 9, digit product 72, 266(9) by brute force, 338(9) by greedy.
I've pushed a little further. I've confirmed that David Wilson's greedy algorithm works for all numbers less than B^9 for bases 2 through 8, and for bases 10, 11, 12, and 16. For instance I've confirmed that it works in base 10 for all numbers less than a billion. (By "numbers" I mean the numbers whose digits are to be multiplied, not necessarily the products thereof). (Of course proving that it always works in bases 2 and 3 is easy.) It fails quite rapidly for all other bases through at least base 85. For instance for bases 13, 14, and 15, digit product 180, the greedy algorithm finds 35C, but the correct answer is 29A. (Yes, it's the same pattern of digits in all three bases, but not, of course, the same number.) For each failed base, there are lots of failures, not just the ones I listed. Why should it always either fail rapidly or (apparently) not at all? What's special about 2,3,4,5,6,7,8,10,11,12,16? (Not in OEIS.)