Question

Мистер Фикс задумал некоторое натуральное число N, большее 410, но меньшее 420, и сложил все натуральные числа от 1 до N. Он обнаружил, что полученная сумма делится на некоторое простое число p, однако ни одно слагаемое на p не делится. Чему равно N?

Answer 1

Сумма N натуральных чисел от 1 до N равна 
$\frac{(N+1)N}{2}$
Эта сумма должна делиться на простое число p
т.е. или N делится на p, или N+1 делится на р
но N не делится на p по условию задачи, т.к. N это одно из слагаемых

значит N+1 делится на простое число p
по условию 410<N<420
411<N+1<421
в этом промежутке есть только одно простое число p=419
значит N+1=p=419
N=418

ответ: N=418

Answer 2

Чтобы решить эту задачу, мы можем перебрать все простые числа p и находить такое число n, которое удовлетворяет условию задачи.

Заметим, что сумма всех натуральных чисел от 1 до n равна (n * (n + 1)) / 2. Мы ищем такое n, для которого эта сумма делится на простое число p, но ни одно слагаемое (натуральное число) не делится на p.

Мы можем перебирать простые числа p начиная с 2 и далее. Для каждого p, мы можем находить n по следующему алгоритму:

1. Пусть s = (n * (n + 1)) / 2 - сумма всех натуральных чисел от 1 до n. 2. Если s делится на p, то увеличиваем n на 1 и переходим к следующей итерации. 3. Иначе проверяем каждое слагаемое (натуральное число) от 1 до n на делимость на p. Если хотя бы одно слагаемое делится на p, то увеличиваем n на 1 и переходим к следующей итерации. 4. Если ни одно слагаемое не делится на p, то мы нашли искомое число n, выводим его и завершаем алгоритм.

Используя этот алгоритм, мы можем найти искомое число n. Однако, в данном случае перебор простых чисел и проверка всех слагаемых может потребовать времени. Можно оптимизировать алгоритм, проверяя только слагаемые до корня из полученной суммы.

Пример решения:

Пусть нашим примером будет число p = 3 (первое простое число после 410 и перед 420). Начинаем с n = 411.

Вычисляем сумму s = (411 * 412) / 2 = 84756. Проверяем, делится ли 84756 на 3. Оказывается, что да, поэтому увеличиваем n на 1 и переходим к следующей итерации.

Вычисляем сумму s = (412 * 413) / 2 = 85178. Проверяем, делится ли 85178 на 3. Оказывается, что нет. Проверяем каждое слагаемое от 1 до 412 и обнаруживаем, что 3 делится на 3. Увеличиваем n на 1 и переходим к следующей итерации.

Вычисляем сумму s = (413 * 414) / 2 = 85671. Проверяем, делится ли 85671 на 3. Оказывается, что да, поэтому увеличиваем n на 1 и переходим к следующей итерации.

И так далее...

Далее продолжаем перебирать числа до тех пор, пока не найдем число n, для которого сумма всех натуральных чисел от 1 до n делится на p (3 в данном примере), но ни одно слагаемое не делится на p.