Tripartite Palindromic Partition of Integer (HP 50g) Challenge

[Albert Chan]

Greedy search algorithm work with other base too.
We redo OP example, but this time assumed n is really hex digits.

Maximize x, assume no carry.

Code:

  808182838485868788
x 71              17
y  F               F
z   2              2
c 10              1

Maximize x: y=0 → z=6 → c=1 → x=5

Code:

  808182838485868788
x 715            517
y  F0             0F
z   26            62
c 101            01

Continue fill the digits, we ended-up with a bad x, with digit ? = -1
We backtrack for valid x, 8? --> 7F, and continue

Code:

  808182838485868788         808182838485868788
x 715B558?  ?855B517  -->  x 715B557F  F755B517
y  F000000   000000F       y  F000000   000000F
z   262D03D  D30D262       z   262D03E  E30D262
c 10101001  1001001        c 10101011  1001001

y=0 → z=8 → c=1 → x=9. With y center = 2, we have the triplets.

Code:

  808182838485868788
x 715B557F99F755B517
y  F000000020000000F
z   262D03E88E30D262
c 10101011111001001

0x808182838485868788 = 0x715B557F99F755B517 + 0xF000000020000000F + 0x262D03E88E30D262

---

To simplify backtracking, we could assume y digits start with 1.
Now, x is not maximized, but it is not OP requirement, thus OK.

Backtracking is simply changing y=1 to y=0. All generated x digits are good.
Bonus: we have an intuitive proof that n = sum of palindrome triplets. (when x digits all filled)

0x808182838485868788 = 0x714B4570880754B417 + 0xF111110161011111F + 0x252C02E66E20C252