Алгоритм grizzly, если я правильно его понял, заключается в том, что мы проверяем ВСЕ разряды в исходном числе,
и если при вставке на один из этих разрядов одной из 10 цифр получается простое число, то итерация продолжается
Да, разумеется. Я разницу вижу. Я пока рассматривал случай, когда количество вариантов вставок ограничено некоторой величиной. Но можно рассмотреть и алгоритм
grizzly.
Заранее предупреждаю, что последующее рассуждение не использует аккуратных оценок и основано только на асимптотике, поэтому рассматривать его как строгое доказательство не следует.
Как известно, плотность множества простых чисел в окрестности большого натурального числа

имеет асимптотику

.
Если десятичная запись простого числа

содержит

цифр, то

, а число

, полученное расширением числа

одной цифрой (неважно, куда вставленной), удовлетворяет неравенству

, поэтому

.
Для вставки перед первой цифрой имеется

вариантов (первая цифра не должна быть

), для вставки после последней цифры разумными являются только

варианта (

,

,

,

), так как в остальных случаях получается составное число, которое делится на

или на

. Так как таким образом отсекаются все числа, делящиеся на

или на

, то плотность простых чисел среди оставшихся увеличивается в

раза и оценивается теперь величиной

("асимптотически сверху").
По этой причине вероятность того, что конкретная вставка даст составное число, можно оценить ("асимптотически снизу") величиной

.
Число возможных вставок в методе
grizzly равно

, поэтому можно ожидать, что вероятность того, что все вставки дадут составное число, "асимптотически больше", чем

Можно проверить, что функция

возрастает при

, и что

(24/VI-2021 исправил опечатку в этой формуле.)
В частности, при

будет

, а вероятность того, что хотя бы одна вставка из

возможных даст простое число, будет "асимптотически меньше"

. Соответственно, вероятность того, что, начиная с не менее чем

-значного простого числа, нам удастся продлить цепочку простых чисел не менее чем на

шагов, будет "асимптотически меньше"
![$$(1-1{,}9\cdot 10^{-5})^k\xrightarrow[k\to\infty]{}0.$$ $$(1-1{,}9\cdot 10^{-5})^k\xrightarrow[k\to\infty]{}0.$$](https://dxdy-02.korotkov.co.uk/f/1/b/b/1bb1ce28849d89ff957e8b2bcbb647cc82.png)
Таким образом, каждая конкретная цепочка вставок обрывается с вероятностью

. Это, однако, не доказывает невозможность бесконечной цепочки вставок, дающих простые числа, а также не доказывает, что, начав с некоторого простого (или составного) числа, невозможно найти сколь угодно длинные цепочки вставок, дающих простые числа.
Я далеко не специалист в теории чисел, поэтому подробнее вдаваться в это дело не буду.
Где-то через минут пять после старта я добираюсь до 1000-значного простого числа
Судя по полученной оценке вероятности существования успешной вставки, Вам следует продлить свой эксперимент до чисел, содержащих хотя бы сотню тысяч цифр, а может быть и больше. Но тут уже, вероятно, придётся использовать не математические пакеты, а специализированные программы, умеющие эффективно выполнять тест с помощью теоремы Ферма. Например,
OpenPFGW. И придётся написать для неё скрипт, автоматизирующий поиск вставок и сохраняющий некоторые промежуточные результаты, достаточные для возобновления расчётов в случае прерывания вычислений. Но даже и здесь вычисления могут потребовать чрезвычайно много времени.