Tripartite Palindromic Partition of Integer (HP 50g) Challenge

[Gerald H]

Further

92805

returns

82128
9889
808

Sum is wrong.

[3298]

I followed the steps in the proof for that input number by hand, and it looks like an issue with the proof, not a particular implementation of its algorithm.

92805 is a 5-digit number with something other than 1 as most significant digit ...

The proof Wrote:then \(n\) is of type A and we apply Algorithm I, which works for \(m = 2\).

More precisely, it's type A3 with \(x_1=8, y_1=9, z_1=8\). The carry from that column is \(c_1=(8+9+8)/10=25/10=2\). Applying step 2 gets us \(x_2=2, y_2=9, z_2=7\), with a carry of \(c_2=(2+9+7+2)/10=20/10=2\). The loop designed into Algorithm I doesn't get to run at all with \(m=2\), so we head straight to the final pre-correction step setting \(x_3=0\). That is, our palindromes start out as 82028, 9999, and 878.

Next, the correction step, which is where it gets spicy. \(c_2=2\) leads us into case I.3, which makes some arguments:

The proof Wrote:In this case, we have that \(y_m \neq 0\) (otherwise \(c_m \neq 2\)). Further, if \(z_m \neq g-1\), then the only possibility to have \(c_m = 2\) is that \(z_m = g-2\), \(y_m = g-1\), \(x_m = 1\) and \(c_{m-1} = 2\), but that gives \(\delta_{m-1} = 0\), which is not allowed. Thus, \(z_m = g - 1\) and we make the following adjustment:

The most obvious problem here is the final conclusion: \(z_m\) is not \(g-1\) (that would be 9 in decimal mode), but 7 instead.
But the problems really start earlier than that, because unlike with greater \(m\), we have the possibility to see an \(x_m\) greater than \(1\) thanks to the algorithm's main loop not running even once. Indeed, we have \(x_2 = 2\). Additionally, we do have \(\delta_{m-1}=\delta_1=0\), despite the proof saying that is "not allowed" (I don't understand enough of it to know where that is coming from; maybe that conclusion is also invalidated by \(x_2=2\) or its root cause, \(m=2\)).

The bottom line is, I don't know how to fix it. Blindly applying the proof's correction of setting \(x_3\) to \(1\), decrementing \(y_2\), and setting \(z_2\) to \(0\) is how you receive the result you did, so the implementation appears to behave as the (buggy) specification says. For this particular number, decrementing \(y_2\) by an additional \(2\) and incrementing \(x_3\) by the same does yield a valid sum (the \(2\) comes from by how much \(z_2\) was off compared to the expected \(g-1\)), but I can't tell if such a fix breaks on another number without a deeper understanding of the math.

[Gerald H]

A problem with ALGO3:

For input

1128097

PALIN returns

1
1020201
99199
7997

Sum is wrong, 1 is superfluous.

[Gerald H]

Well, 3298, this site

http://www.rnta.eu/cgi-bin/three_palindromes/pal3.py

claims to use the algorithms from the proof & gives a correct answer.

[2old2randr]

I have fixed all three problems reported by Gerald.

1. For 3000: there was a missing CASE clause in SML4 which caused the relevant code to never be executed (it got subsumed by a nested CASE). Fixed and PALIN now returns (2992, 7, 1).
2. For 1128097: There were a couple of typos in ALGO3 one of which was a missing "AND" in an IF...THEN causing the extraneous value on the stack. Fixed and PALIN now returns (1020201, 99899, 7997).
3. For 92805: As 3298 correctly pointed out, this is a mistake in the paper. It is also fixed and PALIN now returns (82028, 9889, 888).

The updated code is attached (I have also removed the attachments to previous posts to avoid confusion).

For anyone following the thread: the paper linked to in previous posts (on Arxiv) seems to be a preprint that is not the same as the final published paper. It has a bug in Algorithm 1: in the adjustment step when cm==2, it claims that zm==9 (in base 10). However, as in the case of the number 92805, this is demonstrably false. The final published paper corrects this adjustment step and adds the correction for the case when zm != 9.

The final (corrected) paper can be found at this link. I have not had time to see if there are any other differences between the preprint and the final paper.

Sudhir

Attachment removed since there was a bug in SML5 - updated code attached to post #71

[3298]

Unfortunately, that version of the paper looks identical to version 1 on arXiv (minus an index and clickable links), so the release history seems to be the other way around. Version 1 avoids that particular problem by having an additional case to handle it (apparently there was a flawed attempt to improve it by eliminating unnecessary cases for version 2), but there are a couple other changes, from inconsequential things like some different phrasing across the first three pages and a bunch of spelling corrections throughout the paper, to algorithm-changing things like an adjustment to the limit between types A6 and B2, or making an argument that case II.2.ii.b is unnecessary (thus simplifying the conditions for II.2.ii.a), or splitting up II.2.ii.c because another argument wasn't valid for 7-digit numbers of types A5 and A6 (which incidentally are treated as if they were a digit shorter, making them fall into the small-numbers range we seem to be having trouble with - and now I'm curious whether I should apply the small-number prohibition on Algorithm V to them or not, because the large-number section doesn't mention that).
There's also the elimination of cases IV.2.ii.c (leading to IV.2.ii.d getting renamed and condition-simplified) and IV.3.ii (that leaves IV.3.i as all that's left of IV.3), the addition of IV.4.iii with two subcases .a and .b (and two unnamed sub-subcases each), the elimination of IV.5.iii.e, and a redo of IV.5.v.b and IV.5.v.c.
Algorithm V was rephrased to account for the fact that decrementing both middle digits by 1 can lead to the other one becoming 0, re-triggering the condition for Algorithm V. (It should have been also adjusted to account for the newly emerged difference between the type A5/B1 and A6/B2 cutoffs, but that's a minor oversight.)
In 4-digit numbers, cases iii.a with \(\delta_3 \neq 1\) and iii.b were redone. In 5-digit numbers, cases vii, viii, and viii (yes, version 1 has two named viii here...) were replaced by a single case called vii. 6-digit numbers with \(\delta_5 \neq 1\) get their case iii replaced by a paragraph arguing that this case isn't actually possible, and the following cases iv and v consequently get their names decremented to iii and iv.
6-digit numbers with \(\delta_5=1\) see a change in the justification for case ii (and some missing definitions for \(z_1\), \(c_1\), \(z_2\), and \(c_2\), though similar problems with subsequent cases remain - you can easily fill in those gaps at least). Version 2 also adds case iii.d and corrects the mistake that there were again two identically named cases - the second iii and following iv obviously get renamed to iv and v. The (former) second iii gets split up into sub-cases .a and .b (the old content is found in .a, whereas .b is all-new). All sub-cases of old iv.c (new name: v.c) received a correction in their final digit. There are also fresh sub-cases v.d and v.e, which seem to be written by another author given the very different style (which I find much harder to comprehend) - the new iv.b belongs into that group too.

I hope I caught all the actually important changes here... there was much alt-tabbing back and forth to visually identify changed areas, but I can't guarantee that I did catch all of them.

[Gerald H]

Good work, 2old2randr, but for input

18047

the programme returns

18081
-34
0

[pier4r]

Just an heads up to 2old2randr.

Attachments on this forum are limited (in size used per user). So if you in the future uploads more content, the PALIN.zip will disappear. Since I personally find a pity when contributions are lost, I leave a couple of suggestions. You could:

a: write the program here as a code block

Code:


like this

b: use the awesome https://www.hpcalc.org/ and upload your program there so that is available for future reference. (here the submission form: https://www.hpcalc.org/contribute.php )

Otherwise someone may need to code it again in the future, if the attachment is not there anymore.

[2old2randr]

(03-12-2023 11:45 AM)pier4r Wrote:  Just an heads up to 2old2randr.

Thank you, pier4r. At the moment, with Gerald H identifying scores of bugs, it is too unstable to submit to hpcalc.org - I will do so once the bug reports die down

However, I do have the source available on GitHub (with slightly different filenames) at this link.

Sudhir

[Gerald H]

I believe the problems now only reside in the small numbers - the major task of the 5 algorithms appears faultless.

Well done!

The B7 branch is redundant, only reason for keeping it is to commemorate the proof.

[2old2randr]

(03-13-2023 04:05 AM)Gerald H Wrote:  I believe the problems now only reside in the small numbers - the major task of the 5 algorithms appears faultless.

Well done!

Thank you, Gerald. The code in SML5 was a mess because of my effort to have a single CASE statement to handle all cases. I have rewritten it and verified that the results are correct for 10000-19999.

The updated code is attached. (edit: attachment removed - bug fixed version in a later post)

Sudhir

[Gerald H]

You may, 2old2randr, think that something happened to me, not posting today’s accumulated errors.

But no, I’m still around &, amongst others I tested the programme on this 107 digit input

84079603496574400839385654909302841671928775176508136511539400366510882879682345​079140714467212750577420292

Which returned

80111000101110001010101000011001000011110101110010001010001001110101111000010011​000010101010001110100011108

38630974672524312933094699210640718707118450149936560065639941054811707817046012​99649033921342527647903683

10550592821196853597518497723776979010682905150447949497440515092860109796773277​9481579535869112829505501

Which after double checking proved correct!

In short I believe the programmes now give only correct answers with no superfluous stack objects.

Better than my rather tame dreams!

Could you please say when you first became interested in this problem & how much time you devoted to producing the programmes?

[2old2randr]

Thanks, Gerald.

I only got interested in the problem after reading the initial discussion on this thread. Being new to RPL and the 50g, I thought it would be an interesting exercise to translate a non-trivial and (relatively) clear set of algorithms to RPL as a way to improve my familiarity with writing programs for the 50g.

I think the initial implementation took a couple of hours a day over the course of a week. Most of the time was spent in importing the code (typed in a text editor on my Mac) to the calculator. Because there is no help from the editor with respect to the syntax, in some cases, it took me a while to find the cause of a syntax error and fix it. Initially, I had to resort to deleting blocks (in the calculator editor) to check where the error was contained. Only later did I find a quicker way to locate the position of the syntax error. All my testing was done on the calculator itself. I tried to find numbers that exercised different cases in the algorithms but couldn't in some cases - as you've pointed out on several occasions.

Most of the errors (apart from a few e.g., SML5) were due to the programs being syntactically valid but containing typos of various kinds. This is down to my not having an editing environment on the Mac that can help. For example, one of the errors was due to an AND being misplaced - instead of 'a 1 < b 0 == AND THEN', I had typed 'a 1 < b 0 AND == THEN'. This does not leave extraneous values on the stack but the wrong branch is taken in some cases ...

Anyhow, I was determined to see this through once I started on it. This is why I added SML2-SML6 once the main algorithms seemed ok.

Thank you for setting up the challenge. I quite enjoyed it and I think I'm now quite used to the computer -> 50g environment I am using. I found I am making fewer syntax errors now as compared to when I started and the bugs now are mostly genuine errors in logic rather than typos as they used to be earlier.

Sudhir

[Gerald H]

Quite a wonderful performance.

As to problems with syntax, here a more streamlined version of ALGO1:

Code:

CKSUM: # 85FAh

SIZE: 1673.

« → d p1 p2 p3
 « p1 SIZE DUP
ZEROLST OVER 2 / IP
ROT p2 SIZE p3 SIZE
p1 1 GET p2 1 GET
p3 1 GET 0 0 0 → c
m l1 l2 l3 x y z d1
d2 ci
    « x y + z + 10
/ IP 'ci' STO c 1
ci PUT 'c' STO d 2
m * 1 - GET 'd1'
STO d 2 m * GET
'd2' STO
      IF z d1 <
      THEN d2 y -
      ELSE d2 y - 1
-
      END 10 MOD
'x' STO p1 2 x PUT
l1 1 - x PUT 'p1'
STO d1 z - 1 - 10
MOD 'y' STO p2 2 y
PUT l2 1 - y PUT
'p2' STO d 2 GET x
- y - ci - 10 MOD
'z' STO p3 2 z PUT
l3 1 - z PUT 'p3'
STO x y + z + ci +
d 2 GET - 10 / IP
'ci' STO c 2 ci PUT
'c' STO
      IF m 3 >=
      THEN 3 m
        FOR i d 2 m
* i - 1 + GET 'd1'
STO d i GET 'd2'
STO z d1 < 'x' STO
p1 i x PUT l1 i - 1
+ x PUT 'p1' STO d1
z - 1 - 10 MOD 'y'
STO p2 i y PUT l2 i
- 1 + y PUT 'p2'
STO d2 x - y - ci -
10 MOD 'z' STO p3 i
z PUT l3 i - 1 + z
PUT 'p3' STO x y +
z + ci + d2 - 10 /
IP 'ci' STO c i ci
PUT 'c' STO
        NEXT
      END p1 m 1 +
0 PUT 'p1' STO
      IF c m GET 0
==
      THEN p1 m 1 +
1 PUT 'p1' STO
      ELSE
        IF c m GET
2 ==
        THEN
          IF p3 m
GET 9 ==
          THEN p1 m
1 + 1 PUT 'p1' STO
p2 m GET 1 - 'y'
STO p2 m 1 + y PUT
m y PUT 'p2' STO p3
m 0 PUT 'p3' STO
          ELSE p2 m
GET 1 - 'y' STO p2
m 1 + y PUT m y PUT
'p2' STO p3 m GET 1
+ 'z' STO p3 m z
PUT 'p3' STO
          END
        END
      END p1 NL→I
p2 NL→I p3 NL→I
    »
  »
»

[2old2randr]

Thank you for that - I will try and do the same for the entire set. I guess the run time will be improved as well by eliminating the repeated recall/store combinations.

Sudhir

[Gerald H]

In ALGO5, near the end, there is a section marked

Use B2 setup

Has anyone found a number that requires that path?

[Gerald H]

Some statistics in seconds for run-time on input of 6-digit integers to a version of peruna's programme optimized for a maximum of 6 digits for 1,000 random inputs:

Total 255.9
Mean 0.25
SDev 0.51
Max 4.1
Min 0.06

& the same figures for 2old2randr's programme, again slightly optimised:

Total 1,112.9
Mean 1.1
SDev 0.13
Max 2
Min 0.46

[Albert Chan]

peruna's code does greedy search, picking the biggest palindrome for x first.
For n of 6 or 7 diigits, first (n-x) are under 3 digits.

Example: 3141592 - 3141413 = 179 = 171 + 8

Out of 1000 possibiilties, only 8*2 = 16 are unable to be represented by 2 palindromes.
This may explain why it is fast for small integer cases.

21, 32, 43, 54, 65, 76, 87, 98
201, 302, 403, 504, 605, 706, 807, 908

[Gerald H]

Here a suggestion for a more economical "PALIN" programme in 2old2randr's submission:

Code:

CKSUM: # 29625d

SIZE: 421.5

« DUP I→NL DUP SIZE
DUP 1. ==
  CASE
    THEN DROP2 0 0
    END DUP 7. <
    THEN "SML" SWAP
R→I + OBJ→
    END OVER NTYPE
→ num d n type
special d p1 p2 p3
    «
      CASE special
        THEN num p1
ALGO5
        END d p1 p2
p3 { "A1" "A2" "A3"
"A4" } type POS n 2
MOD AND { "A5" "A6"
} type POS n 2 MOD
NOT AND OR
        THEN ALGO1
        END type
HEAD "A" ==
        THEN ALGO2
        END n 2 MOD
        THEN ALGO3
        END ALGO4
      END
    »
  END
»

[Gerald H]

Today, the 26th day of the competition, we have two complete solutions, from peruna & 2old2randr.

peruna's solution is theoretically easily understandable, as are the programmes, a paradigm of economy & carefully optimised for UserRPL.
However, for large numbers an inordinately large time is required.

2old2randr's solution is a baroque masterpiece, fully based on the proof, a document requiring commitment to get to the end, producing programmes opulently large & full of bi-, tri- & quadrifurcations (& some larger ones), the development of which was kindly displayed in this thread, allowing members to assist & critique.
Larger numbers are dealt with in respectably short times.

Which should win a prize?

No time limit was set for the competition, so perhaps other members will contribute more solutions, accordingly competition stays open for another week.

Indeed, 3298 has hinted that he will produce a solution - another approach to the problem would be interesting.