+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: Tripartite Palindromic Partition of Integer (HP 50g) Challenge (/thread-19563.html)
Tripartite Palindromic Partition of Integer (HP 50g) Challenge - Gerald H - 02-15-2023 10:05 AM
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
+ 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.
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - rprosperi - 02-15-2023 12:55 PM
(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!
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - ttw - 02-15-2023 03:22 PM
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).
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - Gerald H - 02-15-2023 03:39 PM
Thank you, ttw, I'm only interested in base 10.
I think the problem is difficult enough for a starter - other bases later.
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - Gerald H - 02-15-2023 03:41 PM
(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.
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - cruff - 02-16-2023 12:31 AM
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?
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - Albert Chan - 02-16-2023 02:10 AM
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
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - Werner - 02-16-2023 07:07 AM
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
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - Albert Chan - 02-16-2023 09:12 PM
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 1Assuming no carry, we maximize y.
Code:
747586980
y 71 17
z 36 63
c 00 01Code:
747586980
y 711 117
z 368 863
c 000 001No carry assumption is wrong, we backtrack for smaller y.
Code:
747586980
y 710 017
z 369 963
c 001 001Code:
747586980
y 710686017
z 36900963
c 00100001808182838485868788 = 808182837738281808 + 710686017 + 36900963
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - Gerald H - 02-17-2023 03:38 AM
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.
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - Albert Chan - 02-17-2023 07:37 AM
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 1Maximize 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 01Code:
808182838485868788
x 7155 5517
y 900 009
z 262 262
c 1010 001Code:
808182838485868788
x 71555 55517
y 9000 0009
z 2623 3262
c 10101 0001Code:
808182838485868788
x 715559 955517
y 90000 00009
z 26231 13262
c 101010 00001Code:
808182838485868788
x 7155596 6955517
y 900000 000009
z 262319 913262
c 1010101 100001Code:
808182838485868788
x 71555964 46955517
y 9000000 0000009
z 2623198 8913262
c 10101010 1100001Code:
808182838485868788
x 715559640046955517
y 90000000100000009
z 2623198338913262
c 10101010001100001808182838485868788 = 715559640046955517 + 90000000100000009 + 2623198338913262
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - Albert Chan - 02-17-2023 03:57 PM
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 1Maximize x: y=0 → z=6 → c=1 → x=5
Code:
808182838485868788
x 715 517
y F0 0F
z 26 62
c 101 01Continue 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 1001001y=0 → z=8 → c=1 → x=9. With y center = 2, we have the triplets.
Code:
808182838485868788
x 715B557F99F755B517
y F000000020000000F
z 262D03E88E30D262
c 101010111110010010x808182838485868788 = 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
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - cruff - 02-18-2023 01:14 AM
(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.
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - peruna - 02-19-2023 09:49 PM
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 }
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - Werner - 02-21-2023 05:49 AM
Fantastic! What is the running time?
Cheers, Werner
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - 2old2randr - 02-21-2023 07:45 AM
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
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - Werner - 02-21-2023 08:37 AM
(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
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - John Keith - 02-21-2023 05:22 PM
(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.
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - 3298 - 02-21-2023 05:38 PM
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.
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge - John Keith - 02-21-2023 05:46 PM
(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
»