Проект Эйлера. Задача 32 «Пан-цифровые произведения»

Условие:

Каждое n-значное число, содержащее каждую цифру от 1 до n ровно один раз, будем считать пан-цифровым. К примеру, 5-значное число 15234 является пан-цифровым, т.к. содержит цифры от 1 до 5.

Произведение 7254 является необычным, поскольку равенство 39 × 186 = 7254, состоящее из множимого, множителя и произведения, является пан-цифровым, т.е. содержит цифры от 1 до 9.

Найдите сумму всех пан-цифровых произведений, для которых равенство «множимое × множитель = произведение» можно записать цифрами от 1 до 9, используя каждую цифру только один раз.

ПОДСКАЗКА: Некоторые произведения можно получить несколькими способами, поэтому убедитесь, что включили их в сумму лишь единожды.

Решение:

Для решения этой задачи нам понадобятся 2 вспомогательные функции:

1-я функция sqrt() — принимает на вход integer и возвращает floor(sqrt(x)), где floor(x) — числовая функция, которая возвращает наибольшее целое число, не больше чем x.

2-я — has_pandigital_product(n) — проверяет, есть ли пан-цифровое значение.

# Given integer x, this returns the integer floor(sqrt(x)).
def sqrt(x):
	assert x >= 0
	i = 1
	while i * i <= x:
		i *= 2
	y = 0
	while i > 0:
		if (y + i)**2 <= x:
			y += i
		i //= 2
	return y


def has_pandigital_product(n):
	for i in range(1, sqrt(n) + 1):
		if n % i == 0:
			temp = str(n) + str(i) + str(n // i)
			if "".join(sorted(temp)) == "123456789":
				return True
	return False


def compute():
	ans = sum(i for i in range(1, 10000) if has_pandigital_product(i))
	return str(ans)


if __name__ == "__main__":
	print(compute())