# Proof for all largest palindrome numbers for each power of 10

Is there a proof that shows that for any power of 10 the largest palindrome formed by the product of two numbers with equal number of digits occur in the last tenth of the given power of ten. Or another way to say it is do the two numbers start with 9.

First 6 examples

99*91=9009
993*913=906609
9999*9901=99000099
99979*99681=9966006699
999999*999001=999000000999
9999979*9467731=94677111177649


Also is possible to show that the palindrome has to start with a 9? This may be two separate questions but they seem closely related.

Also, if your wondering where I came up with this I was working on project 4 of the Euler project http://projecteuler.net/problem=4 and after solving the problem and then generalizing the problem to all powers of ten I was wondering how to optimize my algorithm to search for these palindromes.

-
This problem is a mess. It's not at all clear what you mean by "largest power palindrome," for example - do you mean "largest palindrome?" Also, when you say two numbers have the "same length," do you mean equal numbers of digits? –  Thomas Andrews Dec 17 '12 at 13:42
The link you include seems to suggest that you're in fact interested in palindromes that are the products of two numbers with certain properties; but you never mention products. –  joriki Dec 17 '12 at 13:43
I think he wants a palindrome $p=x_1x_2$, where $x_1,x_2\in[10^{k-1},10^k)\cap\mathbb Z$ for some $k$. –  Mario Carneiro Dec 17 '12 at 13:50
Note that $(10^{2n}-1)(10^{2n}-10^n+1)=(10^{3n}+1)(10^n-1)$ which seems to be the identity inherent in your final comment. –  Mark Bennet Dec 17 '12 at 13:52
@ThomasAndrews I edited the first paragraph hopefully it is clearer. I struggled with how to word the question and I am not sure of the proper mathematical way to ask it. –  qw3n Dec 17 '12 at 14:05

The formulation given (with smaller factors having leading digit 9) does not work for palindromes of all lengths. For example:$$3 \times 3 = 9$$ $$37 \times 27 = 999$$

So the problem expressed in that form needs to be restricted to palindromes having an even number of digits.

And the part of the question which seems currently to be open is -

Given $n>0$ is there a palindrome having $4n+2$ digits, and leading digit (most significant digit) equal to 9, which is the product of two integers each having $2n+1$ digits?

Notes: the two smaller integers will necessarily have leading digit 9. The largest palindrome of this kind will necessarily have leading digit 9, provided we can find at least one example - though the example we find need not be the largest. For $n=0$ there is no answer, because $9 \times 9 = 81$, which is less than 90, and all two digit palindromes are divisible by 11 (which is prime).

Some construction rather different from the one illustrated will be necessary to tackle palindromes with odd numbers of digits.

-
Thanks for the answer. So if you restrict the problem to even numbered palindromes how would I go about proving it. Also, I added the first 6 examples of palindromes I found. –  qw3n Dec 18 '12 at 0:32
@qw3n There seem to be two obvious approaches - one is to look for a formula for the $4n+2$ case like $(10^{2n}-1)(10^{2n}-10^n+1)=(10^{3n}+1)(10^n-1)$ which gives the family of solutions you found for $4n$ digit palindromes. But in this case you would need to have a reason why the formula did not work in the two digit case. Another way would be to show that there are so many palindromes that one of them must factor in the way you suggest. –  Mark Bennet Dec 18 '12 at 7:47