Tripartite Palindromic Partition of Integer (HP 50g) Challenge

[Gerald H]

It has been proven that every positive integer is the sum of at most three palindromic integers, eg

808182838485868788

is the sum of

715133112211331517
+ 89258189498185298
+ 3791536776351973

I am very interested to see whether someone, anyone, has or can produce a programme for the 50g that calculates such a partition for any positive integer input.

Should such a programme be published here I would present the poster with a calculator (either 50g, 21S or 38G - choice up to poster) – if more than one programme posted, best programme (in my eyes) receives the calculator.

[rprosperi]

(02-15-2023 10:05 AM)Gerald H Wrote:  Should such a programme be published here I would present the poster with a calculator (either 50g, 21S or 38G - choice up to poster) – if more than one programme posted, best programme (in my eyes) receives the calculator.

Wow, now that's motivation! As many folks here frequently rise to a serious challenge simply to learn, teach or otherwise expand knowledge and sharpen skills, a real prize is a whole new class of reason to try. Similar to the programming contests held each year at HHC, this should bring about some interesting activity.

Bravo Gerald!

[ttw]

Is this for base ten, base two, or a specified base?

There are some differences between bases 2,3,4 and those bigger than 5. Even base two (are other bases odd?) has its own problems. It takes 4 numbers in base 2 as every base two number palindrome is odd and three odds is still odd (and two wrongs don't make a right but three lefts do).

[Gerald H]

Thank you, ttw, I'm only interested in base 10.

I think the problem is difficult enough for a starter - other bases later.

[Gerald H]

(02-15-2023 12:55 PM)rprosperi Wrote:  

(02-15-2023 10:05 AM)Gerald H Wrote:  Should such a programme be published here I would present the poster with a calculator (either 50g, 21S or 38G - choice up to poster) – if more than one programme posted, best programme (in my eyes) receives the calculator.

Wow, now that's motivation! As many folks here frequently rise to a serious challenge simply to learn, teach or otherwise expand knowledge and sharpen skills, a real prize is a whole new class of reason to try. Similar to the programming contests held each year at HHC, this should bring about some interesting activity.

Bravo Gerald!

Oh, I don't know, I think most members do it for the glory.

[cruff]

Something I did not see in the introduction to number theory course, but not surprised as it sounds more advanced. Do you have a reference to the proof handy?

[Albert Chan]

Hi, cruff.

Numberphile video had the links for proof, and how to solve for it.




It also had the website to quickly solve it, BEFORE YOUR VERY EYES!
OP example, I get another set of palindrome triplets (1st solution from OP)

808182838485868788
= 715133112211331517 + 89258189498185298 + 3791536776351973
= 710001111111100017 + 95993502820539959 + 2188224554228812

[Werner]

The (algorithmic) proof is a 42-page document. It isn’t necessarily hard to do, it’s just a LOT of work, many different cases…
Cheers, Werner

[Albert Chan]

OP does not ask for the most efficient way to solve this (even brute force is valid solution!)
I would just guess it, backtrack if wrong, like solving N-queen problem.

n = x+y+z, palindrome, x >= y >= z > 0, we maximize x, like this, for OP example:

808,182,838,485,868,788
808,182,837,738,281,808 −      → 747,586,980

If n-x is sum of 2 palindromes, we are done. (if not, we backtrack for smaller x)

Code:

  747586980
y 7       7
z  3      3
c 0      1

Assuming no carry, we maximize y.

Code:

  747586980
y 71     17
z  36    63
c 00    01

Code:

  747586980
y 711   117
z  368  863
c 000  001

No carry assumption is wrong, we backtrack for smaller y.

Code:

  747586980
y 710   017
z  369  963
c 001  001

Code:

  747586980
y 710686017
z  36900963
c 00100001

808182838485868788 = 808182837738281808 + 710686017 + 36900963

[Gerald H]

You are correct, Albert, that I promote any solution programme that works on a 50g, irrespective of method, nothing against brute force if programme proves efficient.

This paper

https://arxiv.org/abs/1510.07507

suggests that taking largest palindrome less than input will not fulfil my requirements - you may have a better(?) chance of success with some smaller palindrome.

[Albert Chan]

Here is another approach, n = x+y+z, greedy search for x, palindromes x >= y >= z > 0

OP example, x start with 8 implied y start with 0, "bad" palindrome. So, we backtrack a bit.
We maxmize x, by first assume no carries (backtrack if necessary).

Code:

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

Maximize x implied y values start with 0 (y=0 → z=6 → c=1 → x=5)

Code:

  808182838485868788
x 715            517
y  90             09
z   26            62
c 101            01

Code:

  808182838485868788
x 7155          5517
y  900           009
z   262          262
c 1010          001

Code:

  808182838485868788
x 71555        55517
y  9000         0009
z   2623        3262
c 10101        0001

Code:

  808182838485868788
x 715559      955517
y  90000       00009
z   26231      13262
c 101010      00001

Code:

  808182838485868788
x 7155596    6955517
y  900000     000009
z   262319    913262
c 1010101    100001

Code:

  808182838485868788
x 71555964  46955517
y  9000000   0000009
z   2623198  8913262
c 10101010  1100001

Code:

  808182838485868788
x 715559640046955517
y  90000000100000009
z   2623198338913262
c 10101010001100001

808182838485868788 = 715559640046955517 + 90000000100000009 + 2623198338913262

[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

[cruff]

(02-16-2023 02:10 AM)Albert Chan Wrote:  Hi, cruff.
Numberphile video had the links for proof, and how to solve for it.

Thanks, Numberphile is one of my favorites, I can't recall if I've watched that one or not yet.

[peruna]

Some programs involving palindromic numbers. (Note: ± is char 177 from the CHARS menu.)

'P?' # 2979h 22. Test if number is palindromic

Code:

«   →STR DUP ± ==
»

1331 P? → 1

1332 P? → 0

'±' # 7F80h 48. Reverse string or list

Code:

«   DUP SIZE { DUP HEAD SWAP TAIL ± SWAP + } IFT
»

"1234" ± → "4321"

'LP' # DDF0h 24.5 Make long palindrome

Code:

«   →STR DUP ± + OBJ→
»

1234 LP → 12344321

'SP' # 366Dh 30. Make short palindrome

Code:

«   →STR DUP ± TAIL + OBJ→
»

1234 SP → 1234321

'→P' # 5274h 85. Make starting palindrome

Code:

«   DUP →STR DUP SIZE 2 IDIV2 DUP 4. ROLLD + 1. SWAP SUB SWAP :: SP :: LP IFTE
    DUP2 ≤ :: P↓ IFT
»

1728 →P → 1661 1728

153 →P → 151 153

'P↓' # B893h 133.5 Next smaller palindrome

Code:

«   DUP XPON { DUP 1 - DUP XPON ALOG ≠ { →STR DUP SIZE 2 IDIV2 DUP 4. ROLLD +
    1. SWAP SUB OBJ→ 1 - →STR SWAP :: SP :: LP IFTE } { 2 - } IFTE } { 1 - } IFTE
»

1001 P↓ → 999

1771 P↓ → 1661

2002 P↓ → 1991

'P2' # 3947h 94. Check if number is sum of 2 palindromes

Code:

«   →P 
              DO DUP2- 
              UNTIL DUP2 < { 3. DROPN 0. 1. }
               { DUP P? { 2. →LIST SWAP } { DROP P↓ 0. }
               IFTE } IFTE
              END
        »

1553 P2 → { 1551 2 }

1771 P2 → 0.

4354 P2 → 0.

4355 P2 → { 4224 131 }

'P3' # C894h 88.5 Integer as sum of 3 positive palindromes
[code]« 3 OVER > :: NOT {→P
DO DUP2 - P2 DUP TYPE :: +
{ SWAP P↓ } IFTE
UNTIL SWAP
END } IFTE
»

58194227 P3 → { 58188185 5335 707 }

808182838485868788 P3 → { 80812837738281808 744232447 3354533 }

11 P3 → {9 1 1 }

[Werner]

Fantastic! What is the running time?
Cheers, Werner

[2old2randr]

Wow! That is such a terse and beautiful solution. I haven’t yet typed it in and run it but one thing puzzled me when looking at the code - what does ‘::’ do in user RPL?

As someone still new to RPL, I’ve been slowly transcribing the algorithms in the referenced paper to code - just have a little more to go. The solutions to the examples in the paper take around 3 secs to run on a physical hp 50g. The code is much longer (of course) and not pretty. I will post it for what it is worth hopefully by this weekend.

Sudhir

[Werner]

(02-19-2023 09:49 PM)peruna Wrote:  'U' # 5BA1h 55.5 Subroutine for 'P3'

Code:

«   DUP2 - P2 DUP TYPE { + NIP } { DROP2 P↓ U } IFTE
»

I think the DROP2 has to be a DROP

Cheers, Werner

[John Keith]

(02-21-2023 07:45 AM)2old2randr Wrote:  ... but one thing puzzled me when looking at the code - what does ‘::’ do in user RPL?


Sudhir

That's called a "null tag". It's another way of delaying execution of an object, with the advantage that it takes less memory than a program. I first learned about it from Joe Horn here. It is undocumented and some consider it to be questionable programming practice so use at your own risk.

[3298]

Yes, that DROP appears to make it work at least (try 100001102 to see it stumble while backtracking without that correction). Checksum still doesn't match though (#0FCCh before correction, #84DCh after, but neither is the #5BA1h listed).

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 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.)


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.

[John Keith]

(02-19-2023 09:49 PM)peruna Wrote:  Some programs involving palindromic numbers. (Note: ± is char 177 from the CHARS menu.)

'P?' # 2979h 22. Test if number is palindromic

Code:

«   →STR DUP ± ==
»

1331 P? → 1

1332 P? → 0

'±' # 7F80h 48. Reverse string or list

Code:

«   DUP SIZE { DUP HEAD SWAP TAIL ± SWAP + } IFT
»

"1234" ± → "4321"

Interesting programs, and very nice programming style IMHO. If you use the ListExt Library, your program '±' can be replaced by REV, and P? can be replaced by

Code:

«   DUP REV SAME
»

The command REV will reverse a string, a list or an integer and is many times faster than any User RPL equivalent.