How to check whether a integer of type mpz_t is a palindrome
Matevž Markovič
ivwcorporation.matevz at gmail.com
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
palindrome...)
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
questions:
(*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
reversed)
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,
Matevž
More information about the gmp-discuss
mailing list