[seqfan] Re: Palindome reciprocal sums

[Joseph S. Myers]

On Sat, 21 Jun 2014, Hans Havermann wrote:

> My attempt at the sum of the reciprocals of binary palindromes yields 2.3787957...
>
> Is anyone else bothered by the (large) number of terms in 
> http://oeis.org/A118031 ?

Yes.  My calculation disagrees with the last five terms given there.  To 
500 digits after the decimal point, I get:

3.37028325949737332049215729850553112307145777945277849133506892598251\
9760349476758970301121926978089863235053242140316891712674793367414783\
0127937467183247967252750087722634827550979318225637556877944404376796\
8474931513133736472955312716374810549779573612056823324844606497743158\
0837857622278037038294037028076954617094867147766671370440750983774732\
7681658124294157278347595895815147012803762301460078753895374219171398\
6878234744254964506003649625696575961977519973554108084376954978206279\
542634832384

(I'm running the calculation for 1000 digits after the point now.)

I believe this can be approximated in polynomial (quartic?) time in the 
number of digits' accuracy required.  Suppose you want to compute the sum 
of the reciprocals of the d-digit palindromes (it's easy to get an upper 
bound on the sum for all those with more than a certain number of digits), 
for d > 4.  Express such a palindrome in the form A+B, where A has the 
first and last two digits of the original palindrome with all the digits 
in between replaced by 0 (and so is itself a d-digit palindrome, with 
leading digit not 0), and B has all the digits in the middle (and can be 
imagined as a d-digit palindrome with initial and final 00).  Then we want 
the sum of values 1/(A+B) for A and B numbers of that form, and 1/(A+B) = 
(1/A)(1/(1 + B/A)) = (1/A)(1 - B/A + B^2/A^2 - B^3/A^3 + ...) since B/A < 
1/10.  But rearranging, this splits into sums involving just the A, and 
sums involving just the B: (sum 1/A)(sum 1) - (sum 1/A^2)(sum B) + (sum 
1/A^3)(sum B^2).  Each sum involving just the A contains just 90 terms, 
and you can compute the sum of nth powers of k-digit palindromes (leading 
0s allowed) - the B terms - using binomial expansion and the sums for 
k-2-digit palindromes for all powers up to n.  And you can easily enough 
produce a bound on the error from truncating the series.

Doing all this with interval arithmetic produced the number given above 
(that disagrees with the last five terms of A118031).  For base 2, to 100 
digits (convergence is slower; you could trade off between the speed of 
different parts of the calculation by using more than two digits in A, but 
I haven't implemented that), I get

2.3787957075413610023353016844282506323532800844658545591838787210323420167865151408468622006356164037

and again I'm running a longer computation.

Perhaps someone should confirm some of this before corrections / 
extensions / b-files are added.

-- 
Joseph S. Myers
jsm at polyomino.org.uk