комбинаторика. Нужен быстрый ответ

[Kristobal Hunta]

Сколько пар взаимно простых чисел среди чисел от 1 до N. Нужно в течении часа.

[Echo-Off]

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

[Kristobal Hunta]

Не могли бы вы разъяснить поподробнее. Что такое
\phi(k)

[Echo-Off]

$\varphi(n)$ - количество чисел, меньших $n$ и взаимно-простых с $n$.

[Бодигрим]

$\phi(k)$ - функция Эйлера. Посмотрите http://ru.wikipedia.org/wiki/Функция_Эйлера

Добавлено спустя 3 минуты 32 секунды:

В качестве асимптотической оценки можно использовать

$$3N^2\over\pi^2$$

[Kristobal Hunta]

Спасибо. Разобрался.
В английской wiki как всегда гораздо больше.