Prime Mountain Range

A mountain range consists of a line of mountains with slopes of exactly $45^\circ$, and heights governed by the prime numbers, $p_n$. The up-slope of the $k$th mountain is of height $p_{2k – 1}$, and the downslope is $p_{2k}$. The first few foot-hills of this range are illustrated below.

Tenzing sets out to climb each one in turn, starting from the lowest. At the top of each peak, he looks back and counts how many of the previous peaks he can see. In the example above, the eye-line from the third mountain is drawn in red, showing that he can only see the peak of the second mountain from this viewpoint. Similarly, from the $9$th mountain, he can see three peaks, those of the $5$th, $7$th and $8$th mountain.
Let $P(k)$ be the number of peaks that are visible looking back from the $k$th mountain. Hence $P(3)=1$ and $P(9)=3$.
Also $\displaystyle \sum_{k=1}^{100} P(k) = 227$.
Find $\displaystyle \sum_{k=1}^{2500000} P(k)$.

To solve this problem, we need to determine the function `P(k)` that counts the number of visible peaks from the `k`th mountain. We can then sum up the values of `P(k)` for `k` ranging from 1 to 2,500,000.

To determine the visibility of the peaks, we need to iterate through the mountains and check if the current mountain is higher than any previous mountain.

Here’s a possible approach to solving this problem in Python:

Step 1: Generate a list of prime numbers up to a certain limit. We can use the sieve of Eratosthenes algorithm to efficiently generate the prime numbers.

“`python
def sieve_of_eratosthenes(n):
primes = [True] * (n + 1)
primes[0] = primes[1] = False

for p in range(2, int(n**0.5) + 1):
if primes[p]:
for i in range(p * p, n + 1, p):
primes[i] = False

return [p for p, is_prime in enumerate(primes) if is_prime]
“`

Step 2: Generate a list of mountains using the prime numbers. Each mountain is represented as a tuple of its up-slope and downslope heights.

“`python
def generate_mountains(primes):
mountains = []
for i in range(len(primes) // 2):
up_slope = primes[2 * i]
down_slope = primes[2 * i + 1]
mountains.append((up_slope, down_slope))
return mountains
“`

Step 3: Implement the `P(k)` function to count the number of visible peaks.

“`python
def count_visible_peaks(mountains, k):
visible_peaks = 0
max_height = 0

for i in range(k):
up_slope, down_slope = mountains[i]

if up_slope > max_height:
visible_peaks += 1
max_height = up_slope

if down_slope > max_height:
visible_peaks += 1
max_height = down_slope

return visible_peaks
“`

Step 4: Compute the sum of `P(k)` for `k` ranging from 1 to 2,500,000.

“`python
primes = sieve_of_eratosthenes(5000000) # Generate prime numbers up to a higher limit
mountains = generate_mountains(primes)

total_visible_peaks = sum([count_visible_peaks(mountains, k) for k in range(1, 2500001)])
print(total_visible_peaks)
“`

This code should output the sum of `P(k)` for `k` ranging from 1 to 2,500,000.

Note: This code may take some time to execute since it involves calculating prime numbers and performing a large number of iterations. You can optimize the code further if needed by using dynamic programming to store intermediate results of `P(k)` to avoid redundant calculations.

More Answers: