【例題】
それ自身を含むすべてのプリフィックスがハーシャッド数で数字和が初めて50を超える数を求めよ
ハーシャッド数
ハーシャッド数(Wikipedia)とはあまりなじみのない数ですが一言で言うと「数字和で割り切れる」数のことです。
この例題ではそれ自身だけでなくすべてのプリフィックスがハーシャッド数となる数字を探すことが求められています。例として2478は以下のようにすべてのプリフィックスがハーシャッド数になっています。
2 / 2 = 1 \\
24 / 6 = 4 \\
247 / 13 = 19 \\
2478 / 21 = 118 \\
単純に1からチェックしていってもそう簡単には数字和が50にはならないことが分かります。
そこで考え方を逆にして一桁のハーシャッド数（1,2,3,4,...,9）の右に数字を加えて行ってハーシャッド数になればまた継続して次のハーシャッド数を求めるようにしました。 実装はQueueを使って幅優先探索を行っています。
答えは19桁とかなり大きな数になりました。
import queue
DS = 50
q = queue.Queue()
for i in range(1,10): # (n, ds) initial vaules: single digit numbers
q.put((i,i))
ans = 0
while not q.empty():
(n,ds) = q.get()
for i in range(10):
n1, ds1 = n*10+i, ds+i # add one digit
if n1 % ds1 == 0: # Harshad number?
if ds1 >= 50: # if digit sum > 50, answer found
q.queue.clear()
print(n1,ds1)
else:
q.put((n1,ds1))
#print(n1,ds1)
print(f"Answer = {ans}")
# 2040084800080000847 53
この考え方はProject Euler, Problem 387: Harshad Numbersを解くのに役に立ちます。
（開発環境：Google Colab）