Ascending Subsequences

Let $a_i$ be the sequence defined by $a_i=153^i \bmod 10\,000\,019$ for $i \ge 1$.
The first terms of $a_i$ are:
$153, 23409, 3581577, 7980255, 976697, 9434375, \dots$

Consider the subsequences consisting of $4$ terms in ascending order. For the part of the sequence shown above, these are:
$153, 23409, 3581577, 7980255$
$153, 23409, 3581577, 9434375$
$153, 23409, 7980255, 9434375$
$153, 23409, 976697, 9434375$
$153, 3581577, 7980255, 9434375$ and
$23409, 3581577, 7980255, 9434375$.

Define $S(n)$ to be the sum of the terms for all such subsequences within the first $n$ terms of $a_i$. Thus $S(6)=94513710$.
You are given that $S(100)=4465488724217$.

Find $S(10^6)$ modulo $1\,000\,000\,007$.

This problem seems to have come from one of the Project Euler’s mathematics and coding challenges. To solve this, we need to create a function that generates the sequence, a function that generates all subsequences of 4 terms, and a function that adds up these combinations for the first n terms. However, it should be noted that the number of combinations within the first n terms of subsequences is quite high, which means this would be very inefficient for larger n.

Instead, we’ll need to observe patterns and simplify the problem. Here’s an approach we can use:

First, it’s important to note that for this particular sequence, no term repeats within the first $10\,000\,019$ terms because $10\,000\,019$ is a prime number and it has no common factors with $153$ except $1$. This implies that every term in the sequence is unique until it wraps around at the $10\,000\,019$’th term. So for $n \leq 10\,000\,019$, all terms in the sequence are unique, and for $n > 10\,000\,019$, the sequence starts to repeat from the beginning.

Now let’s examine how the problem wants us to add terms: we form subsequences of $4$ terms and add them up. A key feature here is that we’re not adding sequences but subsequences. A subsequence of $4$ terms will always have the terms in ascending order, which is equivalent to all the combinations of $4$ terms for a fully sorted sequence.

This means for each term $a_i$, we can calculate how many times it will be in the first position of the $4$-term subsequence, how many times it will be in the second, third, and fourth positions respectively. We can then multiply the term by the positions’ count and sum them up.

For the $i$’th term $a_i$, it will appear in the first position $(i-1)*(i-2)*(i-3)/6$, in the second position $(i-1)*(i-2)*(n-i+1)/6$, in the third position $(i-1)*(n-i+1)*(n-i+2)/6$, and in the fourth position $(n-i+1)*(n-i+2)*(n-i+3)/6$ times.

We can use these formulas to calculate the sum for each term, then sum them all up. Be sure to take the modulus $1\,000\,000\,007$ where necessary to prevent overflow and get the result in the correct range.

Here’s a Pythonic pseudocode implementation of the above approach:

“`python
MOD = 1000000007
a = 153
total_sum = 0

for i in range(1, n+1):
ai = pow(a, i, 10000019) # Calculate ai using mod 10000019

# Calculate position counts and multiply by ai
sum_term = (ai * (((i-1)*(i-2)*(i-3)//6
+ (i-1)*(i-2)*(n-i+1)//6
+ (i-1)*(n-i+1)*(n-i+2)//6
+ (n-i+1)*(n-i+2)*(n-i+3)//6)) % MOD) % MOD

total_sum = (total_sum + sum_term) % MOD # Add to total sum

print(total_sum) # Print final sum
“`

This approach is much more efficient and enables calculation of `S(10^6)` in reasonable time. You can easily translate this pseudocode into your preferred programming language.

If you want to take into account the repetition after $10\,000\,019$ terms for larger n, you would need to add an additional calculation for n > $10\,000\,019$ calculating the sum for n = $10\,000\,019$ and then multiplying this by the quotient $n/10\,000\,019$ and adding the sum for the residual.

Please note that this method can be mathematically complex and requires a good understanding of number theory and combinatorics.

More Answers: