(2^n-1,3^n+2)=1

[rightways]

Найдите наименьшее натуральное число $n$ для которого $НОД(2^n-1,3^n+2)>1$

[Sirion]

Со второго раза смог правильно посчитать программно (в первый раз незаметно для себя словил целочисленное переполнение).

(Оффтоп)

176

[rightways]

И какой же у них нод?

[Sirion]

(Оффтоп)

257, если я не ошибаюсь.

[VAL]

Все верно.
Но не ясно, в чем олимпиадность и математичность задачи.
15 секунд на написание программы и сотые доли на исполнение:

> for n do d:=igcd(2^n-1,3^n+2): if d>1 then print(n,d): break fi od:
                               176, 257

[Sirion]

VAL в сообщении #1103758 писал(а):

Все верно.
Но не ясно, в чем олимпиадность и математичность задачи.
15 секунд на написание программы и сотые доли на исполнение:

Ну, это смотря на чём писать. У меня под рукой был только браузер, так что минут пять на поиск js-библиотеки для длинной арифметики, ещё минут пять на написание самой программы (gcd пришлось писать руками). А посчиталось да, стремительно.

[Deggial]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Помогите решить / разобраться (М)»
Причина переноса: не указана.