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

Matevž Markovič ivwcorporation.matevz at
Wed Feb 15 14:41:08 CET 2012

Hi all,
I apologize for such a late reply...

In the meantime I wrote a program which utilizes the algorithm Torbjorn
proposed. Great speedup was achieved, but unfortunately, this is not enough.
@Pedro: Today I focused on your way of implementing the sieve. I was
thinking about a multi-level sieve:

   1. General tests (number A divisible by 10 is never a palindrome, when
   number of digits N is even & A%11 != 0 & d=10 number is never a
   2. Digit-roots test (Pedro`s proposal)
   3. Check K digits (Torbjorn`s proposal) , K = 20
   4. Full test (trivial, time-consuming)

In order to speed-up the tests, does anybody know the answers to following

(*n* := number of digits in the number *A*, *d* := base, *AK* := first K
digits of number A in base d, *ALastK* := last K digits of number A

   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)
   2. Is Pedro`s test true in every base d? [Is it true for every base d,
   that (AK - ALastK) % (d-1) == 0]
   3. Is the most effective way of dealing with the mpz.sizeinbase(A,d)
   problem whether result is accurate or by 1 too big to check whether
   A/(d^n)==0, then the number n is actually n = n-1?

Thank you,


More information about the gmp-discuss mailing list