How to check whether a integer of type mpz_t is a palindrome

[Pedro Gimeno]

Matevž Markovič wrote:

>    2. Digit-roots test (Pedro`s proposal)
>    3. Check K digits (Torbjorn`s proposal) , K = 20

I guess you've noticed that these two can share some intermediate
results, as the operation to extract the first and last digits is common
to both methods. As noted earlier, K = 19 can yield better speed in a
32-bit machine than K = 20 because it always fits one single limb.

>    1. For even n, are all palindromes in any base d divisible by 11? (I
>    know that for d=10 this is true, I ran some quick tests and it seemed to be
>    true for d=8 and d=16, though I cannot be sure)

If by 11 you mean d+1 then yes. I have an informal proof that can
probably be formalized. A palindrome in base d with even n is a linear
combination of the series (in base d) 11, 1001, 100001, 10000001, ... ,
d^{2*i+1}+1 with integer coefficients. For example:

21544512 = 4000 * 11 + 500 * 1001 + 10 * 100001 + 2 * 1000001

11 in base d is trivially multiple of d+1. My informal proof shows that
1001, 100001, 10000001, ... (all in base d) are all multiples of d+1. It
is based on the fact that 1100, 110000, 11000000, ... (in base d) are
evidently multiples of d+1, and their differences with the above are 99,
9999, 999999, ... (where 9 should be replaced with d-1 for arbitrary d)
which are also multiples of d+1 because they equal 11*9*(1 + 100 + 10000
+ ...) in decimal; (d+1)*(d-1)*(1+d^2+d^4+...) for arbitrary d.

>    2. Is Pedro`s test true in every base d? [Is it true for every base d,
>    that (AK - ALastK) % (d-1) == 0]

Yes. See http://en.wikipedia.org/wiki/Digital_root#Congruence_formula
for proof.