Наибольшее не смехосоставное число

[Ktina]

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

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

[waxtep]

Жадинно-говядинный способ дает $9719$, но еще бы доказать или, "кто больше? продано!"

[Ktina]

waxtep
Достаточно доказать, что 5-значных не бывает, и тело в шляпе!

[waxtep]

Это я поленился сделать, там какая-нибудь делимость на три вылазит, да? Можно по-другому: составить маленький табличкандыр, кто за кем может следовать, и по получившемуся конечному автомату быстро прогуляться. Вариантов немного, т.к. все, кроме $1,3,7,9$ может быть только в старшем разряде, за девяткой может идти только семерка и т.д. Самый неудачный старший разряд для несмехосоставных чисел - двойка, максимальное такое число всего лишь $29$

[grizzly]

waxtep в сообщении #1330580 писал(а):

там какая-нибудь делимость на три вылазит, да?

Нет, на 3 не вылазит: 97319.

[kotenok gav]

grizzly в сообщении #1330585 писал(а):

973

Делится на 7.

[grizzly]

kotenok gav
Да там, наверное, все трёхзначные, четырёхзначные и пятизначные на что-то делятся. Но не на 3.

[waxtep]

Вот я поэтому засмущался идти путем доказательства отсутствия пятиразрядных несмехосоставных. Ведь старший разряд может быть произвольным, необязательно $1,3,7,9$, а четырехразрядные несмехосоставные существуют. Неочевидно, как сюда делимость на что-нибудь притянуть.

[wrest]

PARI/GP уверяет нас со всей ответственностью, что все пятизначные числа смехосоставные.
Для истории, функция PARI/GP которая возвращает "1" если число смехосоставное и "0" если нет:

Ktina128885 =
  (n)->my(v=digits(n),len=#v);if(n<10,return(0));for(j=1,len-1,for(i=1,len-j,if(ispseudoprime(fromdigits(v[i..i+j])),,return(1))));return(0)

Использование:

? Ktina128885(1)
%1 = 0
? Ktina128885(8)
%2 = 0
? Ktina128885(11)
%3 = 0
? Ktina128885(12)
%4 = 1
? Ktina128885(97)
%5 = 0
? Ktina128885(673)
%6 = 0
? Ktina128885(9719)
%7 = 0
? Ktina128885(97319)
%8 = 1

[Ktina]

wrest
Большое спасибо!

-- 05.08.2018, 01:16 --

wrest в сообщении #1330652 писал(а):

PARI/GP уверяет нас со всей ответственностью, ...

(Оффтоп)

Она платная?

[wrest]

Ktina
PARI/GP это GNU/GPL (бесплатная, то есть).
Очень многие вещи, в том числе ваши придумки про простые числа, факториалы, суммы цифр и т.п. реализуются там как one-liner-ы.
Так же, см. «интерактивный курс: введение в программирование на PARI/GP»

[Ktina]

wrest в сообщении #1330662 писал(а):

Так же, см. «интерактивный курс: введение в программирование на PARI/GP»

А за это отдельное спасибо!

[yk2ru]

Aribas ещё есть. http://progopedia.ru/language/aribas/ С помощью паскалевидного языка можно много чего запрограммировать и посчитать. Например вывести простые числа до 100.

n:=1;
while n<98 do
 n := next_prime(n+1);
 if n<100 then
  writeln(n);
 end;
end.

[wrest]

yk2ru в сообщении #1330820 писал(а):

Например вывести простые числа до 100.

? primes([1,100])

[yk2ru]

Там своя программа со своим языком, и только. Я использую этот "калькулятор", когда нужно что то посчитать. При том, запускаю на линукс версию под Windows, хотя можно скачать и чисто Unix версию. Нашёл эту прогу ещё до пользования линуксом.