(максимальная длина таких цепочек 10)
Это не так, максимальная длина таких "цепочек" (потому что цепочками их называть как-то не слишком логично) лишь 7, так как три цифры из десяти будут запрещены признаком делимости на 3.
Первая 5-ка
Все 6-ки (потому что пятёрок слишком много) для простых до миллиарда:
n=6:9303487+[0, 2, 3, 5, 6, 9]
n=6:77569301+[0, 1, 4, 6, 7, 9]
n=6:99769961+[0, 1, 3, 4, 7, 9]
n=6:132891041+[0, 1, 4, 6, 7, 9]
n=6:195449557+[0, 2, 3, 5, 6, 8]
n=6:324935371+[2, 3, 5, 6, 8, 9]
n=6:344406157+[0, 2, 5, 6, 8, 9]
n=6:381469303+[0, 2, 3, 5, 6, 9]
n=6:710697437+[0, 1, 3, 4, 6, 7]
n=6:933463313+[0, 1, 3, 6, 7, 9]
(длина, начальное простое, список вставляемых цифр).