Я рассматривал равенство i*j = rev(j)rev(i) и перебирал всевозможные варианты числа i, то есть в отличие от вас, я перебирал младшие разряды произведения. Допустим для n = 4: abcd*xyzt = tzyxdcba, где xyzt нам неизвестно. Сначала рассматриваем разряд единиц: a = (d*t)%10. Чтобы найти t, я предрассчитал все варианты t для всех пар a и d. В цикле перебираем все варианты t и запускаем рекурсию, переходя к следующему разряду. Разряд десятков: b = (c*t + d*z + (d*t)//10)%10. Нам уже известно значение t, поэтому можем в модульной арифметике записать (d*z) % 10 = (b - c*t + (d*t)//10) % 10. И снова находим z пользуясь предрассчитанными значениями, в цикле перебираем все варианты и запускаем рекурсию, переходя к следующему разряду. Разряд сотен: c = (b*t + c*z + d*y + (c*t + d*z + (d*t)//10)//10)%10. Снова находим d*y в модульной арифметике и так далее.
Значение в скобках я обозначил accum - его не надо пересчитывать полностью, а только добавлять новые слагаемые и делить на 10.
В некоторых случаях оказывается, что вариантов очередной цифры нет и рекурсия просто завершается (например (2*t)%10 = 3 не имеет решений). Если дошли до конца, то проверяем, выполняется ли требуемое равенство для найденного значения xyzt.
Интересная идея! Понимаю, что вы не питонист, но по-моему, range должен идти от 0 до 10+1, поскольку последнее значение не включается и теоретически может так оказаться, что дробная часть первого и второго слагаемого в сумме дают ещё один. В усовершенствованном варианте получается range(0, 10//a[0] + 1). Ну и если добавить проверки на a % 3 != 1 и b % 3 != 1, то получится ещё почти в 2 раза ускорение.
for n in range(1, 4+1):
p = 10**(n-1)
count = 0
for i in range(p, p*10):
for j in range(i, p*10):
if sorted(str(i)+str(j)) == sorted(str(i*j)):
count += 1
print(n, count)
Переворачивающиеся при умножении числа
Hidden text
MIN = 1
MAX = 8
divisors_mod10 = [[[] for j in range(10)] for i in range(10)]
for i in range(10):
for j in range(10):
divisors_mod10[(i*j)%10][i].append(j)
def f(i, si, n, k, sj, accum):
if k == n:
if sj[0] >= sj[n-1]:
j = int("".join(map(str, sj)))
sm = "".join(map(str, (si + sj)[::-1]))
if int(sm) == i*j:
print(f"{i} * {j} = {sm}")
return
for k1 in range(k):
accum += si[n-1-k+k1]*sj[n-1-k1]
vd = divisors_mod10[(si[k] - (accum % 10) + 10) % 10][si[n-1]]
for divisor in vd:
sj[n-1-k] = divisor
if k == 0 and si[0] < sj[n-1]:
continue
f(i, si, n, k+1, sj, (accum + si[n-1]*sj[n-1-k])//10)
for n in range(MIN, MAX+1):
print(f"n={n}")
p = 10**(n-1)
for i in range(p+1, p*10):
if i % 3 == 1:
continue
if i % p == 0:
print(i)
si = list(map(int, str(i)))
sj = [0]*len(si)
f(i, si, n, 0, sj, 0);
Если вкратце, в произведении i*j=m перебираются всевозможные i и все возможные первые t=4 цифры числа m (обозначим за x). По этим значениям определяется, каким может быть число j – оно лежит в некотором диапазоне и при этом должно обязательно содержать цифры, которые входят в x и не входят в i. Списки чисел, которые содержат определённый набор цифр предрассчитываются, поэтому требуется много памяти при больших n.
А вы не против, если я ваш код приведу как пример на oeis.org?
Я вот эту последовательность хочу зарегистрировать https://oeis.org/draft/A370723
Либо можете сами зарегистрироваться и вписать в раздел PROG - там любой человек может черновик редактировать.
Нашёл последовательность для переворачивающихся чисел не обязательно одинаковой длины: A009944 - OEIS
182738252812 туда тоже входит, но его официально не подтвердили, поэтому по нему не ищется.
Добавил в базу две последовательности. Пока они в статусе draft.
A370675 - OEIS
A370676 - OEIS
Все 4 оптимизации очень достойные!
Ваше умение обращаться с GPU впечатляет!
Я рассматривал равенство i*j = rev(j)rev(i) и перебирал всевозможные варианты числа i, то есть в отличие от вас, я перебирал младшие разряды произведения. Допустим для n = 4: abcd*xyzt = tzyxdcba, где xyzt нам неизвестно. Сначала рассматриваем разряд единиц: a = (d*t)%10. Чтобы найти t, я предрассчитал все варианты t для всех пар a и d. В цикле перебираем все варианты t и запускаем рекурсию, переходя к следующему разряду.
Разряд десятков: b = (c*t + d*z + (d*t)//10)%10. Нам уже известно значение t, поэтому можем в модульной арифметике записать (d*z) % 10 = (b - c*t + (d*t)//10) % 10. И снова находим z пользуясь предрассчитанными значениями, в цикле перебираем все варианты и запускаем рекурсию, переходя к следующему разряду.
Разряд сотен: c = (b*t + c*z + d*y + (c*t + d*z + (d*t)//10)//10)%10. Снова находим d*y в модульной арифметике и так далее.
Значение в скобках я обозначил accum - его не надо пересчитывать полностью, а только добавлять новые слагаемые и делить на 10.
В некоторых случаях оказывается, что вариантов очередной цифры нет и рекурсия просто завершается (например (2*t)%10 = 3 не имеет решений). Если дошли до конца, то проверяем, выполняется ли требуемое равенство для найденного значения xyzt.
P.S. si и sj хранят цифры чисел i и j.
Интересная идея!
Понимаю, что вы не питонист, но по-моему, range должен идти от 0 до 10+1, поскольку последнее значение не включается и теоретически может так оказаться, что дробная часть первого и второго слагаемого в сумме дают ещё один. В усовершенствованном варианте получается range(0, 10//a[0] + 1).
Ну и если добавить проверки на a % 3 != 1 и b % 3 != 1, то получится ещё почти в 2 раза ускорение.
Исходная задача
Hidden text
Переворачивающиеся при умножении числа
Hidden text
Если вкратце, в произведении i*j=m перебираются всевозможные i и все возможные первые t=4 цифры числа m (обозначим за x). По этим значениям определяется, каким может быть число j – оно лежит в некотором диапазоне и при этом должно обязательно содержать цифры, которые входят в x и не входят в i. Списки чисел, которые содержат определённый набор цифр предрассчитываются, поэтому требуется много памяти при больших n.
Думаю, что не может. На math.stackexchange.com мне вообще рекомендовали к нему не обращаться)