Detailed mathematical approach

Problem Summary

For positive integers \(m\), \(k\), and \(s\), define the generalized McCarthy function

$M_{m,k,s}(n)=\begin{cases}n-s,&n>m,\\M_{m,k,s}\!\left(M_{m,k,s}(n+k)\right),&n\le m.\end{cases}$

For each pair \(1\le s<k\le p\), we look at all fixed points \(n\) satisfying \(M_{m,k,s}(n)=n\), and we add those fixed points to the global total. The task is therefore to compute

$S(p,m)=\sum_{1\le s<k\le p}\ \sum_{\substack{n\in\mathbb{Z}\\ M_{m,k,s}(n)=n}} n$

for very large parameters. Directly expanding the recursion for every \((k,s)\) would be hopeless, so the solution first characterizes exactly when fixed points exist and what interval they form.

Mathematical Approach

The implementations are based on turning the recursion into a divisibility problem. Once that is done, the answer becomes a single \(O(p)\) summation.

Step 1: Introduce the gap \(g=k-s\)

Set

$g=k-s.$

Because the problem only considers \(s<k\), we always have \(g>0\). The key identity is that for every \(n\le m\),

$M_{m,k,s}(n)=M_{m,k,s}(n+g).$

Why is this true? If \(n+k>m\), then the inner call is already in the base case:

$M_{m,k,s}(n+k)=n+k-s=n+g,$

so indeed \(M_{m,k,s}(n)=M_{m,k,s}(n+g)\).

If \(n+k\le m\), we apply the same statement to the larger argument \(n+k\) and obtain

$M_{m,k,s}(n+k)=M_{m,k,s}(n+k+g).$

Substituting this into the recursion gives

$M_{m,k,s}(n)=M_{m,k,s}\!\left(M_{m,k,s}(n+k)\right)=M_{m,k,s}\!\left(M_{m,k,s}(n+k+g)\right)=M_{m,k,s}(n+g).$

So below the threshold \(m\), each recursive layer effectively shifts the argument upward by exactly \(g\).

Step 2: Closed form below the threshold

Take some \(n\le m\), and let \(q\) be the smallest positive integer such that

$n+qg>m.$

Equivalently,

$q=\left\lfloor\frac{m-n}{g}\right\rfloor+1.$

Repeatedly applying the shift identity from Step 1 gives

$M_{m,k,s}(n)=M_{m,k,s}(n+qg).$

Now the argument \(n+qg\) is above \(m\), so the base rule applies and yields

$M_{m,k,s}(n)=n+qg-s.$

This explicit formula is the turning point of the whole solution: the nested recursion disappears, replaced by a simple linear expression once \(q\) is known.

Step 3: Determine exactly when fixed points exist

A fixed point satisfies \(M_{m,k,s}(n)=n\). Using the closed form above, this means

$n+qg-s=n,$

so

$qg=s.$

Therefore fixed points exist if and only if \(g\) divides \(s\). When that happens, \(q=s/g\), and the minimality condition on \(q\) becomes

$n+(q-1)g\le m<n+qg.$

Substituting \(q=s/g\) gives

$m-s<n\le m-s+g.$

Hence the complete set of fixed points is the interval

$\{m-s+1,\ m-s+2,\ \dots,\ m-s+g\},$

and its length is exactly \(g=k-s\). If \(g\nmid s\), there are no fixed points at all.

Step 4: Reparameterize valid pairs by \((g,t)\)

Whenever \(g\mid s\), write

$s=g(t-1),\qquad k=s+g=gt,$

with \(t\ge 2\). The bound \(k\le p\) becomes

$2\le t\le \left\lfloor\frac{p}{g}\right\rfloor.$

This change of variables is exactly what the implementations use. Instead of iterating over all pairs \((k,s)\), they iterate over the gap \(g\) and over the quotient \(t=k/g\). Every valid pair appears once, and every invalid pair disappears automatically because the divisibility condition is already built in.

Step 5: Sum the fixed-point interval for one valid pair

For a valid pair, the fixed points form the arithmetic interval

$m-s+1,\ m-s+2,\ \dots,\ m-s+g.$

Its sum is

$\sum_{r=1}^{g}(m-s+r)=g(m-s)+\frac{g(g+1)}{2}.$

Substitute \(s=g(t-1)\):

$\Sigma(g,t)=g\bigl(m-g(t-1)\bigr)+\frac{g(g+1)}{2}.$

After rearranging, this becomes

$\Sigma(g,t)=g(m+g+1)+\frac{g(g-1)}{2}-g^2t.$

This is the exact per-pair contribution accumulated by the three implementations.

Step 6: Collapse all pairs with the same gap

For a fixed \(g\), define

$T=\left\lfloor\frac{p}{g}\right\rfloor.$

Then \(t\) runs through the consecutive interval \(2,3,\dots,T\). Therefore

$S(p,m)=\sum_{g=1}^{p}\ \sum_{t=2}^{\lfloor p/g\rfloor}\left(g(m+g+1)+\frac{g(g-1)}{2}-g^2t\right).$

Now the inner sum is just arithmetic-series algebra. Since

$\#\{2,\dots,T\}=T-1,\qquad \sum_{t=2}^{T} t=\frac{T(T+1)}{2}-1,$

the contribution of one \(g\) is

$\begin{aligned} &(T-1)\,g(m+g+1)+(T-1)\,\frac{g(g-1)}{2}\\ &\qquad -g^2\left(\frac{T(T+1)}{2}-1\right). \end{aligned}$

This is why the final program needs only one loop over \(g\), with constant-time arithmetic inside that loop.

Worked Example: \((p,m)=(10,10)\)

The value \(S(10,10)\) is a useful checkpoint. We group terms by \(g\):

$\begin{aligned} g=1&:&&10+9+8+7+6+5+4+3+2=54,\\ g=2&:&&19+15+11+7=52,\\ g=3&:&&27+18=45,\\ g=4&:&&34,\\ g=5&:&&40. \end{aligned}$

For \(g\ge 6\), we have \(\lfloor 10/g\rfloor<2\), so there are no valid pairs. Summing the nonzero groups gives

$54+52+45+34+40=225,$

which matches the implementation checkpoint.

How the Code Works

The C++, Python, and Java implementations all follow the grouped formula from Step 6. They iterate \(g\) from \(1\) to \(p\), compute

$T=\left\lfloor\frac{p}{g}\right\rfloor,$

and skip the iteration when \(T<2\), because then no valid \(t\) exists. Otherwise they evaluate the closed form for the whole block \(t=2,\dots,T\): one factor counts how many terms there are, one factor supplies the arithmetic-series sum of \(t\), and the three resulting pieces are combined into the contribution for that \(g\).

No recursion is executed at runtime. The implementations work entirely with the derived summation formula. Python relies on arbitrary-precision integers automatically, Java uses arbitrary-precision integer arithmetic for the running total, and C++ accumulates in unsigned 128-bit arithmetic and converts the final value to decimal text for output.

Complexity Analysis

The loop over \(g\) runs exactly \(p\) times, and each iteration performs only \(O(1)\) arithmetic. Therefore the total running time is \(O(p)\), and the auxiliary memory usage is \(O(1)\). This is a dramatic improvement over trying to analyze each recursive function instance separately.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=555
2. McCarthy 91 function: Wikipedia — McCarthy 91 function
3. Fixed point: Wikipedia — Fixed point
4. Arithmetic progression: Wikipedia — Arithmetic progression
5. Divisibility: Wikipedia — Divisor