Наипростейшие числа

[caxap]

Назовём наипростейшими такие простые числа, которые остаются простыми при отбрасывании любого количества младших цифр (но не всех, разумеется). Например: число 3793 простое, такие же 379,37,3. число 719333 и т. д.

Как доказать, что девяти- и более значных наипростейщих чисел не бывает? Своих попыток пока нет, т. к. ума не проложу пока.

[ИСН]

Перебрать восьмизначные и убедиться, что они не наращиваются дальше.

[mitia87]

Вспоминается задача про простейшие числа.
Назовём простейшим такое простое число, любое подмножество последовательных цифр которого образуют простое число. Найти все простейшие числа.

[caxap]

ИСН в сообщении #301074 писал(а):

Перебрать восьмизначные и убедиться, что они не наращиваются дальше.

Не понял как это сделать. Я как компьютер перебирать не могу. Вообще, как вручную можно проверить простоту, скажем 8-значного числа. Я кроме перебора делителей ничего не знаю, но таким образом проверять нереально, если ты не компьютер.

[Профессор Снэйп]

А компьютером и предлагается перебирать

[caxap]

А без компьютера это доказать никак нельзя? Т. е. ручкой и бумагой?

[Профессор Снэйп]

Может и можно, но мне сей способ неведом Хотя... Может, там перебор и не такой уж большой. Сколько всего трёхзначных наипростейших (то есть сколько вариантов для первых трёх цифр)?

Кстати, а восьмизначные наипростейшие числа бывают?

[ИСН]

Бывают, к сожалению, и не одно. Так что нет, пожалуй, голыми руками всё-таки никак.
http://en.wikipedia.org/wiki/Truncatable_prime

[mihiv]

Перебор можно,наверно,довольно сильно сократить,если записывать эти числа,начиная со старшего разряда.Нужно учесть,что в старшем разряде могут быть только цифры 2,3,7,а востальных разрядах только 1,3,7,9.Кроме того такие числа должны содержать 1 и 7 не более чем двух разрядах(в остальных разрядах должны быть тройки и девятки).

[Профессор Снэйп]

ИСН в сообщении #301403 писал(а):

Бывают, к сожалению, и не одно.

Ага, целых $83$ штуки. Офигеть!

Ручной перебор без компьютера вполне возможен, если иметь под рукой таблицу всех простых чисел, меньших $10^{10}$