This time I have one of the better solutions:

def nextpal(low,high,reversed=False):

assert low < high

if reversed:

candidate = high

final = low

increment = -1

else:

candidate = low

final = high

increment = 1

while candidate != final:

if str(candidate) == str(candidate)[-1::-1]:

yield candidate

candidate += increment

def getfactor(low,high,target):

for test in range(low,high):

if not target % test:

residual = target/test

if residual in range(low,high):

return test, residual

return None

if __name__ == "__main__":

from time import time

start = time()

pal = nextpal(10000,1000000, reversed=True)

while True:

target = pal.next()

result = getfactor(100,1000,target)

if result:

print target

print result

break

end = time()

print end - start

Most started from the factors to see if they built palindromes. Much better to go the other way; far fewer tests (the 94th palindrome succeeded, so less than 9400 calculations. The cast to string for the palindrome test is easy, but is it efficient?

The most interesting items on the discussion were the Pytho one-liner:

max(map(lambda s: bool(s) and max(s) or 0, [(filter(lambda n: n == int(str(n)[::-1]), map(lambda n: i*n, range(999, 99, -1)))) for i in range(999, 99, -1)]))

and the pen-and-paper solution

You can also do this with pen and paper. You have a number:

(100a + 10b + c)(100d + 10e + f)

Which is a palindrone. This factors out to:

100cd + 10ce + cf +

1000bd + 100be + 10bf +

10000ad + 1000ae + 100af

Assuming the first digit is 9, then cf must be equal to nine.

Also, both a and d must then be equal to nine. The only ways

to make the last digit of the product of two integers 9 would

be if those integers were either of:

1 and 9

3 and 3

7 and 7

So, both numbers must start with 9, end with either 1, 3, 7,

or 9, and one of them must be divisible by 11. The only

numbers divisible by 11 from 900 - 1000 are:

902

913

924

935

946

957

968

979

990

You can discard all of those that do not end in either 1, 3,

7, or 9, and you are left with:

913

957

979

So now the presumed answer is either:

(900 + 10 + 3)(900 + 10x + 3)

(900 + 50 + 7)(900 + 10x + 7)

(900 + 70 + 9)(900 + 10x + 1)

Factoring all those out, you get:

810000 + 9000x + 2700 + 9000 + 100x + 30 + 2700 + 30x + 9

824439 + 9130x

Now, for the first digit 824439 + 9130x to be 9, x must be 9

(if x were 8, then 824439 + 9130x = 897479, and the first

digit is 8). And so you have 913 * 993, which is the answer.

You can factor the others out to see if they produce a bigger

answer, which they don't.

## No comments:

Post a Comment