Задача 569
Горная гряда простых чисел

Горная гряда состоит череды гор с уклоном ровно 45° и высотами, описанными простыми числами pn. Подъем k-той горы имеет высоту p2k−1, а ее спуск - p2k. Первые несколько гор этой гряды показаны ниже:

p569-prime-mountain-range.gif

Тенцинг собрался покорить горную гряду, забираясь на каждую гору по очереди, начиная с самой низкой. На каждой вершине он оглядывается и считает, сколько пройденных пиков он может увидеть. В примере выше линия взгляда с третьей горы показана красным цветом - можно заметить, что он способен увидеть только пик второй горы с этой точки обзора. Подобным образом, с 9-й горы он может увидеть три вершины - 5-ю, 7-ю и 8-ю гору.

Пусть P(k) будет количеством вершин, которые видны, глядя назад с k-той горы. Отсюда P(3)=1 и P(9)=3.
Также $\displaystyle \sum_{k=1}^{100} P(k) = 227$.

Найдите $\displaystyle \sum_{k=1}^{2500000} P(k)$.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net