Сколько существует натуральных чисел N, которые меньше 1000, для которых 2^N-N делиться...

Question

Сколько существует натуральных чисел N, которые меньше 1000, для которых 2^N-N делиться на 7?
Можно в виде кода на языках программирования

Answer 1

Заметим, что 2^3 = 8 дает такой же остаток от деления на 7, что и 2^0, Тогда последовательность остатков 2^n от деления на 7 периодична с периодом 3. При 0 <= n < 3 2^n < 7, поэтому можно просто проверить, что 2^(n%3) совпадает с остатком от деления n на 7.<br>
PascalABC.NET 3.2:
begin
  print(1.To(999).Where(n->power(2, n mod 3) = n mod 7).Count)
end.

Comments

А будет это работать, в моем случае, у меня же 2^N - N

---

Почему должно не работать? Возьмем, например, 578. 2^578 = (2^3)^192 * 2^2 дает остаток 4 при делении на 7, т.к. 2^3 дает остаток 1 при делении на 7. 578 тоже дает остаток 4 при делении на 7, значит, 2^578 - 578 дает остаток 4 - 4 = 0 при делении на 7, т.е. делится на 7.

---

На досуге можно проверить, что 2^578 - 578 = 989321605892418136242010084078588760140525396404847359656252224371588900426127468681265604244972179958390685704064557357405460137227004839870184620407572671666427088594795966
действительно делится на 7.

---

Да, Спасибо