0
$\begingroup$

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.

  • 0
    Note that if two numbers "start with" 9, their product can start with 8 (e.g. $9 \times 9 = 81$), so your two formulations of the question are a bit different from each other.2012-12-17

1 Answers 1

3

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.

  • 1
    @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.2012-12-18