This site is supported by donations to The OEIS Foundation.
User talk:M. F. Hasler/Work in progress/Sum of palindromes
Contents
sumOfPal() applied to A109326
I wrote a function sumOfPal(N,m) which determines whether N is a sum of m palindromes, but for the moment being it uses a very simple algorithm which turns out to be too inefficient beyond 10^20 or so, see below. I did not yet have time to work on implementation of the more efficient algorithm I have in mind for the decomposition N=P1+P2+P3, which should use the final digits of S=N-P1 to guide the search or refute P1 as possible largest term. (In the next section I will put some more details regarding this.)
Let me just share some results concerning my function sumOfPal(N,m) which on success returns N-P, where P is the largest palindrome such that N-P is the sum of m-1 palindromes, if such P exist.
I tested it for the numbers
- A109326 = [1, 10, 21, 1022, 101023, 1000101024, 100000001000101025, ...]
for which the greedy decomposition requires an increasing number of terms.
It yields :
SumOfPal(1022,3) = 23 = 22+1, 1022-23 = 999 SumOfPal(101023,3) = 1022 = 33+989, 101023 - 1022 = 100001 sumOfPal(1000101024,3) = 101023 = 10101+22, 1000101024-101023 = 1000000001 sumOfPal(100000001000101025,3) = 1000101024 = 5252525+994848499
For N = A109326(4..7), we observe the pattern
All these results including A109326(7)~10^17 are returned instantly, which is understandable, since 1+10^(...) is the second next smaller palindrome precpal(precpal( N )-1), and even the less trivial secondary decompositions 33+989 and 5252525+994848499 involve a "nearly next smallest palindrome" (with 99484 being only about 500 steps from 100001).
Unfortunately, for my conjectured value of
my program takes too much time to return a result (I interrupted after half a minute).
Anyway, it is clear that the pattern observed for N = A109326(4..7) will not continue forever because A109326(n-1) will not always be the sum of two palindromes even if it would turn out that this is still the case for n=8, A109326(7).
Towards a more efficient algorithm
Here some details concerning my ideas for a more efficient algorithm. The idea is:
- If N is a palindrome, we have finished and found the optimal decomposition (sum of only one palindrome).
- Else we check whether N is the sum of two palindromes.
- This is the part which we will optimize usig the ideas given below, since this routine is also required later on.
- We will call sum2pal(N) the function which returns the largest P1 such that N - P1 is again a palindrome, or 0 if no such P1 exists.
- Note that P1 is never smaller than N/2. Thus it also has the same number of digits than N, or at worst one less.
- Details on how we build an efficient algorithm for this will be given further below.
- If sum2pal(N) = 0, i.e., we find that N is not the sum of two palindromes, then we wish to find the largest palindrome P1 such that S = N - P1 is the sum of two palindromes.
- The greedy algorithm to do so is to start with P1 = precpal(N), and while sum2pal(N-P1) = 0, go to the next smaller P1 ← precpal(P1-1).
- We can define the function sumOfPal(N) which returns
- N iff N is a palindrome,
- sum2pal(N) iff N is the sum of two palindromes,
- S = N - P1 where P1 is the largest palindrome such that sum2pal(S) > 0. Such a P1 must exist if the "3 palindrome conjecture" is true. Else P1 should be such that S is the sum of the smallest possible number of palindromes.
- Thus, from merely looking at the result, we can at once know whether N is the sum of 1, 2 or 3 (or more) palindromes.
An algorithm for sum2pal
Now let us turn to an algorithm for sum2pal.
- One greedy algorithm for checking whether N = P1 + P2 (sum of two palindromes) is to start with P1 = precpal(N), and then going repeatedly to the next smaller palindrome, P1 ← precpal(P1-1), until P2 = N - P1 is also a palindrome.
- One can hope that most of the first half of digits of P1 coincide with those of N. Thus, also the final digits of P1 coincide with the first digits of N. This allows to know the final digits of N - P1 which are, more or less(*), given as difference
- (final digits of N) - (final digits of P1) = (final digits of N) - (first digits of P1, reversed)
- = (final digits of N) - (first digits of N, reversed)
- This yields the final digits of P2 = N - P1, which should be a palindrome, and thus its final digits are the same as its initial digits. Thus, the initial digits of P2 are determined by N only, without knowning or testing P1!
- ((*) up to a possible "underflow"/carry, see the example)
- This allows a much more efficient search for P1, compared to the greedy algorithm mentioned above. Namely, the "known" initial digits of P2 must "match" the difference N - P1.
Example:
If N = 314159.....950288 and P1 = 314159.....951413 then N - P1 = ...998875 (calculated as you do by hand, from right to left).
Therefore, P2 = 578899...998875, and we can search P1 of the form precpal(N - 10^k*5.78899...).