How to check whether a integer of type mpz_t is a palindrome
Matevž Markovič
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
(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ž
More information about the gmp-discuss
mailing list