Шутки ради :)
216354638 раз был прокручен счётчик во вложенных циклах.

Не смешите мои подковы! Поднял свои решения.
906609 – 7069 итераций. Почти мгновенно на моём МакБуукПро (лень мерять).
32 строки, включая заголовок, описание и “if __name__…”

Хм… у меня в конечном варианте на 542 итерации больше.

ред… 6163 :(

У меня 6 строк, 404550 итераций, 100 милисекунд на 2ггц кор2дуо, и я считаю эту скорость приемлимой в случае задачи, которую нужно выполнить 1 раз и не заумствовать с лишней оптимизацией в ущерб потраченного на написание алгоритма время. :)

906609 за 2111 итераций.

98344389 =9967* 9867 за 6 693 итераций
9966006699= 99979 *99681 за 28 542 итераций
996582285699=999089 *997491 за 2 919 772 итераций
99956644665999=9998017 *9997647 за 4 693 908 итераций
А если еще и учесть что искомое число неможет быть четным ( 9……9)
то получается:
906609 =993 *913 за 1 076
98344389 =9967 *9867 за 3 372
9966006699 =99979 *99681 за 14 346
996582285699 =999089 *997491 за 1 460 286
99956644665999 =9998017 *9997647 за 2 347 047
9997324114237999 = 99994669 *99978571 за 89 500 181

num=0
N=999
for i in xrange(N,1,-1):
for y in xrange(N-i):
tmp1=str((i+y)*(i-y))
num+=1
tmp2=''.join(list(tmp1))
if tmp1==tmp2:
print tmp1, i+y, i-y, num
raise

Ваш алгоритм при длине символов равной 4 работает неправильно. При любой чётной длине символов будут схожие результаты.

А на чём базируется утверждение о нечётности? Наблюдения, или есть соответствующее матиматическое доказательство?

ред…
То есть интуитивно понятно что результат должен быть заключён где то между девятками. Тогда безусловно поиск упрощается во много раз. Но вот как это доказать? :)

ред2… Интересно за 1 383 347. И в тоже время за 25 580.

Да действительно поторопился, (вечер воскресенье)
num=0
N=999
for i in xrange(N,1,-1):
for y in xrange(N-i,0,-1):
tmp1=str((i+y)*(i-y))
num+=1
tmp2=''.join(list(tmp1))
if tmp1==tmp2:
print tmp1, i+y, i-y, num
raise
Про нечетность матиматически доказывать небуду, (давно незанимался доказательствами), но если предположить что мы ищем максимальное число из чисел вида 1..1, 2..2 и.т.д то нас скорее всего будет интересовать 9..9
но если это отбросить то нужно добавить проверку чисел tmp1=str((i+y)*(i-y-1))
906609= 993* 913 за 1 042
99000099= 9999* 9901 за 1 177
9966006699= 99979* 99681 за 14 217
999000000999= 999999* 999001 за 124 252
99956644665999= 9998017* 9997647 за 2 348 844
9999000000009999= 99999999* 99990001 за 12 492 502

Если отбросить четные
и подправить строчку
for y in xrange(N-i,0,-2):
то 906609 993 913 за 533
Хотя согласен это все на предположениях, без обоснований и докозательств, но ответ правильный вплоть до 8 значных.

Мда, нет предела совершенству:
906609 = 913 * 993 , count = 162
99956644665999 = 9997647 * 9998017 , count = 110 958
9999000000009999 = 99990001 * 99999999 , count = 2 001 000

p.s. сейчас найдётся кто-то, кто выполнит это дело в одно действие :)

Griffon
906609 = 913 * 993 , count = 162

алгоритм в студию :)