Date: 01/04/98 at 15:42:04 From: Zeyneb Akyildiz Subject: Palindromic numbers Dear Dr.Math, My friends and I are working on an extra credit assignment. We were wondering how many palindromic numbers exist that are less than 100 000. Could you also help us with the formula? Thank you, Zeyneb Akyildiz and friends
Date: 01/04/98 at 16:18:37 From: Doctor Pete Subject: Re: Palindromic numbers Hi, One way to do this is to simply count palindromes with a fixed number of digits, and take the sum of these values from 1 digit to 5 (why not 6?). For instance, how many palindromes are there with 4 digits? Well, a 4-digit palindrome must be of the form abba, where a is between 1 and 9, and b is between 0 and 9 (again, why?). How many ways can you choose values of a, and choose values of b? Well, since a and b do not need to be distinct, there are 9 ways to choose a and 10 ways to choose b, hence 90 ways to choose pairs (a,b) to give a palindromic number. So there are 90 4-digit palindromes. Similarly, examine the number of 1-, 2-, 3-, and 5-digit palindromes, and then take the sum. If you want a formula, notice that the number of 3-digit palindromes is equal to the number of 4-digit palindromes, because a 3-digit palindrome is of the form aba, and with the same restrictions on a and b as we saw before, this also gives rise to 9(10) = 90 possibilities. Now, show that if n is odd, the number of n-digit palindromes is equal to the number of (n+1)-digit palindromes. Finally, consider an n-digit palindrome (again n is odd), so it has the representation [a1][a2][a3]...[an]...[a3][a2][a1] (here I have written the digits as a1, a2, a3, ..., an, so the above is not a product but the digit representation). Notice that for the digits a2, a3, ... an, they are all between 0 and 9, and the only digit that cannot be 0 is a1. So how many ways can you choose n-tuples (a1,a2,a3,...,an)? Put all of this together and you get a formula. -Doctor Pete, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.