Простой перебор m-значных чисел требует просмотреть 10m - 10m-1 чисел.
Эникейщик предложил сократить перебор цифр для небольших номеров разрядов - остаток от деления должен быть строго меньше номера разряда.
Ещё один способ сократить перебор - учесть связи между разрядами i и j если первый делится на второй. В этом случае для любого n верно что n % j = (n % i) % j (% - взятие остатка от деления).
Левая часть равенства - цифра в разряде j (dj), в скобках в правой части цифра в разряде i (di). Следовательно di % j = dj.
Например: d3 = 2, тогда d12 может принимать значения 2, 5 или 8.
Для сравнения таблица числа кандидатов:
m все с учётом с учётом
числа малых разрядов малых разрядов и
связи между разрядами
1 9 9 9
2 90 18 18
3 900 54 54
4 9e3 216 108
5 9e4 1080 540
6 9e5 6480 540
7 9e6 45360 3780
8 9e7 362880 7560
9 9e8 3265920 22680
10 9e9 32659200 22680
11 9e10 3.26592e8 226800
12 9e11 3.26592e9 189000
13 9e12 3.26592e10 1890000
14 9e13 3.26592e11 1350000
15 9e14 3.26592e12 918000
.
.
.
42 9e41 3.26592e39 2970000000
43 9e42 3.26592e40 29700000000
Код ниже использует и малые разряды и связь. Это рекурсивный поиск от второго разряда до младшего. Если поиск сумел построить все цифры, к заготовке добавляется старший разряд. Получившееся число проверяется is_friendly
. За четыре минуты будут найдены все известные мне приветливые числа. Самое большое из них - двадцатизначное:
for m in range(1, 21):
found = []
d = [0] * (m + 1)
def is_friendly(n):
return all(n % i == d[i] for i in range(2, m + 1))
def make_pred(j):
return lambda e: e % j == d[j]
preds = tuple(
tuple(make_pred(j) for j in range(2, i) if i % j == 0)
for i in range(m + 1)
)
def digits(i):
digits = range(min(i, 10))
for p in preds[i]:
digits = filter(p, digits)
return digits
def search(i, n):
if i > m:
for e in range(1, 10):
# d[1] = e
n1 = 10 ** (m - 1) * e + n
if is_friendly(n1):
found.append(n1)
return
for e in digits(i):
d[i] = e
search(i + 1, 10 * n + e)
search(2, 0)
print(m, len(found))
for n in sorted(found):
print(f' {n}')
Карта местности:
m: количество: примеры
1: 10: 1 2 3 4 5 6 7 8 9
2: 18: 10 11 20 21 30 31 40 41 50 51 60 61 70 71 80 81 90 91
3: 9: 211 300 302 511 600 602 811 900 902
4: 24: 1002 ... 9020
5: 45: 11013 ... 90200
6: 18: 101044 ... 911311
7: 8: 1123151 2121353 3103035 5010040 5012146 5113015 7020020 7022126
8: 17: 11133163 ... 91232567
9: 9: 101044444 ... 900000540
10: 96: 1000405404 ... 9123455759
11: 3: 30204244844 60200244500 90022046622
12: 14: 101044141444 ... 901044647404
13: 5: 2103034705335 3111312173713 6002202202362 8010442044544 9111211577917
14: 11: 10004044347084 ... 80222222822282
15: 19: 101044241414524 ... 910133510389353
16: 5: 4020322088789288 ... 8010446444540644
17: 1: 81031327310329671
18: 1: 902232028812008258
19: 0:
20: 3: 10000024006072048020 21111111710181114721 80200240800854581880
21: 0:
.
. здесь нет ни одного числа
.
60: 0:
С помощью китайской теоремы об остатках можно ускорить перебор ещё примерно в пятнадцать раз. Если известны около 2/3 старших разрядов, младшие разряды можно восстановить без перебора. Программу это сильно раздувает, я её тут не привожу.
Главный вопрос - есть ли приветливые числа большие 1020? Перебор уже дошёл до 1060 - ничего не найдено. Я думаю что их нет, доказать не могу.
pypy
и @Эникейщик я дотащился до 10^10.