How to check whether a integer of type mpz_t is a palindrome
ivwcorporation.matevz at gmail.com
Wed Feb 29 18:03:45 CET 2012
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
--> 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.
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)
More information about the gmp-discuss