Puzzle - RPL and others

[3298]

After I theorycrafted this scheme of sorting base-N digits into buckets based on their GCD with the base (this is what the divisibility stuff boils down to, I just failed to realize that earlier)... I couldn't resist the temptation to try and implement it. Yes, I'm jumping past the odd/even and ==base/2 checking stages, but the way I baked it into my program should make the recursive subroutine faster in all situations than with those two simple tests, even in situations like bases 6 and 8 where my buckets match up perfectly with those tests, thanks to bitset juggling and the fact I already have a bitset check in there.

Code:

::
  CK1NoBlame FPTR2 ^CK1Z
  DUP FPTR2 ^Z># DUP #2-
  BINT63 #> caseSIZEERR
  DUPONE #AND #0<> case2DROP
  WORDSIZE 1LAMBIND
  ERRSET ::
    BINT64 dostws BINT1 #>HXS
    OVER ONE_DO
      DUP ONE{}N 4UNROLL
      DUP4UNROLL bitSL
    LOOP
    DROP' ::
      OVER #2* #3+ GETLAM
      4PICK bitAND UNROT
      3GETLAM FPTR2 ^QMul 1GETLAM
      3PICK 3PICKOVER FPTR2 ^#>Z
      FPTR2 ^Mod FPTR2 ^Z># #-
      DO
        INDEX@ #2* #2+ GETLAM
        4PICKOVER bitAND
        OVER HXS==HXS %0=
        ITE_DROP ::
          bitNOT 5PICK bitAND
          3PICK#1+_ 3PICK INDEX@
          FPTR2 ^#>Z FPTR2 ^QAdd
          OVER 1GETLAM #<>case
          2GETEVAL
          ROTDROPSWAP
          #2* #2* #3- UNROLL
        ;
      OVER +LOOP
      4DROP
    ;
    SWAP' NULLLAM OVER #2* #1+
    NDUPN DOBIND

    1GETLAM ONE_DO
      1GETLAM INDEX@
      BEGIN
        SWAPOVER #/ DROP
      #0=UNTIL
      DROP #2* #3+ DUP GETLAM
      INNERCOMP INDEX@ ROTOVER
      #2* #2+ GETLAM bitOR
      ROT#1+ {}N SWAP PUTLAM
    LOOP
    1GETLAM ONE_DO
      INDEX@ #2* #3+ GETLAM
      DUPTYPEHSTR?
      ITE_DROP ::
        INNERCOMP ONE_DO
          DUPROT #2* #3+ PUTLAM
        LOOP
        DROP
      ;
    LOOP

    BINT0 #>HXS bitNOT BINT1 Z0_
    2GETEVAL
    ABND
  ; ERRTRAP ::
    1GETLAM dostws ERRJMP
  ;
  1GETABND dostws
;

(405.5 bytes, #C476h)
The goal was to make the check for whether a digit is in the right bucket for the currently processed place as quick as I could: another bitset, which gets ANDed into the bitset of not-yet-taken digits before the digit-testing loop in the recursive subroutine starts. (My previous programs used a bitset of already-taken digits, but that's just an inversion away.) The preprocessing that goes into constructing the bucket bitsets is pretty quick too, since it doesn't use many loops or particularly slow commands, and especially not recursively nested loops.
This new part is just a loop over all valid digits taking the GCD between it and the base, using an indefinite loop for a custom BINT version of the Euclidean Algorithm (since I didn't want slow back-and-forth conversion to a slower type which would likely also use that algoithm in ROM). With this GCD a list is recalled, the digit appended to it, a bitset at the end of the list updated by ORing the digit's single-bit bitset into it, and the resulting list stored back. A separate loop over the GCDs (actually over all digits, but everything that doesn't have a list gets ignored) and distributes the finished bitset to the digits in the list. This re-uses the same local variables for lists and extracted bitsets, but I made sure that's safe.
If I comment out the part that sets up the three parameters for the outermost recursive subroutine call along with the call itself (i.e. leaving only this new setup part and the small setup which existed before), the time spent is around 0.16_s for bases 22 and 24 (the highest bases I tried so far). Compare that to how long the recursive part took: 150_s for base 24, which benefits greatly from all that bucket-sorting, and a staggering 1304_s (over 21 minutes!) for base 22, which does not benefit from it at all beyond the simple odd/even and ==base/2 checks. Good ol' base 10 takes just under 2.5 seconds.
Other changes include switching the types employed for the under-construction number and bitsets from reals and BINTs to ZINTs and HXSs, respectively. ZINTs slow things down, but reals broke down partially in base 13 and fully in base 14 and beyond (because they only hold 12 decimal digits), and extended reals push this limit up by only 3. So infinite-precision integers are the way to go; I don't need a fractional part anyway. Similarly, BINTs have only 20 bits, so they only work as bitsets up to base 21; HXSs are theoretically infinite (though the ROM math routines only support up to 64 bits), but also slower. Still, slow results is better than wrong results - base 65 is the upper limit now. Without these type changes base 10 was in the neighborhood of 1 second.
Oh, and I added an early exit in basically constant time for odd bases. No point checking those anymore, just return no results immediately.

---

While climbing the ladder up to base 24, I also noticed that quite a few of the bigger even bases don't have solutions either. Assuming my code is correct, these are the solutions by base:
- 2: \(1_2 = 1_{10}\)
- 4: \(123_2 = 27_{10}, 321_2 = 57_{10}\)
- 6: \(14325_6 = 2285_{10}, 54321_6 = 7465_{10}\)
- 8: \(3254167_8 = 874615_{10}, 5234761_8 = 1391089_{10}, 5674321_8 = 1538257_{10}\)
- 10: \(381654729_{10}\), the original puzzle target
- 12: nothing
- 14: \(9C3A5476B812D_{14} = 559922224824157_{10}\)
- 16 to 24: nothing

I would have liked to dump some Babylonian numerals on you eventually (base 60), but I don't think that's going to happen if I look at the TEVAL reports for 22 and 24. The preprocessing isn't too bad (without the recursive subroutine I measured it to take 0.44 seconds for base 60), but 60 levels of recursion with a loop in each surely is just asking too much from a tortured little pocket calculator. We'd need more shortcuts to make that even remotely feasible.