Tripartite Palindromic Partition of Integer (HP 50g) Challenge

[Albert Chan]

(03-03-2023 10:57 AM)Gerald H Wrote:  I believe ALGO5 is not necessary.

Removing ALGO5 & eg

12267420107203532444

is correctly partitioned, although differently than in the proof by Cilleruelo.

It may not be necessary for this particular number, but we want to be safe in general.
With center 0, it may lead to a palindrome with invalid center, which may be messy to fix.

I like my simpler "palindrome" pair algorithm.

At the center, there are less special cases to consider.
If no carry, center cell is always vaild = (0 .. 9) - (0 .. 9) = (-9 .. 9)
Even with carry, if (n-y) center is not 0 or 9, we are also safe: (1 .. 8) - (0 .. 9) ± 1 = (-9 .. 9)

Only 2 cases may lead to problem: (n-y) - x = z + (non-zero carry)

0 - 9 = (−10) + 1
9 - 0 = (+10) − 1

To get into these situations are rare. Almost always, no backtracking fix needed.

Here is an example that generated invalid center (±10), required backtracking to fix.
NOTE: n is quoted number, but with center adjusted, to purposely get into trouble.

n = 12267420150203532444 (20 digits)
y = 10^19 - 1 (we always pick odd digits y)

(n-y) also 19 digits, so we search for n = (x+y, both 19 digits) + (z, 18 digits)      (*)

Code:

n-y 2   2   6   7   4   2   0   1   5   0   2   0   3   5   3   2   4   4   5
x   2  -1   1   4  -4  -4  -9  -1   3 (-10) 3  -1  -9  -4  -4   4   1  -1   2
z       3   5   3   8   6   9   2   2   9   9   2   2   9   6   8   3   5   3
                                        1      -1           1

Except for center, x digits are generated from LHS, without carry, thus always valid.

With (n-y) center = 0 AND (last z = 9) AND (carry = +1), x center is invalid.
There is no need to backtrack a lot. All we needed is to avoid last z = 9.
z center of 229 → 218 is enough, guaranteed valid x center.

Code:

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

12267420150203532444 = 9899550931390559989 + 2014000000000004102 + 353869218812968353

(*) We only switch to n = x + (y+z) if (n-y) > y (i.e. balance with more digits)
Otherwise, we do n = (x+y) + z, pad with zeroes if necessary.

Above example, n of 122... changed to 100...

Code:

                               7998995386835998997
  10067420150203532444       + 1460210000000120641
-  9999999999999999999       +  608214763367412806
----------------------  -->  ---------------------
   0067420150203532445        10067420150203532444

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