Post Reply 
Tripartite Palindromic Partition of Integer (HP 50g) Challenge
02-15-2023, 10:05 AM (This post was last modified: 05-03-2023 06:25 AM by Gerald H.)
Post: #1
Tripartite Palindromic Partition of Integer (HP 50g) Challenge
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.
Find all posts by this user
Quote this message in a reply
02-15-2023, 12:55 PM
Post: #2
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
(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!

--Bob Prosperi
Find all posts by this user
Quote this message in a reply
02-15-2023, 03:22 PM (This post was last modified: 02-15-2023 03:33 PM by ttw.)
Post: #3
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
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).
Find all posts by this user
Quote this message in a reply
02-15-2023, 03:39 PM
Post: #4
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Thank you, ttw, I'm only interested in base 10.

I think the problem is difficult enough for a starter - other bases later.
Find all posts by this user
Quote this message in a reply
02-15-2023, 03:41 PM
Post: #5
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
(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.
Find all posts by this user
Quote this message in a reply
02-16-2023, 12:31 AM
Post: #6
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
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?
Find all posts by this user
Quote this message in a reply
02-16-2023, 02:10 AM
Post: #7
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
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
Find all posts by this user
Quote this message in a reply
02-16-2023, 07:07 AM
Post: #8
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
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

41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE
Find all posts by this user
Quote this message in a reply
02-16-2023, 09:12 PM
Post: #9
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
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
Find all posts by this user
Quote this message in a reply
02-17-2023, 03:38 AM
Post: #10
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
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.
Find all posts by this user
Quote this message in a reply
02-17-2023, 07:37 AM
Post: #11
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
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
Find all posts by this user
Quote this message in a reply
02-17-2023, 03:57 PM (This post was last modified: 02-17-2023 11:21 PM by Albert Chan.)
Post: #12
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
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
Find all posts by this user
Quote this message in a reply
02-18-2023, 01:14 AM
Post: #13
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
(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.
Find all posts by this user
Quote this message in a reply
02-19-2023, 09:49 PM (This post was last modified: 03-05-2023 01:55 PM by peruna.)
Post: #14
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
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 }
Find all posts by this user
Quote this message in a reply
02-21-2023, 05:49 AM
Post: #15
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Fantastic! What is the running time?
Cheers, Werner

41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE
Find all posts by this user
Quote this message in a reply
02-21-2023, 07:45 AM
Post: #16
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
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
Find all posts by this user
Quote this message in a reply
02-21-2023, 08:37 AM
Post: #17
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
(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

41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE
Find all posts by this user
Quote this message in a reply
02-21-2023, 05:22 PM
Post: #18
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
(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.
Find all posts by this user
Quote this message in a reply
02-21-2023, 05:38 PM
Post: #19
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
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.
Find all posts by this user
Quote this message in a reply
02-21-2023, 05:46 PM
Post: #20
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
(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.
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 3 Guest(s)