The inversion count of a sequence of digits is the smallest number of adjacent pairs that must be swapped to sort the sequence.
For example, $34214$ has inversion count of $5$:
$34214 \to 32414 \to 23414 \to 23144 \to 21344 \to12344$.
If each digit of a sequence is replaced by one of its divisors a divided sequence is obtained.
For example, the sequence $332$ has $8$ divided sequences: $\{332,331,312,311,132,131,112,111\}$.
Define $G(N)$ to be the concatenation of all primes less than $N$, ignoring any zero digit.
For example, $G(20) = 235711131719$.
Define $F(N)$ to be the sum of the inversion count for all possible divided sequences from the master sequence $G(N)$.
You are given $F(20) = 3312$ and $F(50) = 338079744$.
Find $F(10^8)$. Give your answer modulo $1\,000\,000\,007$.
To solve this problem, we’ll start by implementing a few helper functions.
1. `is_prime(n)`: This function will check if a number `n` is prime.
“`python
def is_prime(n):
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True
```
2. `get_primes(n)`: This function will return a list of all prime numbers less than `n`.
```python
def get_primes(n):
primes = []
for i in range(2, n):
if is_prime(i):
primes.append(i)
return primes
```
3. `inversion_count(sequence)`: This function will calculate the inversion count of a given sequence.
```python
def inversion_count(sequence):
count = 0
for i in range(len(sequence)):
for j in range(i+1, len(sequence)):
if sequence[i] > sequence[j]:
count += 1
return count
“`
4. `divided_sequences(primes)`: This function will generate all possible divided sequences from a list of prime numbers.
“`python
def divided_sequences(primes):
sequences = [list(str(primes[0]))]
for p in primes[1:]:
new_sequences = []
for seq in sequences:
for d in seq:
new_seq = seq[:]
new_seq.append(d)
new_sequences.append(new_seq)
sequences = new_sequences
return sequences
“`
Finally, we can implement the main function `F(N)` to calculate the sum of inversion counts for all possible divided sequences from G(N).
“`python
def F(N):
primes = get_primes(N)
G = ”.join(str(p) for p in primes if p != 0)
sequences = divided_sequences(primes)
total_count = 0
for seq in sequences:
divided_seq = ”.join(str(d) for d in seq)
count = inversion_count(divided_seq)
total_count += count
return total_count % (10**9 + 7)
“`
Now we can compute the answer for F(10^8) by calling `F(10**8)`:
“`python
answer = F(10**8)
print(answer)
“`
More Answers:
Random Connected AreaCircular Logic II
Factors of Two in Binomial Coefficients