Минимальное количество НОДов для пары (k, 2k^2-1)

[kthxbye]

Пусть разрешено складывать, отнимать, находить НОД пары чисел и проверять равенство (все это в любой последовательности). Требуется проверить является ли пара нечетных чисел $(k,2k^2-1)$ парой простых чисел.

Какое минимальное количество НОДов необходимо вычислить, чтобы гарантированно это определить? К слову, имеется гипотетически верный алгоритм, который требует ровно $2k$ НОДов. Можно ли улучшить этот результат?

[mihiv]

Не совсем понятно, что требуется.
Можно, например, найти НОДы числа $k$ и первых $\sqrt k$ натуральных чисел, аналогично для числа $2k^2-1$. Всего наберется меньше $2k$.

[kthxbye]

mihiv, вы абсолютно правы. Хорошее замечание. Ну и еще можно проверять только нечетные больше единицы.

А вопрос навеян вот этим.