Solution

Answer: 581468882

Let $a>1$ be irrational (this is true for $a=\sqrt p$ when $p$ is prime).

We are given

$$g_a(x)= \begin{cases} 1,&x<a,\ g_a(x-1)+g_a(x-a),&x\ge a. \end{cases}$$

We must compute

$$G(n)=g_{\sqrt n}(n),$$

and finally

$$\sum_{\substack{p\text{ prime}\10^7<p<10010000}} G(p)\pmod{10^9+7}.$$

1. Mathematical analysis

1.1 Combinatorial interpretation

The recurrence

$$g(x)=g(x-1)+g(x-a)$$

is analogous to counting paths using steps of lengths $1$ and $a$.

Because $a$ is irrational, every number of the form

$$m+na$$

has a unique representation. This removes all ambiguity in the recursion tree.

Define:

$k$ = number of $a$-steps,
$j$ = number of $1$-steps.

Then the total length is

$$j+ka.$$

For fixed $k$, the condition

$$j+ka\le x$$

becomes

$$j\le \lfloor x-ka\rfloor.$$

For each admissible $j$, the number of sequences containing:

$k$ copies of $a$,
$j$ copies of $1$,

$$\binom{j+k}{k}.$$

Therefore

$$g_a(x)= \sum_{k\ge0}\sum_{j=0}^{\lfloor x-ka\rfloor}\binom{j+k}{k}.$$

Now use the hockey-stick identity:

$$\sum_{j=0}^{m}\binom{j+k}{k} = \binom{m+k+1}{k+1}.$$

Hence

$$g_a(x) = \sum_{k\ge0} \binom{\lfloor x-ka\rfloor+k+1}{k+1}.$$

Reindexing with $k\mapsto k-1$:

$$\boxed{ g_a(x)= \sum_{k\ge0} \binom{\lfloor x-ka\rfloor+k}{k} }.$$

1.2 Formula for $G(n)$

Set $a=\sqrt n$, $x=n$:

$$\boxed{ G(n)= \sum_{k=0}^{\lfloor\sqrt n\rfloor} \binom{\lfloor n-k\sqrt n\rfloor+k}{k} }.$$

The problem gives

$$G(90)=7564511.$$

Checking:

$$G(90) = \sum_{k=0}^{9} \binom{\lfloor 90-k\sqrt{90}\rfloor+k}{k} = 7564511,$$

so the formula is correct.

2. Efficient modular computation

We need all primes

$$10^7<p<10010000.$$

There are only a few hundred of them, and for each prime $p$,

$$k\le \lfloor\sqrt p\rfloor \approx 3162.$$

So the total number of binomial evaluations is only about $2\times10^6$.

We compute all binomial coefficients modulo

$$M=10^9+7$$

using factorials and inverse factorials.

3. Python implementation

import math

MOD = 1_000_000_007

LOW = 10_000_000
HIGH = 10_010_000

# ------------------------------------------------------------
# Segmented sieve for primes in (LOW, HIGH)
# ------------------------------------------------------------

limit = int(math.isqrt(HIGH)) + 1

base = [True] * (limit + 1)
base[0] = base[1] = False

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

small_primes = [i for i, v in enumerate(base) if v]

seg = [True] * (HIGH - LOW)

for p in small_primes:
    start = max(p * p, ((LOW + p - 1) // p) * p)
    for x in range(start, HIGH, p):
        seg[x - LOW] = False

primes = [LOW + i for i, v in enumerate(seg) if v and LOW + i > LOW]

# ------------------------------------------------------------
# Precompute factorials modulo MOD
# ------------------------------------------------------------

N = HIGH + 5000

fact = [1] * (N + 1)

for i in range(1, N + 1):
    fact[i] = fact[i - 1] * i % MOD

invfact = [1] * (N + 1)

invfact[N] = pow(fact[N], MOD - 2, MOD)

for i in range(N, 0, -1):
    invfact[i - 1] = invfact[i] * i % MOD

def C(n, r):
    """Compute nCr modulo MOD."""
    if r < 0 or r > n:
        return 0
    return fact[n] * invfact[r] % MOD * invfact[n - r] % MOD

# ------------------------------------------------------------
# Compute G(p)
# ------------------------------------------------------------

def G(p):
    a = math.sqrt(p)

    total = 0

    for k in range(int(a) + 1):
        n = math.floor(p - k * a) + k
        total = (total + C(n, k)) % MOD

    return total

answer = 0

for p in primes:
    answer = (answer + G(p)) % MOD

print(answer)

4. Code walkthrough

Prime generation

We use a segmented sieve:

first sieve all primes up to $\sqrt{10010000}$,
then mark composites in the interval.

This efficiently produces all primes in the target range.

Factorials

We precompute:

$$n!,\quad (n!)^{-1}\pmod M$$

so that

$$\binom{n}{r} = \frac{n!}{r!(n-r)!} \pmod M$$

can be evaluated in constant time.

Computing $G(p)$

For each prime $p$:

for k in range(int(a) + 1):

because $k\sqrt p \le p$ implies $k\le\sqrt p$.

Then:

n = floor(p - k*sqrt(p)) + k

and the contribution is

C(n, k)

exactly matching the derived formula.

5. Verification

The derived identity reproduces the sample: