## generate palindromes numbers...(Usaco problem)

Let's talk about algorithms!

Moderator: Board moderators

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

### generate palindromes numbers...(Usaco problem)

I need to know how I can generate palindromes number in a certain range.
For example, in the input says 7 100000000
and I have to know all palindromes numbers between 7 100000000...
then I must check if the palindromes are primes so I don't need to check the numbers terminated in 2 and the numbers with a pair digits because all the palindromes that have a pair number of digits are multiple of 11 so they are not primes.

well...sorry for my bad english and if someone could help I would appreciate.
thanks
Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

### Re:

I haven't gotten to this problem yet in USACO, but after reading your message I think I see how to do it...

 Doh I'm dumb..yes I have done this problem. : ) I completely forgot about it, too long ago heh. For some reason when I did the problem I didn't realize the even-number of digits thing though...trying both the even/odd didn't exceed time, so it was all good. Btw, do you see why about the even digit palindromes can't be prime (unless 11)? 10 is -1 mod 11, and we write our numbers in base 10. From that it follows that if you have some number a_1a_2a_3...a_n(where those are the digits), the number is divisible by 11 if and only if a_1 - a_2 + a_3 - a_4 + ... + (-1)^{n+1}*a_n is divisible by 11. For palindromes, a_i = a_{n-i+1}. So the sum gives you 0 for an even-length palindrome, which is divisible by 11.[/Edit]

-Note that any palindrome with an even number of digits is divisible by 11 (and thus not prime, except 11 itself).

-Note that odd digit-length palindromes that have at most 2k+1 digits can be generated by running over all numbers of digit-length 0 to k and "palindrifying" each one in 9 different ways. e.g., 12 -> 12X21, for X between 0 and 9.

Also, you spoke about ending with a 2, but in fact to be prime not only should you not end with a 2 but you should end with an odd digit. Thus, when making palindromes from k-digit numbers we can skip over any numbers whose first digit is even.

With all this said, remember that you wanted to make palindromes for numbers up to 100 million. 100 million itself is not a palindrome, so basically what we want is to generate all palindromes of at most 7 digits (and we skip even-length ones since they are divisible by 11, so we generate only 7 digit ones, 5 digit, 3 digit, and 1 digit). We generate these by looping over 3 digit, 2 digit, 1 digit, and "0-digit" numbers, respectively. This totals out to somewhere on the order of 1000 numbers we generate from, all together. Each one can be "palindrified" in 9 ways, so that's like on the order of 9000 things now. But we skip out on half of them because we skip any number that begins with an even digit. So basically we do primality testing for ~ 4500 numbers. If you do just plain old square root primality testing, sqrt(100 million) is 10,000, so we're doing at MOST 10,000 % tests for each number we generated. So we're finally at ~ 10,000 * 4500 = 45,000,000 "units of time" we're spending. Considering that the 10,000 figure was an upper bound and that many numbers will probably fail out of the primality testing early, this may run in time.

Hope this helped.

PS. Even though we skip over even digit-length ones, don't forget
to include 11 in your result. : )

EDIT:
After re-reading your post, I realized you also asked about generating palindromes. Here's one way:

- All 1-digit numbers are palindromes
- An n+2-digit palindrome is of the form x*10^(n+2) + (some n-digit palindrome*10) + x for some non-zero digit x <--- (fact 2)

Considering there are only about 1000 palindromes of odd digit-length <=5, you can generate them all and store them in arrays very quickly. Then generate the ones ending in odd digits by using (fact 2) for x=1;x<=9;x+=2

Of course there are other ways..but we're only gonna be doing this a couple thousand times, so it doesn't have to be that efficient.
Last edited by Minilek on Tue Aug 03, 2004 3:19 pm, edited 2 times in total.
doraemon2112
New poster
Posts: 9
Joined: Sun Jul 11, 2004 10:55 am
I've passed this problem.
A small hint: The length of all prime palindromes must be odd.
For example, there is NO prime palindromes within the range 1000~9999, 100000~999999.
midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:
thanks a lot!!! I got AC
I just confuse when I say terminated in 2..I mean that n%2==0
I just need this part:
- An n+2-digit palindrome is of the form x*10^(n+2) + (some n-digit palindrome*10) + x for some non-zero digit x
hehe...but all the other part is useful too.
It is the problem number 4 in the USACO.. in the section 1.2
thx again!!!  I really appreciate!
I wish u good luck!!!!