Tripartite Palindromic Partition of Integer (HP 50g) Challenge

[3298]

Just replacing ± with SREV (from builtin library 256; reverses a string) roughly halves runtime. I can't be bothered to test ListExt, but its string reversal is likely on the same level, and if I were to guess, using its integer reversal probably gives a smaller but still substantial boost on top.

[2old2randr]

(02-21-2023 05:38 PM)3298 Wrote:  Anyway, I'm in the process of translating the proof's algorithm into SysRPL code. Between SysRPL speed in general and the lack of backtracking in that algorithm (the "correction step" isn't really backtracking, right? 'cause it's not repeated, it merely looks like another set of if-then-else at the end), I'm expecting it to be quicker to execute ... once I am done implementing all those pesky branches of that algorithm at least. Although that'll probably take another few days.

Yes, my user RPL version (not quite complete) does 21-22 digit numbers in less than 3 seconds on a physical 50g so your sysRPL version should be practically instantaneous.

One thing that tripped me up several times is that the authors do not have consistent indexing subscripts between the 4 arrays that they use. There is 0-based indexing, 1-based indexing and 2-based indexing at different places ...

Sudhir

[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

[Werner]

(02-22-2023 01:57 AM)Albert Chan Wrote:  (n, 13 digits) = 1000000110002 = (x, 12 digits) + (y+z, both 11 digits)

Trying to make sense of your very brief description ;-)
How do you know to take x 12 digits and not 13? (13 doesn't work as 110001 cannot be written as the sum of 2 palindromes)

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

The '-5' underneath the 6, how do you know it has to be -5 and not 5?
Cheers, Werner

[Albert Chan]

(02-22-2023 09:07 AM)Werner Wrote:  How do you know to take x 12 digits and not 13?

If x is 13 digits, n = x + (y+z), y must be 12 digits = 10^12-1
Note: to avoid backtracking, we prefer odd digits y ... but, let's ignore this for now.

n-y = (10^12+110002) - (10^12-1) = 110003 = x+z --> x cannot be 13 digits palindrome.

If we force it anyway, we have a contradiction of x > n (palindrome x, first digit cannot be 0)

Code:

   0  0  0  0  0  0  0  1  1  0  0  0  3
x  1  8                                1
z    -8                               -8
c                                  -1

(02-22-2023 09:07 AM)Werner Wrote:  The '-5' underneath the 6, how do you know it has to be -5 and not 5?

The goal is not to backtrack, whatever digits written all good.

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                          1  1  7  7  6
z     3  1  0  7  ?                       ?  7  0  1  3
c  1

If ? = 5, we required carry, and backtracking(s) to correct for the changes.

Code:


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

If ? = 5 - 10 = -5, we can just keep going ...

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                    7  1  1  7  7  6
z     3  1  0  7 -5                      -5  7  0  1  3
c  1                                  -1

Note that 8 - 6 = 8 - (7-1) --> next z=2, whether we backtrack with carry, or not.
Both setup, unfilled digits are exactly the same. We can easily show this:

Δx = [1, 1, ..., 1, 1] ≡ [0, b+1, ..., 0, b+1]      // horner's rule with base b, gives same result

To maintain same x+z, x of [0, 6] → [1, 7], required z of [7, 6] → [7, 6-11] = [7, -5]

[Albert Chan]

(02-22-2023 02:17 PM)Albert Chan Wrote:  Note: to avoid backtracking, we prefer odd digits y ... but, let's ignore this for now.

Here is an example to show the reason for preferring odd y digits.

n = 80818283828586878      // similar to OP example, but not quite.

(n, 17 digits) = (x, 17 digits) + (y+z, both 16 digits)
n - (10^16-1) = 70818283828586879 = x + z

Code:

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

Note that x is not a valid palindrome, and require backtracking to fix.
Top half of x (no center) = 67813794 - 1 = 67813793

[1, 2, 1] ≡ [0, b+2, 1] ≡ [0, b+1, b+1]      // horner's rule with base b, gives same result

To maintain same x+z, x of [4, 10] → [3, 8], required z of [-1, -2] → [-1, -2+11] = [-1, 9]

80818283828586878 = 67813793839731876 + 9999488998849999 + 3005000990005003

---

(n, 17 digits) = (x, 17 digits) + (y+z, both 15 digits)
n - (10^15-1) = 79818283828586879 = x + z

Code:

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

With odd y digits, no backtracking required

80818283828586878 = 79636957575963697 + 979295949592979 + 202030303030202

---

Another way, still keeping digits(y) odd, n = (x+y) + z

80818283828586878 - 69999999999999996 = 10818283828586882

Code:

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

80818283828586878 = 58813000100031885 + 19999694949699991 + 2005588778855002

[2old2randr]

Edit: A complete implementation of the algorithms in the paper (incl. 2-6 digit cases) is attached to a later post. Peruna's code as included here has bugs that do not return correct results for some numbers.

Here is my implementation (in User RPL) of the algorithms in the paper by Cilleruelo, Luca and Baxter. Although I did code their algorithms for "small" numbers (less than 7 digits), I've used Peruna's solution posted earlier for these cases since it is much faster for 5 and 6 digit numbers.

The code takes 65 minutes (measured using TICKS) to compute solutions for the range (100000000 to 100001102), i.e., 3 seconds per number on average. This is on a physical HP 50g

For 80818283828586878, it produces the solution {71110101010101117, 9500653333560059, 207529484925702} in around 3 seconds.

I've used lists as the number representation but this is possibly not the best way to do it although it does make it easy to verify against the algorithms in the paper.

The main program is in PALIN.txt, the classification routine is NTYPE and the algorithms are in ALGO1-ALGO5. For numbers with less than 7 digits, it falls back on Peruna's code in SMALL.

Edit: I have removed the attachment since the code has gone through many bug fixes and this is woefully out-of-date. The fixed code is attached to a later post.

[2old2randr]

I should have mentioned that my code uses ListExt (I\->NL, NL\->I and REV) in order to convert the input number into a list and the lists back to numbers at the end.

Sudhir

[2old2randr]

I found an embarrassing number of typos in the code I posted earlier. I found these when trying to exercise all code paths and I think I've fixed everything so I've updated the zip file in the original post. Sorry about that.

Sudhir

[Gerald H]

As posted (#14), peruna, your programme functions nicely except for numbers of a certain form, eg 1132 - this lack is supplied by Werner's emendation in post #17. Could you, peruna, perhaps edit the posting so we have a correct version in this thread? (This editing has now been done.)

In answer to 3298's question (post 19), the 18 digit test number in post #1 takes 19sec on my real 50g. I have made some small changes to peruna's programmes.

Could you, 2old2randr, please publish here your collection of programmes as they appear on the screen of the calculator, I have problems to transfer them to the calculator in the format you use. eg

Code:

  « DUP P? { 0 0 3. →LIST } { →P U } IFTE
»

Also do you have suggestions how to produce three guesses for input to the programme?

[2old2randr]

(02-28-2023 09:54 AM)Gerald H Wrote:  Could you, 2old2randr, please publish here your collection of programmes as they appear on the screen of the calculator, I have problems to transfer them to the calculator in the format you use. eg

This is difficult to do because symbols such as "greater than or equal to" on the 50g are represented by character code 138 (for example) but this a different character in Unicode. This is why all the non-ASCII characters in my programs are represented by trigraphs ("\>=" and "\<<" for example) that can be understood by the calculator as documented in the AUR appendix J.

My method of working is to type in the code on my Mac using a regular text editor, transfer to the HP 50g using the SD card, convert into a program from string and then test on the calculator. Sadly, there seem to be no dev tools for RPL on the Mac so I don't have a choice even though this approach is inefficient.

The string to code object translation is done using the below program (I got this from a post in this forum) which translates strings to objects (and EVALs) or object to string depending on what is on the stack.

Code:


« RCWS RCLF → ws f
    « 3 TRANSIO DUP
        IF TYPE 2 == THEN
            →STR
            f SIZE 3 > #2F34Dh #3016Bh IFTE SYSEVAL + STR→
        ELSE
            STD 64 STWS →STR
            f SIZE 3 > #2F34Eh #2FEDDh IFTE SYSEVAL
        END
        ws STWS f STOF
    »
»
'INOUT' STO

Quote:Also do you have suggestions how to produce three guesses for input to the programme?

The program cannot take guesses as an input since it is a translation of the algorithmic proof in the paper referred to previously. The way it works is that depending on the given number, the three palindromes (x, y and z) are assumed to be of a certain form (length and first one or two digits of each). Subsequently, the remaining digits of the palindromes are simultaneously generated from the end towards the middle one digit at a time. In general, the digit in position 'n' for x depends on the input number and the digits of x, y and z in position 'n-1'. Sometimes additional digits are considered. Similarly, for y and z - these also take into account the digits generated for x and y in position 'n'.

In any case, there was a serious bug in ALGO5 which I've corrected and the attachment in the original post has been updated.

Sudhir

[Gerald H]

Excellent work, 2old2randr!

Error in ALGO5, for input 29150497 the largest element of answer is a real, with "." at the end, rather than an integer.

[2old2randr]

(03-01-2023 08:09 AM)Gerald H Wrote:  Error in ALGO5, for input 29150497 the largest element of answer is a real, with "." at the end, rather than an integer.

Yes, that is due to my not having used IDIV2 in ALGO5 - I will fix it on the weekend when I have time.

Sudhir

[Gerald H]

Could you, 2old2randr, suggest a number that requires ALGO4?

I haven't managed to find a number of such form.

[Gerald H]

Right, I've found a number requiring ALGO4, namely

106700620371

& the programmes return 7 levels to the stack

"B1"
List of numbers
"B1"
List of numbers

1313111002211313
5063993605
525515525

Do you get the same answer? Is it my sloppy copying of the programmes?

[2old2randr]

I had also run into this issue a couple of days ago with a different number.

The error you are seeing is due to a 'PUT' missing on the line following 'THEN "B1"' in NTYPE. The line should read "p1 1 1 PUT p1 n 1 PUT".

There is also a bug (a typo) in ALGO4 - the line with the comment "@ IV.4" reads
'p1 m GET - ==' but should be 'p1 m GET 0 =='.

Both are fixed in my code but I did not have time to package and update my original post (along with the ALGO5 issue that you pointed out yesterday) - sorry about that.

Your example returns the following solution with those two lines fixed.
101112211101
5028228205
560181065

Sudhir

[Gerald H]

Thank you, 2old2randr, correction cures error for 106700620371.

The typo you mention is not present in the algorithms I downloaded.

[Gerald H]

Here a faster version of programme PALIN.

ID xI→NL is a stand alone version of ListExt function as I prefer to have a stand alone library.

Code:

Size: 381.

CkSum: # C5B5h

::
  CK1&Dispatch
  # FF
  ::
    DUP
    ID xI→NL
    DUPLENCOMP
    UNCOERCE
    DUP
    %7
    %<
    case
    ::
      2DROP
      ID P3
      INCOMPDROP
    ;
    SWAP
    ID NTYPE
    {
      LAM num
      LAM n
      LAM type
      LAM special
      LAM d
      LAM p1
      LAM p2
      LAM p3
    }
    BIND
    LAM special
    FPTR2 ^ZIsOne?
    ITE
    ::
      LAM num
      LAM p1
      ID ALGO5
    ;
    ::
      LAM d
      LAM p1
      LAM p2
      LAM p3
      {
        "A1"
        "A2"
        "A3"
        "A4"
      }
      LAM type
      EQUALPOSCOMP
      UNCOERCE
      LAM n
      %2
      %MOD
      XEQAND_
      {
        "A5"
        "A6"
      }
      LAM type
      EQUALPOSCOMP
      UNCOERCE
      LAM n
      %2
      %MOD
      XEQNOT_
      XEQAND_
      XEQOR_
      %1
      %=
      case
      ID ALGO1
      LAM type
      CAR$
      CHR \41
      EQUAL
      case
      ID ALGO2
      LAM n
      %2
      %MOD
      %0=
      case
      ID ALGO4
      ID ALGO3
    ;
    ABND
  ;
;

[Gerald H]

I believe ALGO5 is not necessary.

Removing ALGO5 & eg

12267420107203532444

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

[2old2randr]

I have updated the program in my original post to correct two typos and a bug pointed out by Gerald H

1. IDIV2 is used in ALGO5 to avoid returning a real (with '.') rather than integer in the solution.
2. There was a missing 'PUT' in NTYPE on the line following 'THEN "B1"'.
3. There was a '-' instead of '0' in ALGO4 on the line after the comment "@ IV.2.iii"

I think there are no more typo-style errors in the code.

Sudhir