Detailed mathematical approach

Problem Summary

For each integer \(k \ge 2\), define the sequence

$f_k(0)=1,\qquad f_k(n)=f_k(n-1)+f_k\left(\left\lfloor\frac{n}{k}\right\rfloor\right)\qquad (n\ge 1).$

The required value is

$\sum_{k=2}^{10} f_k(N)\pmod{10^9+7},$

with \(N=10^{14}\) in the standard instance. A direct dynamic program up to \(N\) is impossible, so the solution converts the recurrence into a digit-by-digit polynomial computation.

Mathematical Approach

Fix one base \(k\), and write \(f(n)=f_k(n)\). Let the base-\(k\) expansion of \(n\) be

$n=d_0+d_1k+\cdots+d_Lk^L,\qquad 0\le d_i\le k-1.$

The aim is to evaluate \(f(n)\) without iterating through every integer from \(1\) to \(n\).

Step 1: Rewrite the Recurrence as a Cumulative Sum

Since \(f(0)=1\), the recurrence telescopes into

$f(n)=\sum_{m=0}^{n} f\left(\left\lfloor\frac{m}{k}\right\rfloor\right).$

Now write \(n=kx+s\) with \(0\le s\le k-1\). Grouping the integers \(m\) by the quotient \(q=\lfloor m/k\rfloor\) gives

$f(kx+s)=k\sum_{q=0}^{x-1} f(q)+(s+1)f(x).$

So one base-\(k\) digit tells us how a prefix sum of previous values is sampled.

Step 2: Expand Repeatedly Until Only Digits Remain

Apply the same identity again to \(f(x)\), then to the next quotient, and continue until the quotient becomes \(0\). The result is an exact nested-sum formula:

$f(n)=\sum_{x_L=0}^{d_L}\sum_{x_{L-1}=0}^{kx_L+d_{L-1}}\cdots\sum_{x_1=0}^{kx_2+d_1}\sum_{x_0=0}^{kx_1+d_0}1.$

Each level introduces one variable whose upper bound is \(k\) times the next variable plus the corresponding digit of \(n\). The depth is only the number of base-\(k\) digits, which is \(O(\log_k n)\).

Step 3: Package One Layer as an Operator

For any function \(P(x)\), define

$T_s[P](x)=\sum_{t=0}^{kx+s} P(t),\qquad 0\le s\le k-1.$

Then the nested sum can be written compactly as

$f(n)=\left(T_{d_L}\circ T_{d_{L-1}}\circ\cdots\circ T_{d_0}\right)[1](0).$

Thus the problem becomes: start from the constant polynomial \(1\), and repeatedly apply the operator “take a prefix sum and evaluate it at \(kx+s\)” according to the digits of \(n\).

Step 4: Why Polynomial States Are Enough

If \(P(x)\) is a polynomial of degree \(r\), then its prefix sum

$S[P](x)=\sum_{t=0}^{x}P(t)$

is a polynomial of degree \(r+1\), and the substitution \(x\mapsto kx+s\) preserves polynomial form. Therefore repeated applications of \(T_s[P](x)=S[P](kx+s)\) never leave the polynomial world.

For a monomial \(x^p\), the required prefix sum is

$\sum_{t=0}^{x} t^p=\sum_{j=0}^{p} S(p,j)\,j!\binom{x+1}{j+1},$

where \(S(p,j)\) denotes a Stirling number of the second kind. This Faulhaber-type identity is exactly what lets the implementation precompute every power-sum polynomial once and reuse it.

Step 5: Handle the Upper Bound with Two Digit States

The implementation does not compose a single operator chain literally. Instead it scans the base-\(k\) digits of \(n\) from least significant to most significant and keeps two polynomial states:

one state for choices that still match the already processed part of \(n\), and one state for choices that are already strictly smaller.

If the next digit is \(d_j\), and \(E_{j-1}\) and \(B_{j-1}\) are the exact and below states from the previous step, then with \(S[P](x)=\sum_{t=0}^{x}P(t)\) we have

$B_j(x)=\sum_{s=0}^{k-1} S[B_{j-1}](kx+s),$

$E_j(x)=\sum_{s=0}^{d_j-1} S[B_{j-1}](kx+s)+S[E_{j-1}](kx+d_j).$

The initial one-digit states are

$B_0(x)=k,\qquad E_0(x)=d_0+1,$

because a full last-digit block contributes \(k\) choices, while the truncated block allowed by \(d_0\) contributes \(d_0+1\). After the final digit, the desired value is simply

$f(n)=E_L(0).$

Worked Example: \(k=5,\ n=10\)

Since \(10=(20)_5\), the digits are \(d_0=0\) and \(d_1=2\). The nested-sum formula gives

$f_5(10)=\sum_{x_1=0}^{2}\sum_{x_0=0}^{5x_1}1=1+6+11=18,$

which matches the sample checkpoint used by the implementation.

The polynomial-state update gives the same answer. Initially, \(B_0(x)=5\) and \(E_0(x)=1\). Their prefix sums are \(5x+5\) and \(x+1\). Therefore

$E_1(x)=\sum_{s=0}^{1}(25x+5s+5)+(5x+3)=55x+18,$

so

$f_5(10)=E_1(0)=18.$

How the Code Works

The C++, Python, and Java implementations follow the same plan. They first determine a safe maximum polynomial degree from the binary length of \(N\), because base \(2\) yields the largest number of digits. Then they precompute binomial coefficients, Stirling numbers of the second kind, factorials, and the explicit polynomials for \(\sum_{t=0}^{x} t^p\) for every degree that can appear.

For each \(k=2,3,\dots,10\), the implementation converts \(N\) to base \(k\), initializes the exact and below states for the least significant digit, and processes the remaining digits one by one. Each digit step performs two generic algebraic operations:

$P(x)\longmapsto \sum_{t=0}^{x}P(t),\qquad P(x)\longmapsto P(kx+s).$

Because the states are stored by coefficients, both operations are done symbolically modulo \(10^9+7\), never by iterating up to \(N\). After the highest digit is processed, the exact-state polynomial is evaluated at \(x=0\), giving \(f_k(N)\). The final answer is the sum of these nine values modulo \(10^9+7\).

Complexity Analysis

Let \(D=\lfloor\log_2 N\rfloor+2\). This bounds the number of digits in every base from \(2\) to \(10\), so every polynomial degree is \(O(D)\). The precomputation of binomial and power-sum data costs \(O(D^3)\) time and \(O(D^2)\) memory. For a fixed base \(k\), processing all digits costs \(O(kD^3)\) time in the worst case, because the degree grows linearly with the number of processed digits and each digit step performs a bounded number of \(O(D^2)\) polynomial transforms. Here \(k\le 10\) and \(D\) is only about the number of binary digits of \(10^{14}\), so the method is easily fast enough.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=546
2. Positional notation: Wikipedia — Positional notation
3. Stirling numbers of the second kind: Wikipedia — Stirling numbers of the second kind
4. Faulhaber's formula: Wikipedia — Faulhaber's formula