Срочно математика на логику

Напоминает китайскую теорему об остатках, только без самих остатков.

По идее, нужно называть простые числа и их степени. Без простых чисел мы не сможем обнаружить их самих. Без всех степеней останется неоднозначность (например, 8 и 16 делятся на 8 и больше ни на что, поэтому надо проверять ещё делимость на 16).

Перечень получается такой:

 20 - составное число, не называем.

19 - простое число.

18 - составное число, не называем.

17 - простое число.

16 - степень простого числа.

15 - составное число, не называем.

14 - составное число, не называем.

13 - простое число.

12 - составное число, не называем.

11 - простое число.

10 - составное число, не называем.

9 - степень простого числа.

8 - степень простого числа.

7 - простое число.

6 - составное число, не называем.

5 - простое число.

4 - степень простого числа.

3 - простое число.

2 - простое число. 

Итого 12 делителей, которые нужно перебрать.

Для числа 20.

 9 - нет, исключаем {9, 18}, остаётся 18 чисел

8 - нет, исключаем {8, 16}, остаётся 16 чисел

7 - нет, исключаем {7, 14}, остаётся 14 чисел

5 - да, {5, 10, 15, 20}

4 - да, {20} 

Пять попыток.

В прямом порядке:

 2 - да (остаются чётные)

3 - нет, {2 4 8 10 14 16 20}

4 - да, {4 8 16 20}

5 - да, {20} 

Четыре попытки.

Для числа 19: в обратном порядке найдём сразу (на 19 делится только оно), а в прямом - будем перебирать 8 делителей:

 2 - нет (остаются нечётные)

3 - нет, { 1, 5, 7, 11, 13, 17, 19 }

5 - нет, { 1, 7, 11, 13, 17, 19 }

7 - нет, { 1, 11, 13, 17, 19 }

11 - нет, { 1, 13, 17, 19 }

13 - нет, { 1, 17, 19 }

17 - нет, { 1, 19 }

19 - да, { 19 } 

(если на некую степень не делится, то следующие степени не называем)

А для числа 2 в обратном порядке придётся перебирать все 12 делителей, а в прямом:

 2 - да (остаются чётные)

3 - нет, {2 4 8 10 14 16 20}

4 - нет, {2 10 14}

5 - нет, {2 14}

7 - нет, {2} 

5 попыток.

Для числа 18, прямой порядок:

 2 - да (остаются чётные)

3 - да, {6, 12, 18}

4 - нет, {6, 18}

9 - да, {18} 

Четыре попытки.
Заметим, что 5, 7, 8 перебирать не нужно, т.к. в списке остающихся к тому моменту вариантов нет чисел, которые делятся на них.

Для числа 16, прямой порядок:

 2 - да (остаются чётные)

3 - нет, {2 4 8 10 14 16 20}

4 - да, {4 8 16 20}

5 - нет, {4 8 16}

8 - да, {8 16}

16 - да, {16} 

Шесть попыток. Можно было бы не проверять 5, осталось бы 5 попыток.

Так что видим, что минимальное число попыток для гарантированного угадывания в общем случае - это 8, и делители надо перебирать в порядке возрастания:

 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19 

Можно поставить 8 перед 5, это поможет быстрее найти 16, но не поможет с остальными числами. Самые худшие числа - это 19 и 1, для них придётся перебирать максимум из 8 делителей. Причём, изменение их порядка может лишь заменить на худшем месте 19 на другое число из перечня делителей, и в худшем случае всё равно останется не менее 8 делителей к перебору.

**Срочная математическая логика** \- *Срочная математическая логика*

Вася должен иметь хотя бы представление о том, насколько большим может быть это число, но он не должен знать, какое именно число задумал Петя. вряд ли удастся найти точное число без какой-либо подсказки, чтобы сузить его.