Tripartite Palindromic Partition of Integer (HP 50g) Challenge

[Albert Chan]

(02-21-2023 05:38 PM)3298 Wrote:  Since I'm currently working with an emulated 50g, how slow is the given 16-digit example take on a physical 50g? With x49gp on an i5-5500U (yes, I know, time for an upgrade, but I know it outruns the physical 50g despite the Saturn-on-ARM-on-x86 nested emulation) it's (100001102) around 16 seconds. I even observed a 13-digit number taking over 40 seconds (1000000110002), but that's an outlier because it's specifically crafted to cause extra backtracking. (You're probably seeing a similarity with the stumbling case above; that pattern is taken from another paper referenced in the proof, which deals with especially evil cases.)

Here is a way to avoid backtracking, by grouping sum of 3 palindromes as a pair.

n = x + (y+z) = (x+y) + z

Bracketed variables have same number of digits, m. (unless 1 variable is plain 0)

Let one of variable = b^m - 1, where b is the base.
The other variable digits (except for first), ranged from -(b-1) to (b-1)

If m is odd, bracketed center is the last cell to calculate.
If center cell have no carry, it is always valid = (0 to b-1) - (0 to b-1) = -(b-1) to (b-1)

(n, 13 digits) = 1000000110002 = (x, 12 digits) + (y+z, both 11 digits)
n - y = n - (10^11-1) = 900000110003 = x + z

Code:

   9  0  0  0  0  0  1  1  0  0  0  3
x  9  6  6  6  6  5  5  6  6  6  6  9
z    -6 -6 -6 -6 -5(-4)-5 -6 -6 -6 -6
c

1000000110002 = 966665566669 + 33334543333

For comparison, this is with n = (x+y, both 12 digits) + (z, 11 digits)
n - y = n - (10^12-1) = 110003 = x + z

Code:

   0  0  0  0  0  0  1  1  0  0  0  3 = (x+y) + z
x -1  6 -4 -3 -3 -4 -4 -3 -3 -4  6 -1
z     4  4  3  3  4 (5) 4  3  3  4  4
c  1                          1

1000000110002 = 795665566597 + 160000000061 + 44334543344

This setup, last cell is now limited to 0 to 9.
Luckily, the fix to correct to valid palindromes is easy.

[1,1] ≡ [1,-9,1] ≡ [1,-9,-9,1] ≡ [1,-9,-9,-9,1] ≡ ...

---

OP example:

n - y = 808182838485868788 - (10^17-1) = 708182838485868789 = x + z

Code:

   7  0  8  1  8  2  8  3  8  4  8  5  8  6  8  7  8  9
x  6  7  7  1  1  7  6  4  4  4  4  6  7  1  1  7  7  6
z     3  1  0  7 -5  2 -1  4 (0) 4 -1  2 -5  7  0  1  3
c  1                                  -1

808182838485868788 = 677117644446711776 + 99994989998949999 + 31070204040207013