Substring Sums of Prime Concatenations

Let $S(n)$ be the sum of all contiguous integer-substrings that can be formed from the integer $n$. The substrings need not be distinct.
For example, $S(2024) = 2 + 0 + 2 + 4 + 20 + 02 + 24 + 202 + 024 + 2024 = 2304$.
Let $P(n)$ be the integer formed by concatenating the first $n$ primes together. For example, $P(7) = 2357111317$.
Let $C(n, k)$ be the integer formed by concatenating $k$ copies of $P(n)$ together. For example, $C(7, 3) = 235711131723571113172357111317$.
Evaluate $S(C(10^6, 10^{12})) \bmod (10^9 + 7)$.

To solve this problem, we will break it down into smaller steps and implement each step using Python code. Here’s a step-by-step solution:

Step 1: Generating Prime Numbers
First, we need a way to generate prime numbers. We can use the Sieve of Eratosthenes algorithm to efficiently generate all prime numbers up to a given limit.

“`python
def generate_primes(limit):
is_prime = [True] * (limit + 1)
is_prime[0] = is_prime[1] = False

for i in range(2, int(limit ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, limit + 1, i):
is_prime[j] = False

primes = [i for i in range(limit + 1) if is_prime[i]]
return primes
“`

Step 2: Concatenating Primes
Next, we need a function to concatenate the first `n` primes together.

“`python
def concatenate_primes(n, primes):
concatenated = “”
for i in range(n):
concatenated += str(primes[i])
return int(concatenated)
“`

Step 3: Concatenating Prime Multiples
We also need a function to concatenate `k` copies of the first `n` primes together.

“`python
def concatenate_prime_multiples(n, k, primes):
concatenated = “”
for i in range(k):
concatenated += str(concatenate_primes(n, primes))
return int(concatenated)
“`

Step 4: Finding Contiguous Integer-Substrings
To find all contiguous integer-substrings, we can convert the number to a string and iterate through all possible substrings.

“`python
def find_integer_substrings(num):
num_str = str(num)
substrings = []

for i in range(len(num_str)):
for j in range(i + 1, len(num_str) + 1):
substr = int(num_str[i:j])
substrings.append(substr)

return substrings
“`

Step 5: Summing the Integer-Substrings
Finally, we can sum all the integer-substrings and calculate the modulo.

“`python
def sum_integer_substrings(num):
substrings = find_integer_substrings(num)
return sum(substrings) % (10**9 + 7)
“`

Putting it all together:
To solve the given problem, we can call the above functions with appropriate arguments.

“`python
primes = generate_primes(10**6)
result = sum_integer_substrings(concatenate_prime_multiples(10**6, 10**12, primes))
print(result)
“`

Note: The code provided above assumes that the `generate_primes` function is given the limit as $10^6$, corresponding to the number of primes required for the calculation. However, the algorithm and code are applicable for any positive integer `limit`. Also, be aware that the code above may take a considerable amount of time to execute due to the large values involved.

More Answers: