Detailed mathematical approach

Problem Summary

Define \(g(n)\) as follows: starting from \(n\), repeatedly divide by \(7\) when possible; otherwise add \(1\), and count only those \(+1\) operations. The problem asks for the large cumulative quantity

$F(N)=\sum_{m=1}^{N} g(m),\qquad H(k)=F\left(\frac{7^k-1}{11}\right)\pmod{M},\qquad M=1{,}117{,}117{,}717.$

The required value is \(H(10^9)\). A direct simulation is impossible because the upper limit \(\frac{7^k-1}{11}\) is astronomically large, so the solution rewrites the process in base \(7\), turns it into a constant-size linear update, and then exploits the repeating digit pattern of \(\frac{1}{11}\) in base \(7\).

Mathematical Approach

Step 1: Rewrite the primitive rule

If \(n=7a+r\) with \(0\le r\le 6\), then one application of the rule gives

$g(7a)=g(a),\qquad g(7a+r)=7-r+g(a+1)\quad (1\le r\le 6).$

The second formula says that when the last base-\(7\) digit is \(r\neq 0\), we need exactly \(7-r\) increments to reach the next multiple of \(7\), after which the number becomes \(a+1\).

Step 2: Shift by one and obtain a digit formula

Introduce

$f(n)=g(n+1).$

For every positive \(n=7a+d\) with \(0\le d\le 6\), the previous recurrence becomes

$f(7a+d)=f(a)+6-d,\qquad f(0)=0.$

Repeatedly stripping the last base-\(7\) digit shows that if \(n=(d_m d_{m-1}\cdots d_0)_7\) is positive, then

$f(n)=\sum_{i=0}^{m}(6-d_i).$

So \(g(n+1)\) is just a weighted digit sum. For example, \(124=(235)_7\), hence

$g(125)=f(124)=(6-2)+(6-3)+(6-5)=4+3+1=8,$

which matches the small checkpoint used by the implementations.

Step 3: Derive a recurrence for the cumulative sum

Now define the prefix sum

$F(N)=\sum_{m=1}^{N} g(m)=\sum_{n=0}^{N-1} f(n).$

For a positive prefix \(n\) and a next base-\(7\) digit \(d\), split the range \(0\le x<7n+d\) into full blocks \(7a,7a+1,\dots,7a+6\) for \(0\le a<n\) and one partial block for \(a=n\). This yields

$F(7n+d)=7F(n)+21n-6+d\,f(n)+P(d),$

where

$P(d)=\sum_{x=0}^{d-1}(6-x)=\frac{d(13-d)}{2}.$

The term \(-6\) is the only correction needed for the special value \(f(0)=0\); otherwise the full-block contribution would be completely uniform.

Step 4: Encode the update as a \(5\times 5\) matrix

For positive \(n\), use the augmented state

$\mathbf{v}(n)=\begin{pmatrix}1\\ n-1\\ F(n)\\ f(n)\\ 1\end{pmatrix}.$

Then appending one digit \(d\in\{0,\dots,6\}\) corresponds to \(n\mapsto 7n+d\), and the state evolves linearly:

$\mathbf{v}(7n+d)=M_d\,\mathbf{v}(n),$

with

$M_d=\begin{pmatrix} 1 & 0 & 0 & 0 & 0\\ 6 & 7 & 0 & 0 & d\\ 15 & 21 & 7 & d & P(d)\\ 0 & 0 & 0 & 1 & 6-d\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \pmod{M}.$

This is the exact matrix family used by the C++, Python, and Java implementations.

Step 5: Exploit the special upper limit \(\frac{7^k-1}{11}\)

Because \(11\mid 7^{10}-1\), we have a purely periodic base-\(7\) expansion for \(\frac{1}{11}\), and in particular

$\frac{7^{10}-1}{11}=(431162355)_7.$

For \(k=10t\),

$\frac{7^k-1}{11}=\frac{7^{10}-1}{11}\left(1+7^{10}+7^{20}+\cdots+7^{10(t-1)}\right).$

Therefore its base-\(7\) digits are the block 4311623550 repeated \(t-1\) times, followed by 431162355. Since every such number begins with the digit \(4\), the implementations start directly from the state

$\mathbf{v}(4)=\begin{pmatrix}1\\ 3\\ 12\\ 2\\ 1\end{pmatrix},$

which already stores \(4-1\), \(F(4)=12\), and \(f(4)=2\).

Worked Example

A small local check comes from appending the digit \(3\) to the prefix \(4\), giving \(43_7=31\). Using \(F(4)=12\), \(f(4)=2\), and \(P(3)=15\),

$F(31)=7\cdot 12+21\cdot 4-6+3\cdot 2+15=183.$

So the recurrence already reproduces \(\sum_{m=1}^{31} g(m)=183\). For the first nontrivial target, \(k=10\), the upper limit is \((431162355)_7\). Starting from \(\mathbf{v}(4)\) and processing the remaining suffix 31162355 gives

$H(10)=690409338 \pmod{M},$

exactly the checkpoint embedded in the implementations.

How the Code Works

The implementations precompute the seven digit-dependent matrices \(M_0,\dots,M_6\), always working modulo \(M\). They also precompute the transformations of the few fixed digit strings that appear in the base-\(7\) representation of \(\frac{7^k-1}{11}\): one short suffix for \(k=10\), one initial boundary block, one repeating 10-digit block, and one final block.

For \(k=10\), the short suffix is applied once to the initial state \(\mathbf{v}(4)\). For \(k=10t\ge 20\), the implementation applies the initial boundary block, raises the repeating block transformation to the power \(t-2\) by binary exponentiation, applies the final block, and then reads the third state component. That component is \(F\!\left(\frac{7^k-1}{11}\right)\), so it is exactly \(H(k)\).

Complexity Analysis

Each matrix has fixed dimension \(5\), so one multiplication is constant-time in the asymptotic sense. The only nontrivial growth comes from raising the repeating block transformation to the power \(t-2\), where \(t=k/10\). Binary exponentiation therefore gives \(O(\log t)=O(\log k)\) matrix multiplications and \(O(1)\) extra memory.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=672
2. Base-\(7\) numerals and positional notation: Wikipedia — Radix
3. Geometric series: Wikipedia — Geometric series
4. Matrix exponentiation: Wikipedia — Exponentiation by squaring