Puzzle - RPL and others

[3298]

Thank you, Albert Chan, for expanding my observation and ideas into a proper proof, because that's not quite my area of expertise. I hope you didn't feel pressured into it.

(04-28-2021 03:30 AM)Albert Chan Wrote:  restricting odd digits odd, even digits even, speed up a lot !

I was going to say that this doesn't work for odd bases, but as we just found out, we can reject those before we get here, since they can't have solutions anyway...

But thinking about why it wouldn't apply to odd bases pushed me into another idea building on this: the shortcut works for any number that divides the base. You already applied this with the number 5 in base 10 ... the fifth position has to be 5, as it is the only base-10 digit divisible by 5.
To take another example, in base 12 we would be looking at divisibility by 2, by 3, by 4, and by 6 (these are the numbers that divide 12 without remainder). Then we can sort all digits into buckets where all digits in the same bucket have the same divisibility results, and when we get to check if a digit is allowed in position <i>, add a third check into the mix: only digits in the bucket containing <i> are allowed.

Not sure if all that complexity is worth it, but at least on bases with a high number of divisors it might eliminate another handful of checks. And the whole business of sorting digits into buckets only needs to be performed once per base, not at each recursion level. For an implementation of the check if a given digit is in the same bucket as another, I'm imagining a lookup table holding references to the buckets that correspond to the lookup table index (O(1)), and the buckets themselves are sets which can be implemented as an array of booleans, a.k.a. another bitset (also O(1)). That means an O(1) check overall.

Maybe generating the buckets could even be optimized by cutting the list of factors down to prime factors with multiplicities, i.e. if we look at the base-12 example again (prime factors are 2 with a multiplicity of 2 and 3 with a multiplicity of 1), digit divisibility by 2 is separated into not divisible (=2^0), divisible by 2^1, and divisible 2^2, while 3 is sorted into not divisible (=3^0) and divisible (=3^1), for a total of three options times two options = six buckets. The last one will always stay empty, because if you multiply all prime factors in full multiplicities back together (2^2 * 3^1 = 12), you get the base, which isn't a valid digit (and neither are its multiples, for obvious reasons). The others are { 1 5 7 11 } { 2 10 } { 4 8 } { 3 9 } { 6 }.

I don't have an implementation to run performance tests on, this is just an idea still. Maybe later.