Количество пар взаимно простых чисел

[Nikita432472]

Требуется найти количество неупорядоченных пар взаимно простых, натуральных чисел каждое из которых не превосходит N.

$$\sum\limits_{k=1}^{N}\varphi (k) $$

Я так решил, а можно с меньшими вычислениями?

[Nikita432472]

Сама задача (Ломоносов 9 класс, п. б).

Найдите количество натуральных делителей числа 10^40 не представимых в виде m^n, где m и n — натуральные числа, причём n > 1.

Такого вида будут числа
2^k1*5^k2 , где
НОД(k1,k2)=1 , 1<=k1,2<=40 , k1=0 , k2=1 и наоборот.

[Andrey A]

Оформляйте быстрее Latex'ом, а то уволят в карантин.
Формула быстрого вычисления есть для суммы $\sigma ()$ в конце поста http://dxdy.ru/post1048178.html#p1048178. Но я не помню как ее выводил. Попробуйте, может найдется подобная и для $\varphi ()$.

[maxal]

Nikita432472, см. A002088

[Nikita432472]

http://oeis.org/A002088 Нужного не нашел или не понял.