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

[Matevž Markovič]

Hy all! I finally completed the research.

For my palindromicity test I utilized following ideas:

Prior to the trivial linear check, following tests should be conducted:
Let AK := first K digits in base d,  ALastK := last K digits in base d

--> Digit root test
on K*2 digits (K at the start of the number and K at the end of the
number), using the observation that for every base d, (AK - ALastK) == 0
(mod d-1)

--> Partial palindromicity test
on K*2 digits (K at the start of the number and K at the end of the number),
where AK ?= ALastK_reversed

--> Test for palindromes with even number of digits, is A ?= 0 (mod d+1)

--> Does d divide A? If so, A is not palindromic

Problem: what K is appropriate?

I decided in favor of K which is obtained by rounding number.length/10 to
the nearest smaller K in the K_array.
K_array[] =
{1,9,19,38,77,154,308,616,1233,2466,4932,9864,19728,39456,78913,157826,315652,631305}

where 10^19 < 2^64 , 10^38 < 2^128, ...

Of course, other values of K should be used for other bases.

________________________________________________________________________________________________________________________

I would like to thank you all one last time for your ideas and your help.
(and also for your informal proofs - Pedro Gimeno)

Yours,

Matevž