User:M. F. Hasler/Work in progress/Sum of palindromes

We consider sequences related to the representation of numbers as sum of palindromes, and study in particular the conjecture (proved in 2016) that any n can be written a sum of at most 3 palindromes.

Related sequences

Elementary sequences

• A002113 : the palindromes in base 10
• A261423 = precpal() = palindromic floor function = largest palindrome <= n
• A262038 = nextpal() = palindromic ceiling function = least palindrome >= n
• A262039 & A262040 = nearest palindrome; in case of a tie choose the larger / smaller one.
• A262037 = replace 2nd half of digits of n by the first half in reversed order
• A261424 = n - precpal(n) = Difference between n and the largest palindrome <= n.

Other related sequences

The following sequences, related to the decomposition of n as sum of palindromes, are based on the above and somhow more complex, although the "greedy decomposition" is just iteration of the above A261424 = n - precpal(n).

• A261675 = Minimal number of palindromes that add to n
• A088601 = Number of palindromes in n's decomposition via the greedy algorithm (i.e., # iterations of A261424 to reach zero)
• A109326 = Smallest positive number that requires n steps to be represented as a sum of palindromes using the greedy algorithm.
• A261132, A261422: Ways to write n as a sum of three palindromes.
• A035137 = Numbers that are not the sum of two palindromes: 21, 32, 43, 54, 65, 76, 87, 98, 201, 1031, ...
• A104444 = Numbers that are not the difference of two palindromes: 1020, 1029, 1031, 1038, 1041, 1047, 1051, 1061, ...
• A262087 = Largest palindrome p such that n - p is again a palindrome, or 0 if no such P exists. This is a very simple variant of the following:
• sumOfPal() = If n can be written as sum of m but not of m-1 palindromes, a(n) = N-P1 where P1 is the largest palindrome such that n-P1 is the sum of m-1 palindromes.

This is also a variant of A261424, where precpal(n) is replaced by "largest palindrome <= n such that the difference can be written as sum of a minimal number of palindromes".

Actually it happens that this sequence coincides up to n=1099 with the much simpler A261424 = n - precpal(n). [check: see comment in A261424]

Palindromic order

N. J. A. Sloane has proposed the following "palindromic order", based on the disproved

Conjecture: [John Hoffman] All sufficiently large N are the sum of three palindromes, the largest of which is precpal(N) or prevpal(prevpal(N)).

cited by Erich Friedman on Math Magic 06/99:

• A002113 = Numbers of order 1 = palindromes
• A261907 = Numbers of order 2 = non-palindromes which are sum of two palindromes: A261906 \ A002113
• A261910 = Numbers of order 3 = numbers which are not sum of two palindromes, but such that N-prevpal(N) is of order 2
• A261911 = Numbers of order 4 = numbers which are not of order < 4, but such that N-prevpal(prevpal(N)) is of order 2.
• A261912 = Numbers of order 5 = numbers not of order < 5.
• A261913 = Palindromic order of n.

and related sequences:

• A261906 = Numbers which are the sum of two nonzero palindromes
• A260255 = Numbers that can be written as the sum of two nonnegative palindromes in base 10.

Algorithms for partitioning as sum of palindromes

Here we only consider algorithms that aim at finding a decomposition using a small number of palindromes, not for example n = 1+1+...+1 = n*1 which is of course also a partition into palindromes. The goal is of course to find a sum of palindromes with the smallest possible number of terms.

The greedy algorithm

The simplest nontrivial algorithm consists in subtracting successively the largest palindrome not exceeding n, i.e., iteration of A261424. Since the difference has at least one digit less (more precisely, at most floor(L/2) digits), it is certain that this algorithm will terminate and yield a decomposition of n into at most ceiling(log_2(n)+1) terms. Sequence A088601 yields the number of terms

The less-than-3 algorithm

In their 2016 preprint arXiv:1602.06208, Cilleruelo et al. prove that any number can be written as sum of at most 3 palindromes, in any base >= 5. The proof is algorithmic, based on the distinction of 5 "types" of numbers. (... to be written ...)

The less-than-49 algorithm

In their paper [...], the authors prove that any number can be written as sum of at most 49 palindromes. The proof is based on the following idea: (... to be written ...)

An improved greedy algorithm

The sumOfPal(N,m) function checks whether N is the sum of at most m palindromes.

The strategy is, for m>2, to subtract a large palindrome P, close to prevpal(N) (= largest palindrome < N), and to apply "recursively" sumOfPal(N-P,m-1). Until this is a success, iterate on P the "next smaller palindrome" function or something better, based on optimizations developed further below.

For m <= 2, we will use an efficient algorithm to decompose N into a sum of 2 palindromes, P and N-P ≤ P. We define the function sum2pal(N) to yield the smallest such N-P.

The simplest brute force algorithm to do so is again to start with P = prevpal(N) and iterate the prevpal() function.

But we can do much better: Indeed, if P >> N-P, then the first digits of P are the same as those of N, and the last digits of P are the same, reversed.

Therefore we get the last digits of the difference N-P from calculating N - prevpal(N), where prevpal(N) has been chosen rather than reverse(N) to ensure there is no "over/underflow" which would yield a negative difference.

But since we want N-P to be a palindrome, its last digits also determine first digits.

Knowing these digits greatly reduces the number of required tests: we only have to fill in a certain number of "middle digits" in the candidate D for difference N-P.

Example

Decompose n = 3141592653589 as n = p + d, p >> d.

Since d is much smaller, p is roughly equal to n, and palindromic, thus p = 314...413. Therefore, d = n - p = 314...589 - 314...413 = ...176. To make it simple and unambiguous, we calculate : n - precpal(n) = 702176.

Therefore, although we don't know its number of digits, we know that d = 671...176.

So, instead of scanning all palindromes smaller than n (which are obtained by repeatedly subtracting 10^6 (where 6 = floor((length of n)/2)) and completing the second half of digits accordingly), we know that p ~ n - 6.71*10^k with k=6,7,8....

We do not have to consider palindromes p for which the difference n-p does not start with digits 67.... The only differences to check are:

1. 3141592653589 - 6712176   (d cannot have less than half the length of n, unless p = prevpal(n), largest palindrome < n).
2. 3141592653589 - 67122176   (here n/d > 10^4 so we know the first 4 digits of d)
3. 3141592653589 - 671xyx176   (here n/d < 1000, therefore the fourth digit of d is not known any more).

We would finally find p = 3140921290413 with d = 671363176.

We see that this is particularly efficient when d has about half as many digits as n, and becomes more expensive when the number of digits of d approaches the number of digits of n. But the improvement w.r.t. the brute-force iteration of prevpal() is still very important, as shows the present example: we had to check only less than 40 d-values (xy = 00..36), which is much less than all ~ 700 palindromes between prevpal(n) and p = 3140921290413.

In other bases

to be written.

About this page

Revision history

• initial version created. — MFH 20:40, 10 September 2015 (UTC)
• added section on palindromic order. — MFH 03:34, 14 September 2015 (UTC)

Cite this page as

M. F. Hasler, User:M._F._Hasler/Work_in_progress/Sum_of_palindromes. — From the On-Line Encyclopedia of Integer Sequences® (OEIS®) wiki.Available at https://oeis.org/wiki/User:M._F._Hasler/Work_in_progress/Sum_of_palindromes