Potential error in the paper: “Every positive integer is the sum of three palindromes”

Maybe some of you know of the nifty trick that every number can be split into three palindromic numbers that add up to said number. As described in the article right here, this works so far so good, but looking further down into the paper you see five algorithms described to compute the individual palindromes: Algorithm V seems to have an error in its algorithm description (page 27), otherwise I can't explain the discrepancy. It goes as follows:

The associated palindrome p1' of n' has 2*m-1 digits. This is only possible when n is of
the form n = 104... and n' = 103... In this special situation, we consider n' as of type
B1 or B2 and apply Algorithm IV to n' (instead of Algorithm I).


To cut this question short, you can look up all surrounding information in the article.

Take, for example, the number $$n = 10409302$$ in base 10. This means that $$l = 8$$ and $$m = \lfloor \frac{l}{2} \rfloor = \lfloor \frac{8}{2} \rfloor = 4$$.

Algorithm V applies since $$l$$ is even and either $$\delta_m = 0$$ (true) or $$\delta_{m-1} = 0$$ (false).

The next step is to substract $$s$$ (or $$2s$$) from the number above, so the condition above yields false for both statements: $$s = 10^m + 10^{m-1}$$. This gives $$n' = n - s = 10398302$$ for this example.

The only problem now is to match this new number $$n'$$ to a certain case mentioned at the beginning of the paper... Well, the case according to the classification is A5, neither B1 or B2 - clearly a contradiction to the description of the algorithm.

Sorry if I am bothering you guys with this problem, this is just the last part missing from my recreation of the algorithm.

This is not a contradiction. The instruction

In this special situation, we consider $$n'$$ as of type B1 or B2 and apply Algorithm IV to $$n'$$ (instead of Algorithm I)

tells you to ignore the classification of $$n' = 10398302$$ (which is A5 in this case) and pretend it is B1 or B2 instead. In this case, we pretend it is B1 (corresponding to A5) rather than B2 (corresponding to A6).

So we apply Algorithm IV to write $$n'= 10398302$$ as the sum of palindromes $$10011001+296692+90609$$, and then increase the middle digits of $$p_1$$ to write $$n = 10409302$$ as the sum of palindromes $$10022001 + 296692 + 90609$$.

Essentially, what's happening is that numbers of the form $$103\dots$$ with an even number of digits can be handled by either Algorithm I or Algorithm IV; both work. Usually, we classify them as A5/A6 and apply Algorithm I. This works perfectly, but doesn't suit our purposes because then $$p_1$$ ends up with an odd number of digits, and we can't modify it as we did above. So in this case, we reclassify $$n'$$ as B1/B2 and apply Algorithm IV, getting a palindrome $$p_1$$ with an even number of digits whose two middle digits can be incremented.

• Ah, I already suspected that. I've fiddled around with some ways to modify this algorithm, but I didn't straight up assume the cases yet. The example (and my code) seems to work now. I wonder if there is a way to work out which one to choose out of the two cases B1 and B2, because while B1 works just fine for the example, B2 results in n + 2. Weird right? Anyway, thank you for explaining! – TheOutrageousZ Jan 26 at 12:28
• EDIT: Aaaahh sorry! I reread your comment, I'm dumb, I know how to deal with it now. Also, I clearly edited my comment under 5 minutes but it didn't let me change it... weird. – TheOutrageousZ Jan 26 at 12:42
• In general, the A1/A2, A3/A4, A5/A6, B1/B2, and B6/B7 distinction is that the first subtype works 90% of the time, and the second subtype is an alternative for when the first subtype would ask to put a $0$ as the first digit of $p_3$. This doesn't change when we do the ignore-the-classification thing. – Misha Lavrov Jan 26 at 15:08