Fleeting Medians

We define two sequences $S = \{S(1), S(2), …, S(n)\}$ and $S_2 = \{S_2(1), S_2(2), …, S_2(n)\}$:
$S(k) = (p_k)^k \bmod 10007$ where $p_k$ is the $k$th prime number.
$S_2(k) = S(k) + S(\lfloor\frac{k}{10000}\rfloor + 1)$ where $\lfloor \cdot \rfloor$ denotes the floor function.
Then let $M(i, j)$ be the median of elements $S_2(i)$ through $S_2(j)$, inclusive. For example, $M(1, 10) = 2021.5$ and $M(10^2, 10^3) = 4715.0$.
Let $F(n, k) = \sum_{i=1}^{n-k+1} M(i, i + k – 1)$. For example, $F(100, 10) = 463628.5$ and $F(10^5, 10^4) = 675348207.5$.
Find $F(10^7, 10^5)$. If the sum is not an integer, use $.5$ to denote a half. Otherwise, use $.0$ instead.

Calculating the given sum requires evaluating a sequence of medians, which involves a significant amount of computation.
Python code that can be used to find the answer:

,,,,,,,,,,,,,,

from sympy import primepi, floor

def S(k):
return pow(primepi(k), k, 10007)

def S_2(k):
return (S(k) + S(floor(k / 10000) + 1)) % 10007

def median(arr):
arr.sort()
n = len(arr)
mid = n // 2
if n % 2 == 0:
return (arr[mid – 1] + arr[mid]) / 2
else:
return arr[mid]

def F(n, k):
result = 0.0
for i in range(1, n – k + 2):
segment = [S_2(i + j – 1) for j in range(k)]
result += median(segment)
return result

n = 10**7
k = 10**5
result = F(n, k)
print(result)

More Answers: