Техника

Указать такое натуральное число начиная с которого 12 последующих чисел являются составными.

Указать такое натуральное число начиная с которого 12 последующих чисел являются составными.
Перебор нам поможет! Составляем на любом языке небольшую программку, которая в цикле перебирает целые числа и на каждом шаге поверяет, не является ли хотя бы одно из N+1, ..N+12 простым числом.

Написал простейшую прогу за 5 минут, с самым тупым вариантом проверки не является ли число простым. Думал, будет сейчас считать... Ответ был молниеносный - 113.

Это минимально возможное, если я нигде не ошибся :-)
Марина Гандзюк (Лившиц)
Марина Гандзюк (Лившиц)
86 411
Лучший ответ
Марина Гандзюк (Лившиц) Еще проще было просто проанализировать список первых простых чисел и найти соседние, разность которых превышает 12.
Перемножь, например, числа от 2 до13,
или учитывая наличие повторных сомножителей 13, 11, 7, 5, 9, 8 = 1001*360= 360 360.
Все числа от 360360 до 360372 составные
В общем, нам надо найти число N такое, что N+1, N+2, N+3, N+4, N+5, N+6, N+7, N+8, N+9, N+10, N+11, N+12 являются составными. Нетрудно заметить, что если N делится на 2, 3, 5, 7, 11, то любая из вышеперечисленных сумм тоже делится на эти числа. Кроме первой, N+1.

Поэтому положим N = 2 * 3 * 5 * 7 * 11 * k и подберём такое k, чтобы N+1 тоже было составным. Ясно, что N+1 не будет делиться на уже использованные числа. Поэтому потребуем, чтобы N+1 делилось, например, на 13. Получаем диофантово уравнение:
2 * 3 * 5 * 7 * 11 * k + 1 = 13 q
13q - 2310k = 1

Путем несложных вычислений находим частное решение: k = 10, q = 1777, откуда получаем окончательный ответ:
N = 23100

Не берусь, правда, утверждать, что это число минимальное из возможных...
Abzal Agabek
Abzal Agabek
24 825
Марина Гандзюк (Лившиц) Чего-то я не понял. "Если N делится на 2, ..то любая сумма тоже делится на эти числа. " Это как это?
Если число четное, то N+3 - нечетное и оно не может делиться на 2. Аналогично, если число делится на 3, то N+5 никак не будет делится на 3.
Марина Гандзюк (Лившиц) Минимальное 113 :-)