Detailed mathematical approach

Problem Summary

For a positive integer \(n\), let \(a=\sqrt{n}\) and define a recursion by

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

The quantity of interest is \(G(n)=g_a(n)\) with \(a=\sqrt n\). Problem 517 asks for

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

A naive recursive evaluation would branch explosively, so the solution turns the recursion into a direct combinatorial formula and then evaluates that formula for every prime in the interval.

Mathematical Approach

The key observation is that every recursive branch corresponds to a sequence of jumps of size \(1\) and \(\sqrt n\). Counting leaves of the recursion tree is therefore the same as counting valid ordered jump patterns.

Step 1: Interpret the Recursion as Ordered Jumps

Start with remainder \(x=n\). Every recursive call replaces \(x\) by either \(x-1\) or \(x-\sqrt n\), and the branch stops as soon as the new remainder is \(<\sqrt n\).

Thus each leaf is an ordered sequence of two move types:

$1\text{-step}: x\mapsto x-1,\qquad \sqrt n\text{-step}: x\mapsto x-\sqrt n.$

If a branch uses \(k\) steps of size \(\sqrt n\), then automatically

$k\sqrt n\le n,$

so only

$0\le k\le \left\lfloor\sqrt n\right\rfloor$

can contribute.

Step 2: Record Where the \(\sqrt n\)-Steps Occur

Fix a branch using exactly \(k\) steps of size \(\sqrt n\). For \(r=1,\dots,k\), let \(s_r\) be the number of \(1\)-steps that have already occurred before the \(r\)-th \(\sqrt n\)-step is taken.

These numbers satisfy

$0\le s_1\le s_2\le \cdots \le s_k,$

because the total number of \(1\)-steps seen so far can only increase.

Before taking the \(r\)-th \(\sqrt n\)-step, the current remainder is

$n-s_r-(r-1)\sqrt n.$

That step is legal only if the recursion has not stopped yet, namely if this remainder is at least \(\sqrt n\). Therefore

$n-s_r-(r-1)\sqrt n\ge \sqrt n,$

so

$s_r\le n-r\sqrt n.$

Since \(s_r\) is an integer, this becomes

$s_r\le \left\lfloor n-r\sqrt n\right\rfloor.$

For prime \(n\), the number \(\sqrt n\) is irrational, hence \(r\sqrt n\notin \mathbb Z\) for every \(r\ge1\), and we may rewrite the bound as

$s_r\le n-\left\lceil r\sqrt n\right\rceil.$

Because these upper bounds decrease as \(r\) increases, the single strongest condition is the last one:

$s_k\le T_k:=n-\left\lceil k\sqrt n\right\rceil.$

Step 3: Turn the Branch into a Multiset Count

Once the nondecreasing \(k\)-tuple \((s_1,\dots,s_k)\) is fixed, the whole branch is determined:

take \(s_1\) steps of size \(1\), then one step of size \(\sqrt n\); then \(s_2-s_1\) more \(1\)-steps, then another \(\sqrt n\)-step; continue in the same way until the \(k\)-th \(\sqrt n\)-step; after that, only \(1\)-steps remain until the remainder drops below \(\sqrt n\).

Conversely, every leaf with exactly \(k\) steps of size \(\sqrt n\) produces exactly one such tuple. So the problem is now:

How many tuples satisfy

$0\le s_1\le s_2\le \cdots \le s_k\le T_k\ ?$

This is the classical count of multisets of size \(k\) chosen from \(T_k+1\) values. Hence

$\#\{\text{branches with exactly }k\text{ }\sqrt n\text{-steps}\}=\binom{T_k+k}{k}.$

Substituting \(T_k=n-\lceil k\sqrt n\rceil\) gives

$\binom{n-\lceil k\sqrt n\rceil+k}{k}.$

Step 4: Sum over All Possible Values of \(k\)

Adding the contributions of all admissible \(k\) yields

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

This is the closed form used by the implementations. It replaces an exponential recursion tree with only \(O(\sqrt n)\) binomial terms.

Notice that the term for \(k=0\) is

$\binom{n}{0}=1,$

which corresponds to the unique branch that uses only \(1\)-steps until the stopping condition is reached.

Step 5: Prepare the Formula for Modular Computation

The required modulus is

$M=10^9+7,$

which is prime. Therefore each binomial coefficient can be evaluated as

$\binom{m}{k}\equiv m!\,(k!)^{-1}\,((m-k)!)^{-1}\pmod M.$

After factorials and inverse factorials have been precomputed once, every summand of \(G(n)\) is obtained in constant time.

The overall Project Euler sum is then

$\sum_{\substack{10^7<p<10^7+10^4\\ p\text{ prime}}}\ \sum_{k=0}^{\lfloor\sqrt p\rfloor}\binom{p-\lceil k\sqrt p\rceil+k}{k}\pmod M.$

Worked Example: \(n=5\)

Here \(a=\sqrt5\approx 2.236\), so \(k\) can only be \(0\), \(1\), or \(2\).

For \(k=0\), the contribution is

$\binom{5}{0}=1.$

This is the single branch that repeatedly subtracts \(1\):

$5\to 4\to 3\to 2,<\sqrt5.$

For \(k=1\), we have

$T_1=5-\lceil \sqrt5\rceil=5-3=2,$

so \(s_1\) can be \(0\), \(1\), or \(2\). That gives the three branches

$\sqrt5,1;\qquad 1,\sqrt5;\qquad 1,1,\sqrt5,$

hence the contribution

$\binom{2+1}{1}=3.$

For \(k=2\),

$T_2=5-\lceil 2\sqrt5\rceil=5-5=0,$

so only \((s_1,s_2)=(0,0)\) is possible, corresponding to the branch

$\sqrt5,\sqrt5,$

and the contribution is

$\binom{0+2}{2}=1.$

Therefore

$G(5)=1+3+1=5.$

How the Code Works

The C++, Python, and Java implementations all follow the same pipeline.

First, they precompute factorials and inverse factorials modulo \(10^9+7\) up to the largest integer that can appear in a binomial coefficient. This makes each later combination lookup constant time.

Next, they generate all primes in the interval \(10^7<p<10^7+10^4\) with a segmented sieve. Because the window width is only \(10^4\), this is much cheaper than sieving the entire range from \(1\) up to \(10^7+10^4\).

For each prime \(p\), the implementation loops over

$0\le k\le \lfloor\sqrt p\rfloor$

and evaluates the summand

$\binom{p-\lceil k\sqrt p\rceil+k}{k}\pmod{10^9+7}.$

The only delicate quantity is \(\lceil k\sqrt p\rceil\). Rather than simulating the original real recursion, the implementations compute this ceiling numerically from \(\sqrt{k^2p}\), then form the corresponding binomial term and add it to \(G(p)\).

Finally, all prime contributions are accumulated modulo \(10^9+7\) to produce the required answer.

Complexity Analysis

Let \(U=10^7+10^4-1\), let \(W=10^4\) be the width of the prime interval, and let \(P\) be the number of primes in that interval.

Precomputing factorials and inverse factorials up to \(U\) costs \(O(U)\) time and \(O(U)\) memory. The segmented sieve needs only the base primes up to \(\sqrt U\), so prime generation over the target window is roughly \(O(\sqrt U\log\log U+W\log\log U)\) time and \(O(W)\) extra memory.

For each prime \(p\), evaluating \(G(p)\) requires \(\lfloor\sqrt p\rfloor+1\) summands, so that phase costs \(O(\sqrt p)\) per prime. Overall the running time is therefore

$O\!\left(U+P\sqrt U\right),$

with memory dominated by the factorial tables:

$O(U).$

Footnotes and References

1. Problem page: https://projecteuler.net/problem=517
2. Binomial coefficient: Wikipedia — Binomial coefficient
3. Stars and bars / multiset counting: Wikipedia — Stars and bars
4. Segmented sieve: Wikipedia — Segmented sieve
5. Modular inverse and Fermat's little theorem: Wikipedia — Fermat's little theorem