Problem 973: Random Dealings
View on Project EulerProject Euler Problem 973 Solution
EulerSolve provides an optimized solution for Project Euler Problem 973, Random Dealings, with C++, Python, Java, and a step-by-step mathematical explanation.
Problem Summary The three solutions show that Random Dealings is organized around a single arithmetic quantity \(X(n)\), and the required task is to evaluate \(X(10000)\) modulo \(10^9+7\). The key point is that the answer is not obtained by simulating individual dealings. Instead, the full result splits into independent dyadic scales \(2^k\), together with one extra correction that appears only when \(n\) is odd. Write \(M=10^9+7\), and let \(\varepsilon(n)=1\) when \(n\) is odd and \(\varepsilon(n)=0\) when \(n\) is even. The common structure extracted from the implementations is $$X(n)\equiv \varepsilon(n)\bigl(2^{n-1}-1\bigr)+\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k A_k(n)\pmod{M}.$$ So the real mathematics lies in the scale-dependent sequence \(A_k(n)\). For the scale \(s=2^k\), the contribution is zero before \(n=s\), it has an explicit closed form on the first band \(s \le n \lt 2s\), and after that it follows a longer linear recurrence with a fixed-width rolling sum. Those are the problem-specific objects that drive all three programs. Mathematical Approach The solutions encode a clean scale-by-scale description. Once a power-of-two scale \(s=2^k\) is fixed, everything can be expressed in terms of a single sequence \(A_k(n)\) and one auxiliary interval sum. Dyadic decomposition of the answer For every \(k \ge 1\), let \(s=2^k\)....
Detailed mathematical approach
Problem Summary
The three solutions show that Random Dealings is organized around a single arithmetic quantity \(X(n)\), and the required task is to evaluate \(X(10000)\) modulo \(10^9+7\). The key point is that the answer is not obtained by simulating individual dealings. Instead, the full result splits into independent dyadic scales \(2^k\), together with one extra correction that appears only when \(n\) is odd.
Write \(M=10^9+7\), and let \(\varepsilon(n)=1\) when \(n\) is odd and \(\varepsilon(n)=0\) when \(n\) is even. The common structure extracted from the implementations is
$$X(n)\equiv \varepsilon(n)\bigl(2^{n-1}-1\bigr)+\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k A_k(n)\pmod{M}.$$
So the real mathematics lies in the scale-dependent sequence \(A_k(n)\). For the scale \(s=2^k\), the contribution is zero before \(n=s\), it has an explicit closed form on the first band \(s \le n \lt 2s\), and after that it follows a longer linear recurrence with a fixed-width rolling sum. Those are the problem-specific objects that drive all three programs.
Mathematical Approach
The solutions encode a clean scale-by-scale description. Once a power-of-two scale \(s=2^k\) is fixed, everything can be expressed in terms of a single sequence \(A_k(n)\) and one auxiliary interval sum.
Dyadic decomposition of the answer
For every \(k \ge 1\), let \(s=2^k\). The scale \(s\) contributes only when \(n \ge s\), so it is convenient to extend the sequence by \(A_k(n)=0\) for \(n \lt s\). The global answer is then the sum of all active scales, plus the odd-\(n\) correction \(\varepsilon(n)\bigl(2^{n-1}-1\bigr)\).
This decomposition is the first important invariant: there is no interaction term mixing different \(k\)-values. Each scale can be solved independently and only combined at the very end with the weight \(2^k\).
The start-up band \(2^k \le n \lt 2^{k+1}\)
The first nonzero values are not produced by the long recurrence. They are given explicitly by
$$A_k(s)=1,\qquad A_k(i)=(i-s+2)\,2^{\,i-s-1}\quad (s \lt i \lt 2s).$$
So inside the first dyadic band, \(A_k(i)\) is a linear factor times a power of two. This start-up band provides the initial conditions for the rest of the computation. It is treated separately because, before \(i\) reaches \(2s\), the lagged terms at distances \(s\) and \(s+1\) have not both become part of the active history yet.
A recurrence with an \(s-2\) term window
Once \(i \ge 2s\), the implementations switch to a recurrence. Define the rolling window
$$W_k(i)=\sum_{j=i-s+1}^{i-2} A_k(j),$$
where the empty sum is interpreted as \(0\). In particular, when \(s=2\), this window has length \(0\) and vanishes identically.
For every \(i \ge 2s\), the sequence satisfies
$$A_k(i)=3A_k(i-1)-W_k(i)-4A_k(i-s)+4A_k(i-s-1)\pmod{M}.$$
This shows exactly which history matters: the previous value, two lagged values spaced by the scale \(s\), and the sum of the \(s-2\) values in between. The rolling sum itself obeys
$$W_k(i+1)=W_k(i)+A_k(i-1)-A_k(i-s+1).$$
That update is crucial. A naive evaluation of \(W_k(i)\) would cost \(O(s)\) per step, but this invariant turns it into \(O(1)\) time per step.
Worked example: the first checkpoint and the first nonempty window
Take \(n=4\). Two scales are active: \(k=1\) with \(s=2\), and \(k=2\) with \(s=4\).
For \(k=1\), the start-up values are \(A_1(2)=1\) and \(A_1(3)=3\). Because \(s=2\), the window term is empty, so the first recurrence step is
$$A_1(4)=3A_1(3)-4A_1(2)+4A_1(1)=3\cdot 3-4\cdot 1+4\cdot 0=5.$$
For \(k=2\), we are exactly at the boundary \(n=s\), so \(A_2(4)=1\). Therefore
$$X(4)=2^1A_1(4)+2^2A_2(4)=2\cdot 5+4\cdot 1=14,$$
which matches the built-in checkpoint.
To see a genuine nonempty window, stay with \(k=2\), so \(s=4\). The start-up values are
$$A_2(4)=1,\qquad A_2(5)=3,\qquad A_2(6)=8,\qquad A_2(7)=20.$$
At \(i=8\), the rolling sum is
$$W_2(8)=A_2(5)+A_2(6)=3+8=11,$$
and the recurrence gives
$$A_2(8)=3\cdot 20-11-4\cdot 1+4\cdot 0=45.$$
This is exactly the pattern used for all larger \(n\): a closed-form start-up region followed by a windowed linear recurrence.
Reconstructing \(X(n)\)
After every active scale has supplied its value \(A_k(n)\), the final answer is assembled as
$$X(n)\equiv \varepsilon(n)\bigl(2^{n-1}-1\bigr)+\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k A_k(n)\pmod{M}.$$
Because the scales are independent, this reconstruction is simple: compute each \(A_k(n)\), weight it by \(2^k\), add the odd correction when needed, and reduce modulo \(M\).
How the Code Works
The C++, Python, and Java implementations all follow the same mathematical pipeline. They differ only in language-specific orchestration, not in the underlying recurrence.
Per-scale computation
For a fixed \(k\), the implementation sets \(s=2^k\). If \(n \lt s\), the scale contributes \(0\). If \(s \le n \lt 2s\), it returns the explicit start-up formula immediately. Otherwise it allocates a linear array for the values \(A_k(i)\), seeds the interval \(s \le i \lt 2s\) with the closed form, and initializes the first rolling sum
$$W_k(2s)=\sum_{j=s+1}^{2s-2}A_k(j).$$
From there, it advances from \(i=2s\) up to \(i=n\), updating \(A_k(i)\) with the recurrence and then shifting the rolling sum by one step. Powers of two are always taken modulo \(M\) with modular exponentiation.
Parallel assembly and validation
Once the scale solver is available, the global routine launches one independent task for each \(k\) with \(2^k \le n\). When a task returns \(A_k(n)\), the result is multiplied by \(2^k\) and added into the total. If \(n\) is odd, the extra term \(2^{n-1}-1\) is inserted before the scale sum is accumulated.
All three implementations also verify the same small checkpoints before producing the final answer: \(X(2)=2\), \(X(4)=14\), and \(X(10)=1418\). Those checks are a strong sanity test for both the closed-form start-up band and the long recurrence.
Complexity Analysis
There are \(\lfloor \log_2 n \rfloor\) active scales. For each scale, the implementation performs only constant work per index once the rolling window invariant is in place, so one scale costs \(O(n)\) time. Summed over all scales, the arithmetic work is \(O(n\log n)\).
Memory usage is \(O(n)\) for one active scale because it stores a linear table of values up to \(n\). Since the implementations evaluate different scales independently and can run them in parallel, the peak live memory can be larger in practice, but the mathematical core of each scale remains linear-space.
Footnotes and References
- Problem page: https://projecteuler.net/problem=973
- Dynamic programming: Wikipedia - Dynamic programming
- Recurrence relation: Wikipedia - Recurrence relation
- Modular exponentiation: Wikipedia - Modular exponentiation
- Power of two: Wikipedia - Power of two
- Sliding window technique: GeeksforGeeks - Sliding Window Technique
Problem 973 source code
C++
#include <iostream>
#include <vector>
#include <future>
#include <cstdlib>
using namespace std;
long long MOD = 1e9 + 7;
long long power(long long b, long long e) {
long long r = 1;
b %= MOD;
while (e) {
if (e & 1) r = (r * b) % MOD;
b = (b * b) % MOD;
e >>= 1;
}
return r;
}
long long get_stable(int k, int n) {
long long s = 1LL << k;
if (n == s) return 1;
long long t1 = (n - s + 2) % MOD;
long long exp = n - s - 1;
return (t1 * power(2, exp)) % MOD;
}
long long solve_bit(int k, int n) {
long long s = 1LL << k;
if (n < s) return 0;
long long es = 1LL << (k + 1);
if (n < es) return get_stable(k, n);
vector<long long> dp(n + 1, 0);
for (int i = s; i < es; ++i) dp[i] = get_stable(k, i);
long long c_sum = 0;
long long ub = 1LL << k;
if (ub > 2) {
for (int i = es - 2; i >= es - ub + 1; --i)
c_sum = (c_sum + dp[i]) % MOD;
}
for (int i = es; i <= n; ++i) {
long long t1 = (3 * dp[i - 1]) % MOD;
long long t3 = (4 * dp[i - ub]) % MOD;
long long t4 = (4 * dp[i - ub - 1]) % MOD;
long long val = (t1 - c_sum - t3 + t4) % MOD;
dp[i] = (val + 2 * MOD) % MOD;
if (ub > 2) {
c_sum = (c_sum + dp[i - 1]) % MOD;
c_sum = (c_sum - dp[i - ub + 1] + MOD) % MOD;
}
}
return dp[n];
}
long long solve_X(int n) {
long long tot = 0;
if (n % 2 != 0) tot = (power(2, n - 1) - 1 + MOD) % MOD;
vector<future<long long>> futs;
for (int k = 1; k < 20; ++k) {
if ((1LL << k) > n) break;
futs.push_back(async(launch::async, solve_bit, k, n));
}
for (int k = 0; k < futs.size(); ++k) {
long long val = futs[k].get();
long long term = (val * power(2, k + 1)) % MOD;
tot = (tot + term) % MOD;
}
return tot;
}
int main() {
if (solve_X(2) != 2) exit(1);
if (solve_X(4) != 14) exit(2);
if (solve_X(10) != 1418) exit(3);
cout << solve_X(10000) << endl;
return 0;
}Python
import concurrent.futures
MOD = 10**9 + 7
def power(b, e):
return pow(b, e, MOD)
def get_stable(k, n):
s = 1 << k
if n == s:
return 1
t1 = (n - s + 2) % MOD
exp = n - s - 1
return (t1 * power(2, exp)) % MOD
def solve_bit(k, n):
s = 1 << k
if n < s:
return 0
es = 1 << (k + 1)
if n < es:
return get_stable(k, n)
dp = [0] * (n + 1)
for i in range(s, es):
dp[i] = get_stable(k, i)
c_sum = 0
ub = 1 << k
if ub > 2:
for i in range(es - 2, es - ub, -1):
c_sum = (c_sum + dp[i]) % MOD
for i in range(es, n + 1):
t1 = (3 * dp[i - 1]) % MOD
t3 = (4 * dp[i - ub]) % MOD
t4 = (4 * dp[i - ub - 1]) % MOD
val = (t1 - c_sum - t3 + t4) % MOD
dp[i] = (val + 2 * MOD) % MOD
if ub > 2:
c_sum = (c_sum + dp[i - 1]) % MOD
c_sum = (c_sum - dp[i - ub + 1] + MOD) % MOD
return dp[n]
def process_k(args):
k, n = args
return k, solve_bit(k, n)
def solve_X(n):
tot = 0
if n % 2 != 0:
tot = (power(2, n - 1) - 1 + MOD) % MOD
tasks = []
for k in range(1, 20):
if (1 << k) > n:
break
tasks.append((k, n))
with concurrent.futures.ProcessPoolExecutor() as executor:
results = dict(executor.map(process_k, tasks))
for k, n_k in tasks:
val = results[k]
term = (val * power(2, k)) % MOD
tot = (tot + term) % MOD
return tot
def run_checkpoints():
assert solve_X(2) == 2
assert solve_X(4) == 14
assert solve_X(10) == 1418
def solve():
return str(solve_X(10000))
if __name__ == "__main__":
run_checkpoints()
print(solve())
Java
import java.util.stream.IntStream;
public class Euler973 {
static final long MOD = 1000000007;
static long power(long b, long e) {
long r = 1;
b %= MOD;
while (e > 0) {
if ((e & 1) != 0)
r = (r * b) % MOD;
b = (b * b) % MOD;
e >>= 1;
}
return r;
}
static long getStable(int k, int n) {
long s = 1L << k;
if (n == s)
return 1;
long t1 = (n - s + 2) % MOD;
long exp = n - s - 1;
return (t1 * power(2, exp)) % MOD;
}
static long solveBit(int k, int n) {
long s = 1L << k;
if (n < s)
return 0;
long es = 1L << (k + 1);
if (n < es)
return getStable(k, n);
long[] dp = new long[n + 1];
for (int i = (int) s; i < (int) es; ++i) {
dp[i] = getStable(k, i);
}
long cSum = 0;
long ub = 1L << k;
if (ub > 2) {
for (int i = (int) es - 2; i >= (int) (es - ub + 1); --i) {
cSum = (cSum + dp[i]) % MOD;
}
}
for (int i = (int) es; i <= n; ++i) {
long t1 = (3 * dp[i - 1]) % MOD;
long t3 = (4 * dp[i - (int) ub]) % MOD;
long t4 = (4 * dp[i - (int) ub - 1]) % MOD;
long val = (t1 - cSum - t3 + t4) % MOD;
dp[i] = (val + 2 * MOD) % MOD;
if (ub > 2) {
cSum = (cSum + dp[i - 1]) % MOD;
cSum = (cSum - dp[i - (int) ub + 1] + MOD) % MOD;
}
}
return dp[n];
}
static long solveX(int n) {
long tot = 0;
if (n % 2 != 0) {
tot = (power(2, n - 1) - 1 + MOD) % MOD;
}
int maxK = 0;
for (int k = 1; k < 20; ++k) {
if ((1L << k) > n)
break;
maxK = k;
}
long sumP = IntStream.rangeClosed(1, maxK)
.parallel()
.mapToLong(k -> {
long val = solveBit(k, n);
return (val * power(2, k)) % MOD;
})
.sum() % MOD;
return (tot + sumP) % MOD;
}
public static String solve() {
return Long.toString(solveX(10000));
}
public static void main(String[] args) {
if (solveX(2) != 2) {
System.out.println("Validation failed");
return;
}
if (solveX(4) != 14) {
System.out.println("Validation failed");
return;
}
if (solveX(10) != 1418) {
System.out.println("Validation failed");
return;
}
System.out.println(solve());
}
}