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
generate palindromes numbers...(Usaco problem)
Moderator: Board moderators
Re:
I haven't gotten to this problem yet in USACO, but after reading your message I think I see how to do it...
[Edit] 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 evennumber 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_{ni+1}. So the sum gives you 0 for an evenlength 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 digitlength palindromes that have at most 2k+1 digits can be generated by running over all numbers of digitlength 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 kdigit 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 evenlength 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 "0digit" 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 digitlength ones, don't forget
to include 11 in your result. : )
EDIT:
After rereading your post, I realized you also asked about generating palindromes. Here's one way:
 All 1digit numbers are palindromes
 An n+2digit palindrome is of the form x*10^(n+2) + (some ndigit palindrome*10) + x for some nonzero digit x < (fact 2)
Considering there are only about 1000 palindromes of odd digitlength <=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.
[Edit] 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 evennumber 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_{ni+1}. So the sum gives you 0 for an evenlength 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 digitlength palindromes that have at most 2k+1 digits can be generated by running over all numbers of digitlength 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 kdigit 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 evenlength 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 "0digit" 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 digitlength ones, don't forget
to include 11 in your result. : )
EDIT:
After rereading your post, I realized you also asked about generating palindromes. Here's one way:
 All 1digit numbers are palindromes
 An n+2digit palindrome is of the form x*10^(n+2) + (some ndigit palindrome*10) + x for some nonzero digit x < (fact 2)
Considering there are only about 1000 palindromes of odd digitlength <=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.

 New poster
 Posts: 9
 Joined: Sun Jul 11, 2004 10:55 am
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+2digit palindrome is of the form x*10^(n+2) + (some ndigit palindrome*10) + x for some nonzero 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!!!!
I just confuse when I say terminated in 2..I mean that n%2==0
I just need this part:
 An n+2digit palindrome is of the form x*10^(n+2) + (some ndigit palindrome*10) + x for some nonzero 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!!!!