Ваш заявленный интерес к парным числам (a, b).Беззаботная пара добавляет дополнительное ограничение, что a без квадратов.Следовательно, это не та же проблема, хотя некоторые математические функции похожи.Насколько я понимаю вашу проблему, это эквивалентно суммированию totient-функции Эйлера от 1 до n, так называемой Totient Summatory Function .
Я не знаю ни одного трюка, который дает одинпростое решение в закрытой форме, чтобы придумать ответ.Тем не менее, я думаю, что изменение простого сита Эратосфена (SoT) должно дать вам ответ менее чем за 10 секунд на большинстве языков программирования.
При нормальном запуске SoT просто получаетсясписок простых чисел <= n.Однако наша цель изменится на вычисление полной факторизации по простым степеням для каждого целого числа от 1 до n включительно.Чтобы сделать это, мы должны хранить более одного бита информации для каждой записи сита, мы должны хранить список.Просеивая простое число p через массив, мы добавляем (p, 1) в список, уже сохраненный в этой записи.Затем мы просеиваем по p <sup>2 и меняем (p, 1) записей в каждом месте, к которому мы попадаем, на (p, 2), и поэтому по одному для каждой степени p <= n и каждого p <= n,Когда он завершится, вы можете быстро вычислить функцию Totient для каждого значения 0 <= x <= n и суммировать их. </s>
РЕДАКТИРОВАТЬ:
Я вижу, что уже есть гораздо лучший наборответов на вопрос на math.stackexchange.com здесь .Я оставлю этот ответ на некоторое время, пока решение вопроса не будет решено.